[3d眼睛]蛋疼研究之怎样刷屏最快？

最近在做网站测验时，遇到了需求在输入框输入3000字的测验用例。联想到平常谈天时常常仿制张贴一堆笑脸刷屏讨MM欢心的行为，不由想到了一个风趣的问题：为了输入必定数量的字符，最少需求按多少个键？

咱们最常用的战略或许是，先输一些字符，然后全选仿制，张贴到必定规划后，再全选仿制，张贴到一个新的数量级，如此重复。注意到进入全选状况（而且仿制后），第一次张贴将会覆盖掉选中的部分，第2次张贴才会增加本来的文本长度。当然，全选仿制后按一次向右键也能够消除选中状况，不过却并没有节约按键次数。因而咱们规则，在输入字符时只要四种原子操作：

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倍的速度增加。给出并证明数列的通项公式或许会是一件十分风趣的工作。
金融工程,数学算法