`
magixyu
  • 浏览: 79405 次
  • 性别: Icon_minigender_1
  • 来自: 青岛
社区版块
存档分类
最新评论

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

算法F#PythonRubyGo 
阅读更多
闲逛时看了这篇文章
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环境性能调优
评论
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  
<p><span style="">斐波那契算法</span></p>
<p>是有O(LogN)的解法的</p>
<p>利用矩阵相乘</p>
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]).
发表评论

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

相关推荐

    NDK例子之 斐波那契算法

    **NDK例子之 斐波那契算法** NDK（Native Development Kit）是Android平台提供的一种工具集，允许开发者使用C、C++等原生代码编写应用的一部分，以实现高性能计算或者利用硬件特性。在本示例中，我们将探讨如何使用...

    斐波那契多种算法优化

    总的来说，理解和优化斐波那契算法有助于提升我们的编程技巧，特别是在处理递归和复杂计算问题时。了解递归、迭代、动态规划和高级算法如矩阵快速幂，能够帮助我们更有效地解决问题，并在实际工作中发挥重要作用。

    Fibonacci数多种算法

    在编程中，我们通常会用不同的算法来实现斐波那契数列的计算，每种算法有其特定的时间复杂度和空间复杂度。以下是一些常见的斐波那契数列计算方法： 1. **递归法**： 递归是最直观的方法，但也是效率最低的。代码...

    斐波那契算法实现

    斐波那契算法实现主要涉及的是计算机编程中的一个经典数列问题——斐波那契数列。斐波那契数列是由两个初始项1（fold1）和1（fold2）开始，后续每一项都是前两项之和。用数学公式表示就是：F(n) = F(n-1) + F(n-2)，...

    算法设计实验报告之多种方法求解斐波那契数列

    在这个算法设计实验报告中，主要关注的是通过不同的方法求解斐波那契数列，这是一种经典的计算机科学问题。斐波那契数列是由0和1开始，后面的每一项数字是前面两项数字的和，通常表示为F(n)。实验的目标是实现四种...

    数据结构实验四实现Fibonacci检索算法

    【数据结构实验四实现Fibonacci检索算法】的实验旨在让学生深入理解和掌握不同的检索方法，特别是Fibonacci检索算法的实现。此实验涉及到的主要知识点包括： 1. **检索方法**：实验要求掌握不同检索方法的实现，这...

    斐波那契数列算法分析.doc

    "斐波那契数列算法分析" 斐波那契数列是一种非常经典的数学概念，它的应用非常广泛，包括算法设计、生物学、经济学等领域。斐波那契数列的定义是：每个数都是前两个数的和，从第三个数开始，每个数都是前面两个数的...

    斐波那契C程序 递归算法

    在压缩包中的"Fibonacci"文件可能包含了这个C程序的源代码，你可以打开查看并运行它来体验递归斐波那契函数的效果。理解并能熟练运用递归是每个程序员必备的技能，因为它不仅在解决斐波那契序列这类问题上发挥作用，...

    0.618法和fibonacci法matlab算法

    Fibonacci法也是一种在一维区间内查找函数极小值的方法，它利用斐波那契数列的特点来确定测试点的位置。 **MATLAB代码解析：** ```matlab function [x, T, j] = Fibonacci(F_1, a1, b1, l, e) ``` 这里定义了一个...

    实现Fibonacci检索算法

    总之，Fibonacci检索算法是数据结构中一种巧妙的查找技术，它通过利用Fibonacci数列的性质来减少平均查找次数，提高了在有序数组中查找效率。福建农林大学的这个实验旨在让学生熟练掌握这种算法，理解其工作原理，并...

    递归算法算斐波那契数列

    对于斐波那契数列的递归算法来说，其时间复杂度为 O(2^n)。这是因为递归树呈指数增长，并且存在大量的重复计算。 #### C语言实现递归斐波那契数列 以下是一个完整的C语言程序，用于计算并输出指定位置的斐波那契...

    经典斐波那契数列的算法实现教案.doc

    经典斐波那契数列的算法实现教案 在本教案中，我们将探讨经典斐波那契数列的算法实现，并将其与 FOR 循环构造相结合，培养学生的变通性思维能力和程序设计能力。 知识点1：FOR 循环构造 * FOR 循环是控制构造中...

    斐波那契数列的三种算法.doc

    这里，我们讨论了三种不同的算法来计算斐波那契数列的第 n 项。 **算法一：递归** 递归算法是最直观的方法，它直接根据斐波那契数列的定义进行计算。代码如下： ```c long int fibo(int n){ if(n==0) return 0; ...

    算法-数论- 斐波那契数列（Fibonacci）.rar

    - 在编码理论中，斐波那契数列出现在某些编码算法中，如Fibonacci编码。 - 在图形学中，斐波那契螺旋被用于创建自然和有机形状的模拟。 8. **数论上的性质**： - 斐波那契数的模p余数的规律（例如费马小定理和...

    java实现Fibonacci算法实例

    斐波那契（Fibonacci）算法是一种计算序列的算法，该序列由两个连续的整数相加得到，起始的两个数字通常是0和1。斐波那契序列在计算机科学中有广泛的应用，如在算法设计、数据分析以及优化问题中。在Java中，我们...

    算法与数据结构实验四 实现Fibonacci检索算法

    【Fibonacci检索算法】 Fibonacci检索算法是一种在有序数组中查找特定元素的高效算法，它基于Fibonacci数列的特性。Fibonacci数列由递推关系定义，f0=0, f1=1, fi=f(i-1)+f(i-2) (i≥2)，产生的数列是0, 1, 1, 2, 3...

    动态规划,分治算法,概率算法,模拟退火算法,搜索算法,贪婪算法,网上matlab,遗传算法,组合算法

    本篇文章将深入探讨标题和描述中提到的一些核心算法，包括动态规划、分治算法、概率算法、模拟退火算法、搜索算法、贪婪算法、在线MATLAB应用、遗传算法以及组合算法。 1. **动态规划**：动态规划是一种解决具有...

    算法导论斐波那契堆（C#,C++）

    总的来说，斐波那契堆是优化某些算法性能的关键工具，特别是当需要频繁地插入和删除最小元素时。掌握它的原理和实现方法，对于提升算法效率和解决复杂问题具有重要意义。在C#和C++中实现斐波那契堆，可以结合这两种...

    用循环算法求解斐波那契数列

    用循环算法求解斐波那契数列，里面有详细代码文件，亲测可运行

    递归算法 斐波那契数列Demo案例！

    下面是一个简单的Python代码示例，展示了如何使用递归算法来计算斐波那契数列： ```python def fibonacci(n): if n return 0 elif n == 1: return 1 else: return fibonacci(n-1) + fibonacci(n-2) ``` 这...

Magicbox
Global site tag (gtag.js) - Google Analytics