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

《蛋疼研究之怎样刷屏最快？》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、蛋疼研究之怎样刷屏最快?最近在做网站测试时，遇到了需要在输入框输入3000字的测试川例。联想到平时聊天时经常复制粘贴亠堆笑脸刷屏讨MM欢心的行为，不由想到了•个有趣的问题：为了输入•定数量的字符，最少需要按多少个键？大家最常用的策略或许是，先输-些字符，然后全选复制，粘贴到一定规模后，再全选复制，粘贴到」个新的数罐级，如此反复。注意到进入全选状态(并且复制后)，第一次粘贴将会覆盖掉选中的部分，第二次粘贴才会增加原來的文木K度。“1然，金选复制后按一次向右键也可以消除选中状态，不过却并没冇节省按键次数。因此我们规定，在输入字符时只有四种原子操作：1.按一个按键

2、，输入一个字符2.按Ctrl+A,全选3.按Ctrl+C,复制4.按Ctri+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在，这样的动态规划程序只需要一行便能写完：in[i]：=f[n_]:=f[n]=Min[(f[n/#]♦片♦2)&/@Divisors[n][[2

3、;;]]rf[n-1]♦1];f[l]：=1；ln[3]:=f[100]Ou1(3]=18可见，输入100个字符需要18次按键。具体方法是，用5次按键输入5个字符，再用7次按键把它变成25个字符，再用6次按键把它变成100个字符。ln[4]:=f[99]0ul(4]=20有趣的是，这个函数并不是单调的。输入99个字符需要的按键次数比输入100个字符需耍的按键次数更多一些，事实上这最少要花费20次按键。方法是，先用5次按键输入5个字符，4次按键把它变成10个字符，单独按…次键添加…个字符，5次按键把字符数复制粘贴到33，再來5次按键把字符数复制粘贴到99o下而

4、这个图是输入不同的字符数所需要的最少按键。可以看到，20次按键足以应付100以内任何数量的字符，也就是说99个字符所需要的按键次数已经是100个字符以内的情况小最人的了。不过，瑕悲剧的应该要数83个字符了，它是所仃至少要用20次按键的悄况屮字符个数最少的(也即首次出现的要用20次按键方能输入的情况)。对应的输入方案是520-80-81-82-83(氏到分析到这里，我才总识到，在考虑输入指定数量的字符时,引入退格键可以帯來的更少的按键次数)。那么，20次按键最多町以输入多少个字符呢？为了解决这个问题，我们可以给出另外•个递推式。令g(n)为n次按键最多可以输入

5、的字符个数。对于每一个n,考虑两种转移决策：要么在n・1次按键能够达到的最大字符数丛础上加1,要么把n・k次按键能够达到的字符数复制成k-2份。也就是说，g(n)就等于g(n-1)+1和g(n-k)*(k-2)的域大值，其小k可以从3取到n・1。我们还是用一句话写下这个转移方程式：in[6]：=g[Q_]：=g[n]=Max[g[n-1]flzTable[g[n-k]♦(k-2)z{kr3，n-1)]];g[i]i;ln[d]：=Table[{n,g[n]},{n,10z100r10}]//Transpose//TableFoxnn8t[8WTab*eFor

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

7、数据。似乎这个増长速度是指数级的。描出g(n)的图彖证实了我们这-•想法:in[9]：=ListPlot[Table[g[n]9{n,1r100}]9PlotRange-♦{0r10A9}]1.xlO9•1.xlO8-*■1.X108•■Ou1[9]=4.X108-•■♦2.X108•020406080100我们自然而然地想到观察数列g(n)相邻两项的比值:in[io]：=ListPlot[Table[g[n]/g[n-1]9{nz2.100}]9PiotRangcf{lr1.5}]Ou1(l0]=容易看到，当n到了一定人时，数列已经呈现出了一定的规律，多数

8、吋候都是以1・25倍的速度增长。给出并证明数列的通项