小学奥数:有 m 级楼梯，每次可上1级、2级或3级，有几种走法？
小学五年级奥数问题：从一层到达二层的楼梯共有 12 级。小明每跨一步，可以 1 级，或是 2 级，或是 3 级楼梯。问：从一层上到二层，共有几种走法？
解：如果只有1级台阶，共有 a1=1 种走法。如果有2级台阶，则有 a2=2 种走法。如果有3级台阶，则3=1+1+1=1+2=2+1=3，有 a3=4 种走法。
如果有4级台阶，可以分三种情况讨论：
如果第一步跨1级，还剩3级，还有 a3=4 种走法；
如果第一步跨2级，还剩2级，还有 a2=2 种走法；
如果第一步跨3级，还剩1级，还有 a1=1 种走法。
因此， a4=a3+a2+a1=4+2+1=7种走法。
一般地，如果有 n 级台阶，则共有 an= a(n-1)+ a(n-2)+ a(n-3) 种走法。
于是， a6= a5+ a4+ a3=13+7+4=24； a7= a6+ a5+ a4=24+13+7=44； a8= a7+ a6+ a5=44+24+13=81；
a9= a8+ a7+ a6=81+44+24=149； a10= a9+ a8+ a7=149+81+44=274； a11= a10+ a9+ a8=274+149+81=504；
a12= a11+ a10+ a9=504+274+149=927。
所以本题的答案就是12级台阶共有927种走法。
但是，这种算法好吗？ 如果陕西华山某山坡有 200 级台阶，小明每跨一步，可以是 1 级，或是 2 级，或是 3 级台阶。问：小明从坡底上到坡顶，共有几种走法？ http://bbs.emath.ac.cn/thread-667-1-1.html
相当于连接中抛硬币出现连续三次正面问题，链接10楼是答案，32楼有比较完整的证明
于是我们可以得出$r$是方程$x^4-2*x^3+1=0$的唯一正实根，所以$r~=1.8392867552141611325518525646532866004$
而$u={1/r-1}/(6-4r)~=0.33622811699494109422536295401433241517$
而本题结果为$$
比如对于n=200,我们有
(09:20) gp > \p 200
realprecision = 211 significant digits (200 digits displayed)
(09:23) gp > polroots(x^4-2*x^3+1)
%16 = ~
(09:23) gp > r=real(%)
%17 = 1.8392867552141611325518525646532866004241787460975922467787586394042032220819664257384354194283070141419798268592409741641784507465074369438315458204995137962496555396446136661215402779726781189410412
(09:23) gp > u=(1/r-1)/(2*3-4*r)
%18 = 0.33622811699494109422536295401433241515792609002045928044370624854382953699108191745012092780622316616338926362955987496703412199134661722478534716979661323670287361659441554928881504561537151324472766
(09:23) gp > u*r^201
%19 = 52622583840983769603765180599790256716084480555530641.000000000000000000000000000050488436444247109886150152300565002103643993810898360662690792585747039575871588017088719052767932070560385117926578853 \(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……\)
Mathematica代码跑一下。得到公式如下：
RSolveValue[{a == a + a + a, a == 1,a == 2, a == 4}, a, n]
然后代值得到，跟mathe完全一样
In:= Round^n Root[-1+12 #1-44 #1^2+44 #1^3&,1]/.n->200]
Out= 52622583840983769603765180599790256716084480555530641
In:= Round^n Root[-1+12 #1-44 #1^2+44 #1^3&,1]/.n->12]
Out= 927 本帖最后由 aimisiyou 于 2017-5-1 12:25 编辑
math_humanbeing 发表于 2017-5-1 11:49
我看了半天，发现没人提到递推公式可以通过生成函数写成通项形式
如果你不嫌麻烦，可以利用生成函数把通项公式写出来。https://www.felix021.com/blog/read.php?2111 对于小学生，递推公式已经足够好。生成函数是大学程度。 我给的链接32楼已经包含通项公式形式了，用方程的根表示对应系数 RecurrenceTable[{a==a+a+a,a==1,a==2,a==4},a,{n,1,200}] mathematica 发表于 2017-5-1 15:05
RSolve[{a == a + a + a, a == 1, a == 2,a == 4}, a, n]
{{a ->
Root[-1 - #1 - #1^2 + #1^3 &, 1]^
n Root[-1 + 12 #1 - 44 #1^2 + 44 #1^3 &, 1] +
Root[-1 - #1 - #1^2 + #1^3 &, 3]^
n Root[-1 + 12 #1 - 44 #1^2 + 44 #1^3 &, 2] +
Root[-1 - #1 - #1^2 + #1^3 &, 2]^
n Root[-1 + 12 #1 - 44 #1^2 + 44 #1^3 &, 3]}}
近似地就取
Root[-1 - #1 - #1^2 + #1^3 &, 1]^n Root[-1 + 12 #1 - 44 #1^2 + 44 #1^3 &, 1]
N[%,20]
0.61841992231939255094533043807106162610558831061794*1.8392867552141611325518525646532866004241787460976^n 对于特别大的n,可以使用类似于矩阵模幂的算法
{{1, 1, 1}, {1, 0, 0}, {0, 1, 0}}
就是这个矩阵,
除此之外,应该没有更好的计算的快速并且精确的办法