菲波纳奇算法困扰！

夜夜呆

这个菲波纳奇算法我卡死了...头都大了就是想不出来...!!

是这样的... 输出 0,1,1,2,3,5,8,13,21,34.............!
前两个数字之和是第三个数....
谁有好想法 给我体个醒...谢谢拉...!!

perryhg

不出10行就搞定了
http://www.cs.princeton.edu/intr ... Fibonacci.java.html

不过，这个算法使用了递归，代码少，但是效率并不高，目标数列很大的时候占内存很历害。计算菲波纳奇数列也是算法优化的一个研究方向，就像计算圆周率和阶乘一样，我还看见过一个用多线程并行处理来计算菲波纳奇数列的算法。

[ 本帖最后由 perryhg 于 2006-6-7 01:14 编辑 ]

Brevity

支持，递归很简洁，2楼的，多线程并行处理来计算菲波纳奇数列的算法能不能介绍学习下？

jakieyoung

x=0,y=1

loop:
    t=x+y
    x=y
    y=t
    put t to file
until t reaches max

这种办法不会占多少内存
可以将结果写入文件

这个很直观，但是效率也最差
fibonacci数列还有很多特点，利用这些特点，可以写出比较高效的程序

chouy

不支持递归,原因是:
1.把逻辑复杂化了, 而且还要处理前两个数的问题.
2.压栈也要耗内存! 如果你用算第10000000个数试试
如果只会用第N个数, 前面的数不用, 可以只用两数相加的办法.

夜夜呆

感谢老大.....感谢各位...!~
我还得仔细想想....!!
丫的数学真奇妙...!~

lsyong

用ruby吧。
def fibonacci(i)
    a, b = 0, 1
    i.times do a, b = b, a + b end
    a
end

perryhg

原帖由 Brevity 于 2006-6-7 09:41 发表
支持，递归很简洁，2楼的，多线程并行处理来计算菲波纳奇数列的算法能不能介绍学习下？

网上搜索一下，有很多的，我给个例子
http://gee.cs.oswego.edu/dl/clas ... t/taskDemo/Fib.java

Jade_King

呵呵，有个迭代算法，很快

wangjianEgg

连接怎么看不了啊！