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

magixyu

浏览: 79765 次
性别:
来自: 青岛

最近访客更多访客>>

我爱爸爸妈妈

shenyongxianghihi

进退取舍

longzhou3

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

C/C++

算法 F#Python Ruby Go

闲逛时看了这篇文章
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

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

分享到：

诺基亚手机万能密码【转】 | Tomcat环境性能调优

2010-07-18 01:28
浏览 1089
评论(18)
论坛回复 / 浏览 (18 / 8127)
分类:编程语言
查看更多

18 楼 topcss 2011-05-16

wandou 写道

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

不知道是不是我对斐波那契的理解失误！？反正这样能打印出结果。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            for (int i = 0; i < 50; i++)
                Console.WriteLine(fib(i));
            Console.ReadLine();
        }

        public static ulong fib(int i)
        {
            ulong a, b;
            a = b = 1;

            for (int j = 0; j < i; j++)
                if (j % 2 == 0)
                    a += b;
                else
                    b += a;

            return a > b ? a : b;
        }
    }
}

17 楼 ggzwtj 2011-03-18

这个有什么意义？上矩阵乘法或者通项公式 :@

16 楼 gtssgtss 2011-01-04

cleanerje 写道

试试数学通项公式函数的
function y = Fib(n)
sr5 = sqrt(5);
y = uint32((((1 + sr5) / 2) ^ n - ((1 - sr5) / 2) ^ n) / sr5);
end

如果没有处理无理数运算的工具，一个sqrt(5)都会要人命的，精度问题难以解决

15 楼 cozilla 2010-12-06

斐波那契算法
是有O(LogN)的解法的
利用矩阵相乘

14 楼 yiyidog125 2010-10-20

没看出神奇在哪　这个不就是非递归的方式吗
循环里面就是swap两个数而已
a = a + b;
b = a - b;
a = a - b;
就可以swap a和b了

13 楼 wjywjy678 2010-07-30

public int fib(int n){
if(n==1)
return 0;
if(n==2)
return 1;
return fib(n-1)+fib(n-2);
}

12 楼 ywgoal 2010-07-28

闲得蛋痛啊

11 楼 cleanerje 2010-07-28

试试数学通项公式函数的
function y = Fib(n)
sr5 = sqrt(5);
y = uint32((((1 + sr5) / 2) ^ n - ((1 - sr5) / 2) ^ n) / sr5);
end

10 楼 infinite 2010-07-28

public long fib(int index) {
 long sum = 1, x = 1;
 if (index > 2) {
 for (int i = 0; i < index - 2; i++) {
 sum += x;
 x = sum - x;
 }
 }
 return sum;
 }

9 楼 robert 2010-07-28

clojure 代码：

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

取第一千个斐波那契数：

(nth fib 1000)

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

8 楼 mymGrubby 2010-07-27

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

7 楼 plghqr 2010-07-27

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

6 楼 lzyzizi 2010-07-26

python生成器

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

5 楼 Ulysses 2010-07-26

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

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

就行了吧

4 楼 nereusposeidon 2010-07-22

砖，还是要拍滴。: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)。
自己需要管理的栈就会越来越长。循环栈用起来也会更复杂。

3 楼 wandou 2010-07-21

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

2 楼 Elminster 2010-07-20

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

1 楼 hittyo 2010-07-19

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]).

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论