方块计数二
|
注：本题是第114题的困难版。
用黑色方块和红色方块摆成一行，要求任意两个红色方块（长度可以不同）之间至少有一个黑色方块。
用F(m,n)表示红色方块的最短长度为m，行的总长度为n时的摆法总数。
例如，$F(3,29)=673135$，$F(3,30)=1089155$，亦即当$m=3$时，摆法总数首次超过一百万是在$n=30$时。
类似地，当$m=10$时有，$F(10,56)=880711$，$F(10,57)=1148904$，因而此时摆法总数首次超过一百万是在$n=57$时。
当$m=50$时令摆法总数首次超过一百万的n等于多少？
|
本题难度:
|
解答
|
解法与第114题完全相同，第令$a_n$为长度为n的摆法中以红色块结尾的摆法总数，$b_n$为长度为n的摆法中以黑色块结尾的摆法总数，并考虑在最后添加一块的情形，此时的递推公式为
$$a_{n+1}=a_{n}+b_{n-49} \quad b_{n+1}=a_{n}+b_n.$$
初值是
$$a_1=a_2=\ldots=a_{49}=0, a_{50}=1,\quad b_1=..=b_{50}=1.$$
递推得结果是$168$。
a=[0]*50+[1]
b=[0]+[1]*50
n=50
while a[n]+b[n] < 1000000:
n+=1
b.append(a[n-1]+b[n-1])
a.append(a[n-1]+b[n-50])
print n
|
| |
