当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

最爱fibonacci

发表于: 2011-11-15   作者:bookjovi   来源:转载   浏览次数:
摘要:   Fibonacci 的算法如下:   %% regular recursive fibonacci fib(0) -> 0; fib(1) -> 1; fib(N) -> fib(N-1) + fib(N-2).   这中简单算法用C或Java写也极其简单,但是绝对不要小看这个fibonacci,要记住fibonacci和fact

 

Fibonacci 的算法如下:

 

%% regular recursive fibonacci
fib(0) -> 0;
fib(1) -> 1;
fib(N) -> fib(N-1) + fib(N-2).

 

这中简单算法用C或Java写也极其简单,但是绝对不要小看这个fibonacci,要记住fibonacci和factorial可是FP的经典example(这两个本人老是容易混淆),如果面试官让你写出一个fibonacci实现,不限语言,而你却从容的写了上面的递归函数,那你就...

    上面的实现问题在于时间复杂度:O(2^N),单单这个数字有点抽象,试试运算fib(50),看看要多久(本人没有足够的耐心等了),这个小的数字50都要花费那么长的时间,那fib(10000)呢?

 

    下面函数语言FP的尾递归(tail recursion)就要上场了.

 

%% tail recursive fibonacci
fib2_tr(0, Result, _Next) -> Result;
fib2_tr(Iter, Result, Next) when Iter > 0 -> fib2_tr(Iter-1, Next, Result+Next).
fib2(N) -> fib2_tr(N, 0, 1).

 

    上面的程序时间复杂度为 O(N),算一下fib2(10000),立马出结果:

 

[root@localhost ~]# cat fibonacci.erl 
#!/usr/local/bin/escript


%% regular recursive fibonacci
fib(0) -> 0;
fib(1) -> 1;
fib(N) -> fib(N-1) + fib(N-2).


 
%% tail recursive fibonacci
fib2_tr(0, Result, _Next) -> Result;
fib2_tr(Iter, Result, Next) when Iter > 0 -> fib2_tr(Iter-1, Next, Result+Next).
fib2(N) -> fib2_tr(N, 0, 1).

main(Arg) ->
    io:format("~p~n", [fib2(10000)]).

[root@localhost ~]# time escript fibonacci.erl
fibonacci.erl:5: Warning: function fib/1 is unused
fibonacci.erl:16: Warning: variable 'Arg' is unused
33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875

real    0m0.472s
user    0m0.342s
sys     0m0.114s

    相比之下,用第一种算法计算fib(10000)估计要等到天荒地老了。 

 

    fibonacci的尾递归算法与普通递归算法的实质区别在于:尾递归是自底向上计算,而普通递归则是自顶向下计算,普通递归计算中包含了大量的重复运算。

 

    这里告诉我们tail recursion在FP中不仅仅是对stack grow的优化,更是一种算法思维的升华。

 

    在SICP一书中fib和fac讲的很透彻,不过SICP里讲的是scheme lisp,点这里

    lisp版的fib应该是这样:

 

(define (fib n)
  (define (fib-iter a b count)
    (if (= count 0)
      b
      (fib-iter (+ a b) a (- count 1))))
  (fib-iter 1 0 n))

 

    lisp版的fac应该是这样:

 

(define (factorial n)
  (define (iter product counter)
    (if (> counter n)
        product
        (iter (* counter product)
              (+ counter 1))))
  (iter 1 1))
 

其实我最爱的fibonacci不是用C/C++/Java写的,也不是用Erlang和scheme写的,而是haskell,haskell的fib真是大快人心啊:

 

Prelude> let fib = 1:1:(zipWith (+) fib $ tail fib) in fib
[1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711

 一行搞定,有人问用同是FP的Erlang或scheme可以写的这样精炼吗?我不知道,起码Erlang和scheme都不是lazy的。

 

haskell不仅用一行搞定fibonacci,也可以搞定prime素数:

 

Prelude> let sieve (p : xs) = p : sieve [x | x <- xs, x `mod` p > 0] in sieve [2..]
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109
 

haskell也可以一行搞定factorial:

Prelude> let fac n = product [1..n] in fac 50 
30414093201713378043612608166064768844377641568960512000000000000

 

 

 

最爱fibonacci

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
斐波纳契数列(Fibonacci Sequence),又称黄金分割数列。 意大利的数学家列昂那多·斐波那契在1202
斐波那契堆的结构较二项堆更松散,关键思想在于尽量延迟对堆的维护。 A Fibonacci heap is a collect
1.最爱你的女人,会在你晚上睡觉打呼噜的时候,轻轻吻吻你而不吵醒你,因为她知道你累了. 2.最爱你的
Another kind of Fibonacci Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/65536 K
问题描述 求Fibonacci数列的第n项。Fibonacci数列为1,1,2,3,5,... 解决思路 (1) 递归,指数级时间复
先看对数的性质,loga(b^c)=c*loga(b),loga(b*c)=loga(b)+loga(c); 假设给出一个数10234432,那么log1
想写这一篇文章已经很久了,只是一直拖到现在。 这里仅仅说Windows操作系统。 电脑重做系统对于使用
One thing you need to keep in mind about finding the time complexity of a recursive function
这是一个简单的fibonacciheap样图。 //斐波那契堆. #include <iostream> #include <type_t
距离 RIM 公司发售平板电脑 PlayBook 已经有好几个月了。还记得 4 月 19 号上市之初,主流媒体和博
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号