本帖最后由 TSC999 于 2017-5-1 20:28 编辑
谢谢各位大神的回复！让我耳目一新！9# 楼的那个程序很好。我原先写的程序是：
f = 1; f = 2; f = 4;
f := f + f + f;
f
这个程序看似正确，实际运行奇慢，不知何故？ 请高手指点。
我用 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 发表于 2017-5-1 20:36
程序巨慢是因为递归调用没有优化过，反复重复计算导致指数复杂度。而这题正常递推就可以得到线性复杂度，效 ...
f = 1; f = 2; f = 4;
f := f + f + f;
f // Timing
上面这个递归程序，计算 30 个台阶时用了 23 秒多：{23.478151,53798080}，我想起来了，好像是程序中少了保留中间计算数据的命令。这是一本书里讲的，当时没有理解是啥意思。如何增加保留中间数据的语句？我早忘了。
TSC999 发表于 2017-5-1 20:02
谢谢各位大神的回复！让我耳目一新！9# 楼的那个程序很好。我原先写的程序是：
f = 1; f = 2; f[ ...
慢的原因是因为每次都重新计算之前的结果。
这个可以通过存储而避免（俗称动态规划，以空间换时间）。最终复杂度如mathe所言，是线性的。快速的版本如下（不到1秒就出结果）：
f=1;f=2;f=4;
Table[{i+3,f=f+f+f},{i,1,200}]
或者
f = 1; f = 2; f = 4; n = 200;
Do = f + f + f, {i, n - 3}]; f
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$
wayne 发表于 2017-5-1 21:13
慢的原因是因为每次都重新计算之前的结果。
这个可以通过存储而避免（俗称动态规划，以空间换时间）。 ...
f = 1; f = 2; f = 4;
f := f = f + f + f;
f
查了下教程，按上面写即可保留中间计算结果。算出 f只须一瞬间。
mathe 发表于 2017-5-1 21:15
直接用特征多项式在多项式环上也可以快速计算
我们知道这个特征多项式为$x^3-x^2-x-1=0$
它对应有三 ...
(*小学奥数:有 m 级楼梯，每次可上1级、2级或3级，有几种走法？*)
Clear["Global`*"];(*Clear all variables*)
a={{1,1,1},{1,0,0},{0,1,0}};(*乘法矩阵*)
n=2000000;(*要计算的第几项*)
vector={{4},{2},{1}};(*初始值列向量*)
b=Dot,vector];(*矩阵幂乘法乘以列向量*)
b[](*最后求出来的值*)
mathematica 一两秒钟就给出了答案
mathematica 发表于 2017-5-2 13:19
mathematica 一两秒钟就给出了答案
当项目特别巨大的时候,必须采用我的办法!
否则应该没办法计算!或者计算一定会失败!
mathematica 发表于 2017-5-2 13:23
当项目特别巨大的时候,必须采用我的办法!
否则应该没办法计算!或者计算一定会失败!
那可未必. 我依然用 线性复杂度不停的递推(显然弱于对数级别的复杂度.), 但也不用花太长的时间.
只是此时的我没必要存储前面的200w个结果.我只需存储最近的两个值,方便 用来递推即可,代码如下:
Last], #[], Total[#]} &, {1, 2, 4}, 2000000 - 3]]
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……\)
土法炼钢,好办法,对于小学生容易明白