蛋疼的刷屏算法问题
最近在v2ex的看到一道有趣而蛋疼的求助帖，搜了一下，原题刊登在神人matrix67的博客上。先看看题目：
你有一个特殊的键盘，只有四个键：
a, 输入字符actrl+a, 全选ctrl+c, 复制ctrl+v, 粘贴
还需要说明一下的是，上面的ctrl+x都只算一个按键，而且全选之后的第一次复制粘贴，是不会增加字符长度的，（也就是只覆盖了已有字符，这个在现实生活中应该有体会）。
这是一个不着边际的题目，乍看非常简单，但是细想一下脑子就打结了。牛逼的matrix67大神，用两个公式，三下五除二就搞定了这个问题：
- f(n) = f(n-1) + 1
- f(n) = f(n/k) + k + 2
然后在以上两种情况下取最小值，再用递推法，递推的层数就是所走的步数了。
具体的计算情况在博客里有介绍，这里不再赘述，我感兴趣的是上面这两个公式，是否能涵盖所有情况，已经怎么推导出这两个公式，这才是真正神奇的地方，而且matrix67也没有给出详细的推导过程。
倒推法
要推导出递推公式，顺着题目的意思思考是不行的（事实上，我认为所有最大值n不确定的问题，都需要逆向思维，否则很容易就陷入无底深渊了）。我们可以看到问题结束的几种情况：
- 最后一个按键是
a，则这种情况最简单，f(n) = f(n) + 1。 - 最后一个按键是
cv，则这种情况下，最后第二个按键只能是cc或者cv，最后第三个按键只能是ca，cc或cv，整个按键流程可以归纳为x->ca->cc->cv...cv->y，其中x是在全选前的字符数，y表示总字符数，那么设按键cv的次数为k，全选复制阶段的按键次数就是k+2，而且值得一提的是，这个k必须大于或等于2，否则复制就是多余的。然后y是由x复制k次而来，所以就不难推导出公式f(n) = f(n/k) + k + 2，其中k为大于等于2的n的约数。
由此，两个公式都被推导出来了，但这就结束了吗？是否所有的情况都涵盖到了？根据计算结果可以得出f(n)并非单调函数，也就是说f(n-2)有可能小于f(n-1)，那么会不会有f(n-2)到f(n)比f(n-1)到f(n)快的情况呢，这个还需要证明一下：
1
| |
f(n-2)到f(n-1)最快的路径应该就是f(n-2) + 1了吧，所以不可能是这种情况，那么还剩下一种情况：
1
| |
那么这里又回到了之前预设的第二种情况，其本身就是需要参与递归的比较的，所以这种情况也是已涵盖了的。
这样看了是我多虑了，下面要做的就是将这个递归程序写出来。
实现
从程序的角度看，其实算法中还有一些值得优化的地方：
- 1到100之间(这个范围甚至可以再扩大些)的素数的最小步数可以事先计算出来作为常数数组保存，这些数字是递归的终点，预处理可以让递归的最后一步变成O(1)，而不是O(n)
- 上面提到的，k是从2到n，但事实上范围可以更小。在
f(n) = f(n/k) + k +2中，随着n的增加，步数的增加并不是线性的，步数的增速的是逐渐放缓的，但是k对于步数的增长变化却是线性的。对公式求导，f(n/k)' < 1而k' = 1，所以我们有理由相信，k的范围只需要从2到√n（包含）就可以了。
实际上，第二点对于代码的效率优化是显而易见的，差不多是省了50%的时间。而第一点对于效率的提升是相当惊人的，以n=200为例，有素数索引和没有素数索引的情况下执行时间如下：
- 4.05s user 0.06s system 99% cpu 4.129 total # no index
- 0.05s user 0.01s system 92% cpu 0.067 total # have index
提升了整整60倍，而且随着n的提高，这个差距会更加明显，100以内的索引可以涵盖n等于0到10000的情况，当n大于10000时，提升这个素数索引即可，代码中提供了很方便的实现索引生成的方法。
代码
我做了一个ruby版本的demo，放在gist上。
扩展
这个命题其实还可以扩展，比方说还是这四个键，但是ctrl+a, ctrl+c, ctrl+v均算作两次按键，那么情况又复杂了，因为不光增加了按键的不确定性，而且复制时候增加了一种情况，在不松开ctrl的情况下，可以多次按v来实现复制。这个扩展命题只有等将来有时间再思考了。
这个命题仍然套用倒推法，只需要对第二个公式做一些修改即可：
- f(n) = f(n-1) + 1
- f(n) = f(n/k) + k + 5
下面的事情就跟之前一模一样啦，这里也有一个demo版本，在不算两次按键的时候，最少在n=9时出现了复制，算作两次按键的时候，到n=15才出现复制。