闲来无聊，改写斐波那契算法

闲逛时看了这篇文章
http://www.dnbcw.com/biancheng/hanshu/fpbs77602.html
作者优化后用长度为3的数组求解斐波那契，其实长度为2就足够了，上代码。。。

int fib(int n)
{
    int f[2] = {0, 1};
    int i = 2;
    for(i=2;i<=n;i++) {
       f[0] = f[0] + f[1];
       f[0] = f[0] + f[1];
       f[1] = f[0] - f[1];
       f[0] = f[0] - f[1];
    }

    return f[1];
}

Ruby 的代码就更简单了

def fib2(n)
    a=[0,1]
    2.upto(n) do
        a[0], a[1] = a[1], a[0]+a[1]
    end
    return a[1]
end

纯属好玩，请勿拍砖。。。。

FP代码:

go(N) -> go(N,0,1,[1,0]).
go(N,_,N2,L) when N2>=N -> L;
go(N,N1,N2,L) ->
New=N1+N2,
go(N-1,N2,New,[New|L]).

复杂度不减，数组长度是 3 而是 2 有个毛关系 ……

请运行f(1000),一秒钟能算出来的算法才算合格。

砖，还是要拍滴。:D

开个玩笑。

链接里给出的代码还是很有意思的。
里面用到了循环栈。F[i%3]=F[(i-1)%3]+F[(i-2)%3];
降低了空间复杂度。
楼主给出的代码也不错，也是循环栈。


从时间复杂度方面深想一下。这种循环做法，只不过是用自己管理的栈（就是那个数组）代替了递归算法中的运行栈，还不如直接用递归算法呢，写起来简单，时间复杂度也一样。

当公式复杂起来的时候， f(n) = f(n-1) + f(n-2) + f(n-3) ....+ f(n - m)。
自己需要管理的栈就会越来越长。循环栈用起来也会更复杂。

有点意思。
不过楼主那循环体里那四行代码我看着比较奇怪。
其实就是有两个数a,b 最后的结果为a=a+b,b=a,return a;
所以

f[1]=f[0]+f[1];
f[0]=f[1]-f[0];

就行了吧

python生成器

def fab(n):
    f1,f2 = 0 ,1
    for i in xrange(n):
            yield f2
            f1,f2 = f2,f1+f2

package com.test;

import java.math.BigDecimal;

public class Fbbs {
public static void main(String[] args) {
long begTime=System.currentTimeMillis();
Fbbs that=new Fbbs( new BigDecimal("1000") );
System.out.println( that.Fbfunction() );
long endTime=System.currentTimeMillis();
System.out.println( "Times=" + (endTime -begTime) + "ms");
}

private BigDecimal n;

public Fbbs(){}

public Fbbs(BigDecimal n){
this.n=n;
}

public BigDecimal Fbfunction(){
BigDecimal f[]={ new BigDecimal("0"), new BigDecimal("1"), new BigDecimal("1")};

for(int i=2;i<n.intValue();i++){
f[2]=f[0].add( f[1] );
f[0]=f[1];
f[1]=f[2];
}

return f[2];
}

public BigDecimal getN() {
return n;
}

public void setN(BigDecimal n) {
this.n = n;
}
}

1000的结果以及时间：
26863810024485359386146727202142923967616609318986952340123175997617981700247881689338369654483356564191827856161443356312976673642210350324634850410377680367334151172899169723197082763985615764450078474174626
Times=31ms

用BigInteger 跑plghqr的算法，10000的结果19066427ns跑完。
结果：
20793608237133498072112648988642836825087036094015903119682945866528501423455686648927456034305226515591757343297190158010624794267250973176133810179902738038231789748346235556483191431591924532394420028067810320408724414693462849062668387083308048250920654493340878733226377580847446324873797603734794648258113858631550404081017260381202919943892370942852601647398213554479081823593715429566945149312993664846779090437799284773675379284270660175134664833266377698642012106891355791141872776934080803504956794094648292880566056364718187662668970758537383352677420835574155945658542003634765324541006121012446785689171494803262408602693091211601973938229446636049901531963286159699077880427720289235539329671877182915643419079186525118678856821600897520171070499437657067342400871083908811800976259727431820539554256869460815355918458253398234382360435762759823179896116748424269545924633204614137992850814352018738480923581553988990897151469406131695614497783720743461373756218685106856826090696339815490921253714537241866911604250597353747823733268178182198509240226955826416016690084749816072843582488613184829905383150180047844353751554201573833105521980998123833253261228689824051777846588461079790807828367132384798451794011076569057522158680378961532160858387223882974380483931929541222100800313580688585002598879566463221427820448492565073106595808837401648996423563386109782045634122467872921845606409174360635618216883812562321664442822952537577492715365321134204530686742435454505103269768144370118494906390254934942358904031509877369722437053383165360388595116980245927935225901537634925654872380877183008301074569444002426436414756905094535072804764684492105680024739914490555904391369218696387092918189246157103450387050229300603241611410707453960080170928277951834763216705242485820801423866526633816082921442883095463259080471819329201710147828025221385656340207489796317663278872207607791034431700112753558813478888727503825389066823098683355695718137867882982111710796422706778536913192342733364556727928018953989153106047379741280794091639429908796650294603536651238230626

clojure 代码：

(def fib (lazy-cat [0 1] (map + fib (rest fib))))

取第一千个斐波那契数：

(nth fib 1000)

在我的电脑上用时 4.936ms :-)
换成取第10000个，用时 28.293ms