1
Rojey 2013-12-25 04:04:06 +08:00 1
递归,循环太多,循环套递归,递归套循环。能不慢么。
|
2
casparchen 2013-12-25 04:17:09 +08:00 1
远大于2的60次方次计算,30S就能出结果?不会吧。
能出结果已经很不错了。 |
3
skyangel3 2013-12-25 04:55:43 +08:00 via iPhone
60的fibonnaci sequence 运算30s 在php可以出结果。你的机器已经很牛了
|
5
wizardoz 2013-12-25 09:17:05 +08:00 1
你用的这个算法是算法导论上用来做反面教材的。
|
6
justfindu 2013-12-25 09:20:06 +08:00
这递归到死了吧
|
7
kennedy32 OP |
9
ccidcce32167 2013-12-25 09:38:14 +08:00
建议你用银河或深蓝来跑这个程序
|
10
luoyou1014 2013-12-25 09:39:46 +08:00
@kennedy32
改用循环写菲波纳锲算法 |
11
kennedy32 OP @luoyou1014 可以把一楼的代码改写一下么??
|
13
Keita1314 2013-12-25 10:18:51 +08:00 1
|
14
luoyou1014 2013-12-25 10:19:49 +08:00 1
@kennedy32
<?php function tuzi($x){ $sum = 0; $first=0; $second=1; for($i=0;$i<$x;$i++){ $sum = $first + $second; $first = $second; $second = $sum; } return $sum; } function testtuzi($n){ for ($i=0;$i<=$n;$i++){ echo "兔子在".$i."月的数目是".tuzi($i)."<br/>"; } } testtuzi(60); |
15
levn 2013-12-25 10:25:29 +08:00 1
|
16
TMBest 2013-12-25 10:30:00 +08:00 1
算法概论第一章吧,就在讲fib的各种算法,更快的算法是用矩阵。最快的是这货:
long int fib(unsigned long int n) { return lround((pow(0.5 + 0.5 * sqrt(5.0), n) - pow(0.5 - 0.5 * sqrt(5.0), n)) / sqrt(5.0)); } 参考:http://www.evanmiller.org/mathematical-hacker.html#HN_Repost |
17
tonitech 2013-12-25 10:40:00 +08:00 1
return tuzi($x-1)+tuzi($x-2);
这句话让你的代码变成了一个庞大的2叉树。。。n进去就是2的n-1次方! |
18
Golevka 2013-12-25 10:43:05 +08:00
因为这种二阶线性递归式直接写出来的话复杂度是exponential time的, 如果一定要递归的话可以用memoization. 所以说那些妄想速成码农就应该尽早砍掉重练, 回去撸一撸SICP和lambda calculus就知道踏实了.
ref: http://mitpress.mit.edu/sicp/full-text/sicp/book/node16.html |
21
anheiyouxia 2013-12-25 11:10:04 +08:00 1
|
22
flyaway 2013-12-25 11:15:23 +08:00
斐波拉契数列,递归的方法存在太多的overlapping,大量重复计算,降低了效率
|
26
kennedy32 OP @luoyou1014 谢谢
|
27
baiyunheitu 2013-12-25 12:05:18 +08:00
递归的复杂度不太乐观。
|
28
c742435 2013-12-25 12:14:16 +08:00
你用一个数组存储计算结果就可以了。算法不用改。
|
29
kuye 2013-12-25 12:35:18 +08:00 1
一种很肤浅的作法:
function tuzi($x){ static $result=array(); if(isset($result[$x])){ return $result[$x]; } if($x == 0 || $x == 1){ $r= 1; }else{ $r= tuzi($x-1)+tuzi($x-2); } $result[$x]=$r; return $r; } function testtuzi($n){ for ($i=0;$i<=$n;$i++){ echo "兔子在".$i."月的数目是".tuzi($i)."<br/>"; } } testtuzi(60); |
30
kevinroot 2013-12-25 13:29:24 +08:00
PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND
14896 root 25 0 302m 9.9m 6948 R 100.0 0.5 1:07.71 php tuzi.php php tuzi.php 11870.42s user 4.86s system 99% cpu 3:18:38.25 total 才跑到46 |
31
dorentus 2013-12-25 14:53:49 +08:00 2
回答楼主的问题:
tuzi($x) 这个函数,里面用到了前两次的计算结果 tuzi($x-1) 和 tuzi($x-2) 但是,每次计算的结果并没有保存在什么地方,每次都是从头开始重新计算的 例如:要计算 tuzi(4), >>>> 需要先计算 tuzi(3) 和 tuzi(2),分解为: >>>>>>>> 计算 tuzi(3):需要先计算 tuzi(2) 和 tuzi(1) >>>>>>>>>> 计算 tuzi(2):需要先计算 tuzi(1) 和 tuzi(0) >>>>>>>>>>>> 计算 tuzi(1) 得 1 >>>>>>>>>>>> 计算 tuzi(0) 得 1 >>>>>>>>>> 计算 tuzi(1) 得 1 >>>>>>>> 计算 tuzi(2):需要先计算 tuzi(1) 和 tuzi(0) >>>>>>>>>> 计算 tuzi(1) 得 1 >>>>>>>>>> 计算 tuzi(0) 得 1 注意上面每一步计算都是独立的(因为之前的结果并没有保存起来供以后使用),比如 tuzi(2) 就分别计算了两次。 然后,比如 testtuzi 的循环里面,下一步假如开始要计算 tuzi(5),需要计算 tuzi(4) 和 tuzi(3),然后虽然上次循环里面 tuzi(4) 和 tuzi(3) 其实已经都算过了,但是不行,这一次里面还是得重新从头开始算。 @kuye 的方法是拿空间换时间的方法(如果我对 PHP 的 static 没理解错的话),拿很少的空间(那个 static array)保存了每次 tuzi($x) 计算的结果,大大提高了后面计算的速度。 |
34
vibbow 2013-12-25 18:17:15 +08:00
能30s跑完这个代码的电脑都是神级的电脑了...
我的电脑还在慢慢跑,我看多久能跑完... |
35
pljhonglu 2013-12-25 18:37:35 +08:00
其实 LZ 是来秀电脑配置的。。。
|
36
hourui 2013-12-25 19:25:18 +08:00
楼上正解...
|
38
faceair 2013-12-25 20:36:04 +08:00
|
39
kurtis 2013-12-25 22:54:37 +08:00
@dorentus
看到现在,只有你got point 这个问题,本质就是应该拿空间换时间。 有张表记录下每次计算的结果作为缓存,以后不用每次计算就可以了。 这个是大学作业吗?好像很久很久以前有人讨论过这个问题了, |
40
TheJuli 2013-12-25 23:01:31 +08:00
用超算平台跑一遍试试
|
41
tonic 2013-12-25 23:21:22 +08:00
可以改成尾递归的... 或者直接改迭代
|
44
wizardoz 2013-12-26 09:19:32 +08:00
@kennedy32 正确的应该是从底向上,从n = 1 累加到n = x。所以问题不在于用了递归调用,而是在于选了一种有很多冗余计算的算法。
|
46
huafang 2014-01-14 22:30:38 +08:00
你函数还没定义好,就内部调用。。。
|