数学中国

 找回密码
 注册
搜索
热搜: 活动 交友 discuz
查看: 7993|回复: 41

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

[复制链接]
发表于 2017-4-30 19:53 | 显示全部楼层 |阅读模式
小学五年级奥数问题:
从一层到达二层的楼梯共有 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 级台阶。问:小明从坡底上到坡顶,共有几种走法?
 楼主| 发表于 2017-5-1 09:18 | 显示全部楼层
本帖最后由 天山草 于 2017-5-2 07:16 编辑

用电脑算,12 阶楼梯算了一瞬间。

In[4]:=

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

Out[6]= {0., 927}

但是 30 阶楼梯算了 23.4 秒。

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

Out[3]= {23.415750,53798080}

200阶的话,还不算到明天?貌似没有啥好算法,老老实实的递归,用电脑算也很慢。

后来查了一下 mathematica 教程,说是上面这个程序 “没有寄存中间计算结果” 而导致慢,解决方法很简单,在程序中加几个字就行了:

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

给出 f[200] 只须一瞬间。


发表于 2017-5-1 10:39 | 显示全部楼层
这种上台阶问题好像是斐波纳契数数列.
发表于 2017-5-1 10:47 | 显示全部楼层
本帖最后由 luyuanhong 于 2017-5-1 21:02 编辑

  已知 a(1)=1 ,a(2)=2 ,a(3)=4 ,a(n)=a(n-1)+a(n-2)+a(n-3) ,求 a(12) 。

  对应于递推公式 a(n)=a(n-1)+a(n-2)+a(n-3) ,有特征方程 x^3=x^2+x+1 。

    解特征方程,可以求得三个特征根(精确表达式太繁,下面只写出近似值):

    x1 = 1.839286755 ,

    x2 = -0.4196433776 + 0.6062907292 i ,

    x3 = -0.4196433776 - 0.6062907292 i 。

    a(n) 可表示为 a(n) = A x1^n + B x2^n + C x3^n 。

    再根据初始条件,可列出方程组:

    A x1 + B x2 + C x3 = a(1) = 1 ,

    A x1^2 + B x2^2 + C x3^2 = a(2) = 2 ,  

    A x1^3 + B x2^3 + C x3^3 = a(3) = 4 。

    可解得(精确表达式太繁,下面只写出近似值):

    A = 0.6184199223 ,

    B = 0.1907900388 - 0.01870058232 i ,

    C = 0.1907900388 + 0.01870058232 i 。

    在通项公式 a(n) = A x1^n + B x2^n + C x3^n ,n=1,2,3,… 中,

    令 n=1 ,可得 a(1) = 1 ;

    令 n=2 ,可得 a(2) = 2 ;

    令 n=3 ,可得 a(3) = 4 ;

    令 n=12 ,可得 a(12) = 927 ;

    令 n=30 ,可得 a(30) = 53798080 ;

    令 n=200 ,可得 a(200) = 5.262258×10^52  。
发表于 2017-5-1 11:00 | 显示全部楼层
本帖最后由 王守恩 于 2017-5-1 19:50 编辑

这是道好题!我们先把题目扩大,解数可能容易些。

每次级数  共1级楼梯  共2级楼梯  共3级楼梯  共4级楼梯  共5级楼梯   共6级楼梯    共7级楼梯     共8级楼梯      共9级楼梯   
最多1级         1             1          1=1×2-1    1=1×2-1    1=1×2-1     1=1×2-1      1=1×2-1       1=1×2-1        1=1×2-1
最多2级         1             2              3          5=3×2-1    8=5×2-2    13=8×2-3    21=13×2-5    34=21×2-8     55=34×2-13
最多3级         1             2              4              7         13=7×2-1   24=13×2-2   44=24×2-4    81=44×2-7   149=81×2-13
最多4级         1             2              4              8              15        29=15×2-1   56=29×2-2   108=56×2-4   208=108×2-8
最多5级         1             2              4              8              16              31         61=31×2-1   120=61×2-2   236=120×2-4
最多6级         1             2              4              8              16              32              63          125=63×2-1   248=125×2-2
最多7级         1             2              4              8              16              32              64                127         253=127×2-1

最多A级  共n级楼梯

问题:解数有规律吗?
提示:2×a(n)=a(n+1)+a(n - A),每个解数都是另外两个解数的平均数。
 楼主| 发表于 2017-5-1 19:48 | 显示全部楼层
哈哈哈哈……,谢谢陆教授的精彩解答。原来这道题的实质远远超过小学生的能力,只是让小朋友初步建立一个递推概念而已。

第二个问题,用 mathematica 编写的那个小程序,可能存在大毛病,虽然运行结果正确,但是速度奇慢。我认为这是不正常的。下面是用 VB 语言写的程序的计算结果,200 个台阶,只运行 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(14)=3136
f(15)=5768
f(16)=10609
f(17)=19513
f(18)=35890
f(19)=66012
f(20)=121415
f(21)=223317
f(22)=410744
f(23)=755476
f(24)=1389537
f(25)=2555757
f(26)=4700770
f(27)=8646064
f(28)=15902591
f(29)=29249425
f(30)=53798080
f(31)=98950096
f(32)=181997601
f(33)=334745777
f(34)=615693474
f(35)=1132436852
f(36)=2082876103
f(37)=3831006429
f(38)=7046319384
f(39)=12960201916
f(40)=23837527729
f(41)=43844049029
f(42)=80641778674
f(43)=148323355432
f(44)=272809183135
f(45)=501774317241
f(46)=922906855808
f(47)=1697490356184
f(48)=3122171529233
f(49)=5742568741225
f(50)=10562230626642
f(51)=19426970897100
f(52)=35731770264967
f(53)=65720971788709
f(54)=120879712950776
f(55)=222332455004452
f(56)=408933139743937
f(57)=752145307699165
f(58)=1383410902447554
f(59)=2544489349890656
f(60)=4680045560037375
f(61)=8607945812375585
f(62)=15832480722303616
f(63)=29120472094716576
f(64)=53560898629395777
f(65)=98513851446415969
f(66)=181195222170528322
f(67)=333269972246340068
f(68)=612979045863284359
f(69)=1127444240280152749
f(70)=2073693258389777176
f(71)=3814116544533214284
f(72)=7015254043203144209
f(73)=12903063846126135669
f(74)=23732434433862494162
f(75)=43650752323191774040
f(76)=80286250603180403871
f(77)=147669437360234672073
f(78)=271606440286606849984
f(79)=499562128250021925928
f(80)=918838005896863447985
f(81)=1690006574433492223897
f(82)=3108406708580377597810
f(83)=5717251288910733269692
f(84)=10515664571924603091399
f(85)=19341322569415713958901
f(86)=35574238430251050319992
f(87)=65431225571591367370292
f(88)=120346786571258131649185
f(89)=221352250573100549339469
f(90)=407130262715950048358946
f(91)=748829299860308729347600
f(92)=1377311813149359327046015
f(93)=2533271375725618104752561
f(94)=4659412488735286161146176
f(95)=8569995677610263592944752
f(96)=15762679542071167858843489
f(97)=28992087708416717612934417
f(98)=53324762928098149064722658
f(99)=98079530178586034536500564
f(100)=180396380815100901214157639
f(101)=331800673921785084815380861
f(102)=610276584915472020566039064
f(103)=1122473639652358006595577564
f(104)=2064550898489615111976997489
f(105)=3797301123057445139138614117
f(106)=6984325661199418257711189170
f(107)=12846177682746478508826800776
f(108)=23627804467003341905676604063
f(109)=43458307810949238672214594009
f(110)=79932289960699059086717998848
f(111)=147018402238651639664609196920
f(112)=270409000010299937423541789777
f(113)=497359692209650636174868985545
f(114)=914787094458602213263019972242
f(115)=1682555786678552786861430747564
f(116)=3094702573346805636299319705351
f(117)=5692045454483960636423770425157
f(118)=10469303814509319059584520878072
f(119)=19256051842340085332307611008580
f(120)=35417401111333365028315902311809
f(121)=65142756768182769420208034198461
f(122)=119816209721856219780831547518850
f(123)=220376367601372354229355484029120
f(124)=405335334091411343430395065746431
f(125)=745527911414639917440582097294401
f(126)=1371239613107423615100332647069952
f(127)=2522102858613474875971309810110784
f(128)=4638870383135538408512224554475137
f(129)=8532212854856436899583867011655873
f(130)=15693186096605450184067401376241794
f(131)=28864269334597425492163492942372804
f(132)=53089668286059312575814761330270471
f(133)=97647123717262188252045655648885069
f(134)=179601061337918926320023909921528344
f(135)=330337853341240427147884326900683884
f(136)=607586038396421541719953892471097297
f(137)=1117524953075580895187862129293309525
f(138)=2055448844813242864055700348665090706
f(139)=3780559836285245300963516370429497528
f(140)=6953533634174069060207078848387897759
f(141)=12789542315272557225226295567482485993
f(142)=23523635785731871586396890786299881280
f(143)=43266711735178497871830265202170265032
f(144)=79579889836182926683453451555952632305
f(145)=146370237357093296141680607544422778617
f(146)=269216838928454720696964324302545675954
f(147)=495166966121730943522098383402921086876
f(148)=910754042407278960360743315249889541447
f(149)=1675137847457464624579806022955356304277
f(150)=3081058855986474528462647721608166932600
f(151)=5666950745851218113403197059813412778324
f(152)=10423147449295157266445650804376936015201
f(153)=19171157051132849908311495585798515726125
f(154)=35261255246279225288160343449988864519650
f(155)=64855559746707232462917489840164316260976
f(156)=119287972044119307659389328875951696506751
f(157)=219404787037105765410467162166104877287377
f(158)=403548318827932305532773980882220890055104
f(159)=742241077909157378602630471924277463849232
f(160)=1365194183774195449545871614972603231191713
f(161)=2510983580511285133681276067779101585096049
f(162)=4618418842194637961829778154675982280136994
f(163)=8494596606480118545056925837427687096424756
f(164)=15623999029186041640567980059882770961657799
f(165)=28737014477860798147454684051986440338219549
f(166)=52855610113526958333079589949296898396302104
f(167)=97216623620573798121102254061166109696179452
f(168)=178809248211961554601636528062449448430701105
f(169)=328881481946062311055818372072912456523182661
f(170)=604907353778597663778557154196528014650063218
f(171)=1112598083936621529436012054331889919603946984
f(172)=2046386919661281504270387580601330390777192863
f(173)=3763892357376500697484956789129748325031203065
f(174)=6922877360974403731191356424062968635412342912
f(175)=12733156638012185932946700793794047351220738840
f(176)=23419926356363090361623014006986764311664284817
f(177)=43075960355349680025761071224843780298297366569
f(178)=79229043349724956320330786025624591961182390226
f(179)=145724930061437726707714871257455136571144041612
f(180)=268029933766512363053806728507923508830623798407
f(181)=492983907177675046081852385791003237362950230245
f(182)=906738771005625135843373985556381882764718070264
f(183)=1667752611949812544979033099855308628958292098916
f(184)=3067475290133112726904259471202693749085960399425
f(185)=5641966673088550407726666556614384260808970568605
f(186)=10377194575171475679609959127672386638853223066946
f(187)=19086636538393138814240885155489464648748154034976
f(188)=35105797786653164901577510839776235548410347670527
f(189)=64569628900217779395428355122938086836011724772449
f(190)=118762063225264083111246751118203787033170226477952
f(191)=218437489912135027408252617080918109417592298920928
f(192)=401769182037616889914927723322059983286774250171329
f(193)=738968735175016000434427091521181879737536775570209
f(194)=1359175407124767917757607431924159972441903324662466
f(195)=2499913324337400808106962246767401835466214350404004
f(196)=4598057466637184726298996770212743687645654450636679
f(197)=8457146198099353452163566448904305495553772125703149
f(198)=15555116989073938986569525465884451018665640926743832
f(199)=28610320653810477165032088685001500201865067503083660
f(200)=52622583840983769603765180599790256716084480555530641
回复 支持 1 反对 0

使用道具 举报

 楼主| 发表于 2017-5-1 21:56 | 显示全部楼层
想起程序慢的原因了,运行慢的程序是:

f[1] = 1; f[2] = 2; f[3] = 4;
f[n_] := f[n - 1] + f[n - 2] + f[n - 3];    (* 这句没有保留中间计算结果!*)
f[200]

慢的原因是电脑没有保留中间计算结果,解决方法是:

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

只须在 f[n_] := 的后面增加  f[n] 就行了。改进后的程序一瞬间即可求出结果!
 楼主| 发表于 2017-5-2 07:25 | 显示全部楼层
本帖最后由 luyuanhong 于 2017-5-2 12:20 编辑

源于陆教授那个解法,有网友给出了精确解的表达式,我是看不懂的,但是深感数学的博大精深和巨大魅力。

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x
发表于 2017-5-11 11:40 | 显示全部楼层
王守恩 发表于 2017-5-11 06:35
蔡老弟!找一找规律:
1,1,1,2,2,3,4,5,7,9,12,16,21,28,37,49,65,86,..........

1,1,1,2,2,3,4,5,7,9,12,16,21,28,37,49,65,86,..........
相当于有 m 级楼梯,每次可上2级 , 3级,有几种走法。
发表于 2017-5-12 05:46 | 显示全部楼层
蔡家雄 发表于 2017-5-2 05:48
这个级数究竟有多少个平方数?

这个级数是否有无穷多个素数?




这个方法就是用到了多项式模。应该可以推广到类似的线性递归关系。

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x
回复 支持 1 反对 0

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|手机版|小黑屋|数学中国 ( 京ICP备05040119号 )

GMT+8, 2024-3-29 09:48 , Processed in 0.092773 second(s), 16 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表