有这样一个游戏：
- 打开你的记事本，输入一个"0"。
- 你有10次行动回合
- 在每个回合中，你只能：①再输一个"0" ②把所有内容复制到剪贴板 ③粘贴
请问在10次行动回合结束后，你的记事本最多能有多少个"0"？
这是我很久以前试图用最快方法打出最多个字符时无聊想到的一个问题，其实还挺简单的（现在知道了答案以后的想法），但是当时想了十几分钟没想明白。之后又因为学习原因，就搁置了下来。现在寒假疫情在家里没事干，又想到了这个问题，便试图解决一下。
这个问题可以抽象成对于一个数字1，你每次能够[0]加一/[1]存取当前/[2]加上存取的数字，然后有10次机会。那这里直接记[0]为做了一次加一的操作，记[1]为存取当前数字的操作，以此类推。比如数字1在[0,0,0]之后变成了4（加了三次一），在[0,1,2]之后也变成了4（加一然后复制在加自身，相当于加一后翻倍）。
那我们先简单地试一下，开头肯定要多加一，积累底数，然后复制一次，多粘贴几次，到了一定程度后，再复制一下，多粘贴几次，嗯，直觉上是这样最大。那就[0,0,0,0,1,2,2,2,1,2]好了，最终结果是40，好像挺大了。那要是早点开始复制呢？比如[0,0,1,2,1,2,1,2,1,2]，最终结果是48。还有更好的方案吗？emmmm……多试几次，总能试出最佳结果的吧……？
确实，想到这里，我就想到动用python大法了。那怎么用代码去描述这个过程呢？肯定用一个变量a来存值。[0]好说，就变量a的值加一。[1]的话，再建一个变量b来存存取的值。[2]的话就是变量a加一下变量b里的值就好了。然后分别为[0] [1] [2]这三个操作定义一下相应的函数，放一个列表里，根据输入的值执行相应的操作就好了嘛。
def add():
global a
a=a+1
def copy():
global a,b
b=a
def paste():
global a,b
a=a+b
a=1
b=0
cmdlst=[add,copy,paste]
times=10
for i in range(times):
op=int(input("第"+str(i+1)+"次操作，输入0或1或2："))
cmdlst[op]()
print("结束，结果为",a)
随便跑了一种结果
第1次操作，输入0或1或2：0 第2次操作，输入0或1或2：0 第3次操作，输入0或1或2：1 第4次操作，输入0或1或2：2 第5次操作，输入0或1或2：1 第6次操作，输入0或1或2：2 第7次操作，输入0或1或2：1 第8次操作，输入0或1或2：2 第9次操作，输入0或1或2：1 第10次操作，输入0或1或2：2 结束，结果为 48
然后呢？自己对这个破程序玩一年？显然不可能，当然是让程序自己暴力枚举啦~反正也就3^10种情况，最后跑出来的结果是54，步骤为[0, 0, 1, 2, 1, 2, 2, 1, 2, 2]。
问题到这里，基本也告一段落，对于只有10次步骤的游戏来说，[0, 0, 1, 2, 1, 2, 2, 1, 2, 2]是最优解，最终会有54个"0"呢！好吧，也不是很多。至于为什么步骤是这样的，这里暂时不好说，需要把问题推广到有n次游戏步骤，再找找看规律好了。
既然前面python程序已经写好了，那就改改让他能算n次的吧。因为加了类来管理这个游戏，所以代码比较长，为了保证阅读体验我放文末了。跑到n=16的时候，结果为：
[0] [] 1 [1] [0] 2 [2] [0, 0] 3 [3] [0, 0, 0] 4 [4] [0, 0, 1, 2] 6 [5] [0, 0, 1, 2, 2] 9 [6] [0, 0, 0, 1, 2, 2] 12 [7] [0, 0, 1, 2, 1, 2, 2] 18 [8] [0, 0, 1, 2, 2, 1, 2, 2] 27 [9] [0, 0, 0, 1, 2, 2, 1, 2, 2] 36 [10] [0, 0, 1, 2, 1, 2, 2, 1, 2, 2] 54 [11] [0, 0, 1, 2, 2, 1, 2, 2, 1, 2, 2] 81 [12] [0, 0, 0, 1, 2, 2, 1, 2, 2, 1, 2, 2] 108 [13] [0, 0, 1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2] 162 [14] [0, 0, 1, 2, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2] 243 [15] [0, 0, 0, 1, 2, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2] 324 [16] [0, 0, 1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2] 486
可以看到，如果能进行16次操作，最终能有486个"0"！而且最优解的操作似乎前2~3次是[0]之后都是[1,2,2]循环。规律读者应该能自己归纳出来，这里就不写了（反正就是一开始[0,0]，然后从后往前堆[1,2,2]，然后还剩下一个操作位置就填[0]，剩下俩就填[1,2]）。
程序能帮我们也就那么多了，至少我们知道所有一般情况的最优解是啥样的了。可是为什么呢？一开始用[0]显然是最高效的，但之后的[1,2,2]为啥是最高效的？为什么不能是[1,2,2,2]，也不是[1,2]（倍增）。
首先，我们来考虑一开始[0]次数多少的问题。其实在本文的一开始就已经埋下伏笔了。因为很容易发现最初[0,0,0]的效率和[0,1,2]的效率是一样的，结果都是4。以这个为分界线，如果[0]操作执行两次和[1,2]比较，前者结果为3，后者结果为2；如果[0]操作多余3次，那效率显然不如[1,2]，因为起始值超过3后加二肯定没有倍增来得快。所以一开始执行两次[0]到3的效率是最高的。
那[1,2,2]为啥在之后局部最高效呢？首先，我们要清楚一件事情。[1]和[2]必然是[1]之后一串[2]，因为重复的[1]操作没有任何意义。那么我们只需要比较[1,2]和[1,2,2]和[1,2,2,....]的效率就好了。我们记f(n)为[1,(n-1)个2]的效率，并定义[1,2]的效率为1，那么很容易就能算出：f(2)=1 f(3)=9/8 f(4)=16/16 f(5)=25/32...用数学归纳法可以推导并证明出f(n)=n^2/2^n。那这个效率函数f(n)的最值在哪里，运用求导的知识便可以证明求出。当然，这里是离散的，也很容易就能看出从f(3)开始效率递减。因此,[1,2,2]的效率最高。
之后便是剩下一个或者两个操作次数的时候怎么办的问题了。其实这仅局限于前5步，枚举证明法即可。
至此，这个困惑了我许久的简单的小问题，就在这个寒假被解决了。以上便是笔者思考这个问题时候的思路过程，记录在这篇博客里，以作留念。
计算n次最优解的代码：（其中GameManager是可以互动着玩的，RobotPlay就是机器暴力枚举，最终只输出一种最优解）
class GameManager:
def __init__(self,times=10):
self.timesbak=times
self.num=1
self.record=0
self.times=times
self.cmd=[self.add,self.rec,self.pas]
def rec(self):
self.record=self.num
def add(self):
self.num+=1
def pas(self):
self.num+=self.record
def info(self):
return (self.num,self.record,self.times)
def show(self):
print("目前数字 {0}，目前记录 {1}，剩余次数 {2}".format(*self.info()))
def clear(self):
self.num=1
self.record=0
self.times=self.timesbak
def run(self):
while(self.times>0):
op=int(input("\n[0]加一 [1]复制 [2]粘贴:"))
self.cmd[op]()
self.times-=1
self.show()
print("-end-")
class RobotPlay(GameManager):
def toTri(self,num):
res=[0]*self.timesbak
now=num
for i in range(self.timesbak):
res[-i-1]=now%3
now=now//3
if(now==0):
break
return res
def run(self):
allres=[]
for i in range(3**self.times):
oplst=self.toTri(i)
for j in oplst:
self.cmd[j]()
#print(i+1,"of",3**self.times,":",self.info()[0],sep="")
allres.append(self.info()[0])
self.clear()
print("[{0}]".format(self.timesbak),self.toTri(allres.index(max(allres))),max(allres))
for i in range(20):
_rbp=RobotPlay(i)
_rbp.run()
