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

TSC999

小学五年级奥数问题：
从一层到达二层的楼梯共有 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 级台阶。问：小明从坡底上到坡顶，共有几种走法？

mathe

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$
而本题结果为$[u*r^{n+1}]$
比如对于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 = [1.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 + 0.E-211*I, 1.8392867552141611325518525646532866004241787460975922467787586394042032220819664257384354194283070141419798268592409741641784507465074369438315458204995137962496555396446136661215402779726781189410412 + 0.E-211*I, -0.41964337760708056627592628232664330021208937304879612338937931970210161104098321286921770971415350707098991342962048708208922537325371847191577291024975689812482776982230683306077013898633905947052061 - 0.60629072920719936925934219702802300294957066838642171221489968631886827528114566203132793037940234098292626876971223625418176179406992185592933810251810152309956472500321717855391200038694799281665007*I, -0.41964337760708056627592628232664330021208937304879612338937931970210161104098321286921770971415350707098991342962048708208922537325371847191577291024975689812482776982230683306077013898633905947052061 + 0.60629072920719936925934219702802300294957066838642171221489968631886827528114566203132793037940234098292626876971223625418176179406992185592933810251810152309956472500321717855391200038694799281665007*I]~
(09:23) gp > r=real(%[2])
%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

aimisiyou

\(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……\)

wayne

Mathematica代码跑一下。得到公式如下：

1. RSolveValue[{a[n] == a[n - 1] + a[n - 2] + a[n - 3], a[1] == 1,  a[2] == 2, a[3] == 4}, a[n], n]

复制代码

然后代值得到，跟mathe完全一样

In[16]:= Round[Root[-1-#1-#1^2+#1^3&,1]^n Root[-1+12 #1-44 #1^2+44 #1^3&,1]/.n->200]
Out[16]= 52622583840983769603765180599790256716084480555530641
In[17]:= Round[Root[-1-#1-#1^2+#1^3&,1]^n Root[-1+12 #1-44 #1^2+44 #1^3&,1]/.n->12]
Out[17]= 927

aimisiyou

math_humanbeing 发表于 2017-5-1 11:49
我看了半天，发现没人提到递推公式可以通过生成函数写成通项形式

如果你不嫌麻烦，可以利用生成函数把通项公式写出来。https://www.felix021.com/blog/read.php?2111

zeroieme

对于小学生，递推公式已经足够好。生成函数是大学程度。

mathe

我给的链接32楼已经包含通项公式形式了，用方程的根表示对应系数

mathematica

1. RecurrenceTable[{a[n]==a[n-1]+a[n-2]+a[n-3],a[1]==1,a[2]==2,a[3]==4},a,{n,1,200}]

复制代码

mathematica

mathematica 发表于 2017-5-1 15:05

RSolve[{a[n] == a[n - 1] + a[n - 2] + a[n - 3], a[1] == 1, a[2] == 2,  a[3] == 4}, a[n], n]
{{a[n] ->
   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

mathematica

对于特别大的n,可以使用类似于矩阵模幂的算法
{{1, 1, 1}, {1, 0, 0}, {0, 1, 0}}
就是这个矩阵,
除此之外,应该没有更好的计算的快速并且精确的办法