蛋疼研究之怎样刷屏最快?

    最近在做网站测试时,遇到了需要在输入框输入 3000 字的测试用例。联想到平时聊天时经常复制粘贴一堆笑脸刷屏讨 MM 欢心的行为,不由想到了一个有趣的问题:为了输入一定数量的字符,最少需要按多少个键?

    大家最常用的策略或许是, 先输一些字符,然后全选复制,粘贴到一定规模后,再全选复制,粘贴到一个新的数量级,如此反复。注意到进入全选状态(并且复制后),第一次粘贴将会覆盖掉选中的部分,第二次粘贴才会增加原来的文本长度。当然,全选复制后按一次向右键也可以消除选中状态,不过却并没有节省按键次数。因此我们规定,在输入字符时只有四种原子操作:

      1. 按一个按键,输入一个字符
      2. 按 Ctrl + A ,全选
      3. 按 Ctrl + C ,复制
      4. 按 Ctrl + V ,粘贴


    排除明显不划算的行为,真正的决策其实只有两种:

      1. 按一次按键,输入一个字符
      2. 按 k + 2 次按键,将现有内容复制成 k 份。

    这样一来,我们就有了一个清晰的递推思路。设 f(n) 表示输入 n 个字符所需要的最少按键次数,则 f(n) 将会在 f(n-1) + 1 和 f(n/k) + k + 2 中取一个最小值(其中 k 取遍 n 的所有约数)。
    Mathematica 牛 B 就牛 B 在,这样的动态规划程序只需要一行便能写完:

  

    可见,输入 100 个字符需要 18 次按键。具体方法是,用 5 次按键输入 5 个字符,再用 7 次按键把它变成 25 个字符,再用 6 次按键把它变成 100 个字符。

  

    有趣的是,这个函数并不是单调的。输入 99 个字符需要的按键次数比输入 100 个字符需要的按键次数更多一些,事实上这最少要花费 20 次按键。方法是,先用 5 次按键输入 5 个字符,4 次按键把它变成 10 个字符,单独按一次键添加一个字符, 5 次按键把字符数复制粘贴到 33 ,再来 5 次按键把字符数复制粘贴到 99 。

    下面这个图是输入不同的字符数所需要的最少按键。

  

    可以看到, 20 次按键足以应付 100 以内任何数量的字符,也就是说 99 个字符所需要的按键次数已经是 100 个字符以内的情况中最大的了。不过,最悲剧的应该要数 83 个字符了,它是所有至少要用 20 次按键的情况中字符个数最少的(也即首次出现的要用 20 次按键才能输入的情况)。对应的输入方案是 5 → 20 → 80 → 81 → 82 → 83 (直到分析到这里,我才意识到,在考虑输入指定数量的字符时,引入退格键可以带来的更少的按键次数)。

    那么, 20 次按键最多可以输入多少个字符呢?为了解决这个问题,我们可以给出另外一个递推式。令 g(n) 为 n 次按键最多可以输入的字符个数。对于每一个 n ,考虑两种转移决策:要么在 n – 1 次按键能够达到的最大字符数基础上加 1 ,要么把 n – k 次按键能够达到的字符数复制成 k – 2 份。也就是说, g(n) 就等于 g(n-1) + 1 和 g(n-k) * (k-2) 的最大值,其中 k 可以从 3 取到 n – 1。我们还是用一句话写下这个转移方程式:

  

    可以看到, 20 次按键足以输入 150 个字符(方案是 6 → 30 → 150 ), 30 次按键足以输入 1600 个字符(方案是 5 → 25 → 100 → 400 → 1600 )。这样看上去,我们好像有了快速刷屏的指导思想:粘贴到原来的 4 倍长或者 5 倍长后再进行下一波全选复制粘贴似乎总是最优的选择。另外,这个数列增长得很快, 80 次按键能输入的字符数就已经上亿了。看来,要想刷屏到系统崩溃并不难,不足 100 次按键就能产生上 G 的数据。

    似乎这个增长速度是指数级的。描出 g(n) 的图象证实了我们这一想法:

  

    我们自然而然地想到观察数列 g(n) 相邻两项的比值:

  

    容易看到,当 n 到了一定大时,数列已经呈现出了一定的规律,多数时候都是以 1.25 倍的速度增长。给出并证明数列的通项公式或许会是一件非常有趣的事情。

53 条评论

回复给 wallc 取消回复