小学奥数:有 m 级楼梯，每次可上1级、2级或3级，有几种走法？

TSC999

谢谢各位大神的回复！让我耳目一新！9# 楼的那个程序很好。我原先写的程序是：
   f[1] = 1; f[2] = 2; f[3] = 4;
   f[n_] := f[n - 1] + f[n - 2] + f[n - 3];
   f[200]
   这个程序看似正确，实际运行奇慢，不知何故？ 请高手指点。

   我用 VB 写了一个程序，1 秒钟能得到正确答案：

f(4)=7
f(5)=13
f(6)=24
f(7)=44
f(8)=81
f(9)=149
f(10)=274
f(11)=504
f(12)=927
f(13)=1705
……………………………………………………
f(194)=1359175407124767917757607431924159972441903324662466
f(195)=2499913324337400808106962246767401835466214350404004
f(196)=4598057466637184726298996770212743687645654450636679
f(197)=8457146198099353452163566448904305495553772125703149
f(198)=15555116989073938986569525465884451018665640926743832
f(199)=28610320653810477165032088685001500201865067503083660
f(200)=52622583840983769603765180599790256716084480555530641
上面这个结果与 9# 楼的结果相同。

mathe

程序巨慢是因为递归调用没有优化过，反复重复计算导致指数复杂度。而这题正常递推就可以得到线性复杂度，效率已经很不错了。当然如果用公式或矩阵表达都能达到更高的效率

TSC999

mathe 发表于 2017-5-1 20:36
程序巨慢是因为递归调用没有优化过，反复重复计算导致指数复杂度。而这题正常递推就可以得到线性复杂度，效 ...

1. f[1] = 1; f[2] = 2; f[3] = 4;
   
2. f[n_] := f[n - 1] + f[n - 2] + f[n - 3];
   
3. f[30] // Timing

复制代码

上面这个递归程序，计算 30 个台阶时用了 23 秒多：{23.478151,53798080}，我想起来了，好像是程序中少了保留中间计算数据的命令。这是一本书里讲的，当时没有理解是啥意思。如何增加保留中间数据的语句？我早忘了。

wayne

TSC999 发表于 2017-5-1 20:02
谢谢各位大神的回复！让我耳目一新！9# 楼的那个程序很好。我原先写的程序是：
   f[1] = 1; f[2] = 2; f[ ...

慢的原因是因为每次都重新计算之前的结果。
这个可以通过存储而避免（俗称动态规划，以空间换时间）。最终复杂度如mathe所言，是线性的。快速的版本如下（不到1秒就出结果）：

1. f[1]=1;f[2]=2;f[3]=4;
   
2. Table[{i+3,f[i+3]=f[i+2]+f[i+1]+f[i]},{i,1,200}]

复制代码

或者

1. f[1] = 1; f[2] = 2; f[3] = 4; n = 200;
   
2. Do[f[i + 3] = f[i + 2] + f[i + 1] + f[i], {i, n - 3}]; f[n]

复制代码

mathe

mathematica 发表于 2017-5-1 15:22
对于特别大的n,可以使用类似于矩阵模幂的算法
{{1, 1, 1}, {1, 0, 0}, {0, 1, 0}}
就是这个矩阵,

直接用特征多项式在多项式环上也可以快速计算
我们知道这个特征多项式为$x^3-x^2-x-1=0$
它对应有三个根$r_1,r_2,r_3$,于是我们可以知道$r_1+r_2+r_3=1,r_1^2+r_2^2+r_3^2=3$
而根据前面的公式可以得出$a_n=\sum_{h=1}^3 {1-r_h}/{6r_h-4r_h^2}r_h^{n+1}$
由于$r_h^3-r_h^2-r_h-1=0$,我们可以将表达式${1-r}/{6r-4r^2}r^{n+1}$在模多项式$r^3-r^2-r-1$的环上进行计算。
而这一步可以通过在这个环上做模幂运算。
比如(21:10) gp > Mod((1-r)/(6*r-4*r^2)*r^201,r^3-r^2-r-1)
%9 = Mod(105815536640573855652705038607002134363681116623932051/11*r^2 + 177619156796624815634249136312145904871277962793801105/22*r + 115061489287191660577451535080408978900164636561426897/22, r^3 - r^2 - r - 1)
于是我们得出$a(200)=105815536640573855652705038607002134363681116623932051/11 xx (r_1^2+r_2^2+r_3^2)+177619156796624815634249136312145904871277962793801105/22 xx (r_1+r_2+r_3)+115061489287191660577451535080408978900164636561426897/22 xx 3$
得出$a(200)=52622583840983769603765180599790256716084480555530641$

TSC999

wayne 发表于 2017-5-1 21:13
慢的原因是因为每次都重新计算之前的结果。
这个可以通过存储而避免（俗称动态规划，以空间换时间）。 ...

1. f[1] = 1; f[2] = 2; f[3] = 4;
   
2. f[n_] := f[n] = f[n - 1] + f[n - 2] + f[n - 3];
   
3. f[200]

复制代码

查了下教程，按上面写即可保留中间计算结果。算出 f[200]只须一瞬间。

mathematica

mathe 发表于 2017-5-1 21:15
直接用特征多项式在多项式环上也可以快速计算
我们知道这个特征多项式为$x^3-x^2-x-1=0$
它对应有三 ...

1. (*小学奥数:有 m 级楼梯，每次可上1级、2级或3级，有几种走法？*)
   
2. Clear["Global`*"];(*Clear all variables*)
   
3. a={{1,1,1},{1,0,0},{0,1,0}};(*乘法矩阵*)
   
4. n=2000000;(*要计算的第几项*)
   
5. vector={{4},{2},{1}};(*初始值列向量*)
   
6. b=Dot[MatrixPower[a,n-3],vector];(*矩阵幂乘法乘以列向量*)
   
7. b[[1,1]](*最后求出来的值*)
   

复制代码

mathematica 一两秒钟就给出了答案

mathematica

mathematica 发表于 2017-5-2 13:19
mathematica 一两秒钟就给出了答案

当项目特别巨大的时候,必须采用我的办法!
否则应该没办法计算!或者计算一定会失败!

wayne

mathematica 发表于 2017-5-2 13:23
当项目特别巨大的时候,必须采用我的办法!
否则应该没办法计算!或者计算一定会失败!

那可未必. 我依然用 线性复杂度不停的递推(显然弱于对数级别的复杂度.), 但也不用花太长的时间.
只是此时的我没必要存储前面的200w个结果.  我只需存储最近的两个值,方便 用来递推即可,代码如下:

1. Last[Nest[{#[[2]], #[[3]], Total[#]} &, {1, 2, 4}, 2000000 - 3]]

复制代码

mathematica

aimisiyou 发表于 2017-5-1 11:27
\(f(m)=f(m-1)+f(m-2)+f(m-3),(m>=4) 其中f(1)=1,f(2)=2,f(3)=4,f(4)=7……\)

土法炼钢,好办法,对于小学生容易明白