找回密码
 欢迎注册
楼主: TSC999

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

[复制链接]
 楼主| 发表于 2017-5-1 20:02:22 | 显示全部楼层
本帖最后由 TSC999 于 2017-5-1 20:28 编辑

谢谢各位大神的回复!让我耳目一新!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# 楼的结果相同。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-5-1 20:36:15 来自手机 | 显示全部楼层
程序巨慢是因为递归调用没有优化过,反复重复计算导致指数复杂度。而这题正常递推就可以得到线性复杂度,效率已经很不错了。当然如果用公式或矩阵表达都能达到更高的效率
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2017-5-1 20:53:26 | 显示全部楼层
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},我想起来了,好像是程序中少了保留中间计算数据的命令。这是一本书里讲的,当时没有理解是啥意思。如何增加保留中间数据的语句?我早忘了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-5-1 21:13:23 | 显示全部楼层
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]
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-5-1 21:15:53 | 显示全部楼层
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$

点评

从时间上来说,我算了不到两秒出结果了,但是你的没,所以不可能没区别  发表于 2017-5-3 13:26
计算结果应该不会有问题。我的方法计算200w项也很快,本质上两种方法没有很大区别,可以相互转化  发表于 2017-5-2 16:30
我已经把第200w项的结果贴在了后面,你可以对比一下  发表于 2017-5-2 13:22
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2017-5-1 21:42:49 | 显示全部楼层
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]只须一瞬间。

点评

关键是矩阵乘法需要27次数字乘法,而两个二次多项式乘法需要9次数字乘法。所以矩阵比多项式方法应该慢3倍左右  发表于 2017-5-2 17:36
20,000,000项也就是数秒的时间。只是这时Pari/gp默认内存大小不够用,需要增加内存。  发表于 2017-5-2 16:47
200w项我已经算出来了,mathematica连输出估计不到两秒,你们可以尝试找更快的计算办法  发表于 2017-5-2 13:25
递推计算在我的电脑上用pari/gp要到200,000项才会感觉到延时,但是计算到2,000,000项就完全不行了。 而采用模r^3-r^2-r-1,需要将输入改为 Mod((1-r)/(6-4*r), r^3-r^2-r-1)*Mod(r,r^3-r^2-r-1)^2000000  发表于 2017-5-2 07:32
因为200很小,你可以试着计算更后面的,比如2000或20000项  发表于 2017-5-2 07:10
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-5-2 13:19:52 | 显示全部楼层
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 一两秒钟就给出了答案

点评

我给我这个回帖打一万分,点一万个赞!  发表于 2017-5-2 13:39
当项目特别巨大的时候,必须采用我的办法! 否则应该没办法计算!或者计算一定会失败!  发表于 2017-5-2 13:23
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-5-2 13:23:46 | 显示全部楼层
mathematica 发表于 2017-5-2 13:19
mathematica 一两秒钟就给出了答案

当项目特别巨大的时候,必须采用我的办法!
否则应该没办法计算!或者计算一定会失败!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-5-2 13:35:37 | 显示全部楼层
mathematica 发表于 2017-5-2 13:23
当项目特别巨大的时候,必须采用我的办法!
否则应该没办法计算!或者计算一定会失败!


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

点评

这个问题,关键还是算法的问题  发表于 2017-5-2 13:51
也许吧,用我的办法2秒不到就算出来了,我用你的代码,算了二三十秒还没出结果,我就关闭掉了  发表于 2017-5-2 13:46
在我的笔记本上上,需要等待57秒钟  发表于 2017-5-2 13:40
算了很长时间没算出来  发表于 2017-5-2 13:38
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-5-2 13:52:43 | 显示全部楼层
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……\)

土法炼钢,好办法,对于小学生容易明白
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 10:04 , Processed in 0.072878 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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