写文章
提问题
写文章
提问题
这是我今天刷知乎的时候看到的一个问题，认为按Ctrl+C时已经进行了全选（Ctrl+A），只能按Ctrl和C，V三个键，不可以长按复制。
刚开始的时候认为一定是 复制->粘贴->复制->粘贴 这样最少，单词个数成指数增长，但是后来发现并不是这样，当按键次数为6次的时候，复制->粘贴->复制->粘贴 这种方式一共得到8个单词（2的三次方），而Ctrl C、V、V、C、V、V这种方式一共得到了9个单词。有没有什么算法可以准确的求出按键的方案？（不要穷举法）
jerkzhang
这是一个很好的动态规划问题。但是我没跑出结果来。估计是还有更好的算法吧。
我对这个问题的看法就是，其实拆解下来可以归纳为两种动作的选择：
动作一：复制 + 粘贴 （需要按2次）
动作二：粘贴 （需要按1次）
恰好达到这个词的目标次数的最少按键次数的方案大多情况上来说都是不只一种方案的，但无疑的是有一种贪心算法是肯定是属于最少按键次数的方案，即：动作一的优先级别比动作二高，即每一层递推中都优先选择动作一，只要找到等于目标次数的方案，那就是最少按键的方案。一切到此结束。
这种贪心算法的根源在于乘法永远比加法更具有威力。（当然毕竟是贪心算法，我感觉这种捷径应该是对的）
上代码：
# coding=utf-8
import sys
sys.setrecursionlimit(100000000)
res_n = 100000000
# n为单词次数
# copy_n 为复制板内单词数量
# 动作1 ctrl+c 后 ctrl+v
def action1( action_list, n, copy_n ):
action_list += "CV"
copy_n = n
n *= 2
# print action_list, n
# 检验结果
if n == res_n:
print action_list
print len( action_list )
return "cool"
elif n > res_n:
return "fuck"
# 继续下一层
res = action1( action_list, n, copy_n )
if res in [ "fuck" ]:
res = action2( action_list, n, copy_n )
return res
# 动作2 ctrl+v
def action2( action_list, n, copy_n ):
action_list += "V"
n += copy_n
# print action_list, n
# 检验结果
if n == res_n:
print action_list
print len( action_list )
return "cool"
elif n > res_n:
return "fuck"
# 继续下一层
res = action1( action_list, n, copy_n )
if res in [ "fuck" ]:
res = action2( action_list, n, copy_n )
return res
action1( "", 1, 0 )
但是1亿这个数据对python来说太大，有捷径python也跑不出来，但是这个逻辑应该是可以的。把数字改小一点，如下所示：
当res_n = 10000 CVCVCVCVCVVVVCVVVVCVVVVCVVVV 28 当res_n = 100000 CVCVCVCVCVCVVVVCVVVVCVVVVCVVVVCVVVV 35 当res_n = 1000000 CVCVCVCVCVCVCVVVVCVVVVCVVVVCVVVVCVVVVCVVVV 42
备注：python在做递推时，传参的时候别用list类型的变量，因此，上述代码中的action_list并不是真正的list类型而是string类型。