斐波那契数算法优化


		      在很多算法都用到了递归算法，谈到递归就难免要提到斐波那契数的算法。
     最一般的算法如下(C#语法)：        
[csharp] 
private long Fibonacci(int n)  
       {  
           if (n == 1 || n == 2)  
               return 1;  
           else if (n > 2)  
               return Fibonacci(n - 1) + Fibonacci(n - 2);  
           else  
               return 0;  
       }  
 
    运行测试下，发现当参数n=39时运行速度就变的很慢了,我计算了下，大概3－4秒,而当n=42时，已然要10来秒才能完成，当n=45时就没反应了，一两分钟都没有结果。
    其实仔细分析下可以Fibonacci方法在被调用后，向下调用就翻倍地调用了下一级的Fibonacci方法。
    计算了一下，假设斐波那契数数列的第N项的值是an(n)的话，那么调用上面的递归算法，Fibonacci方法会被调用 an(n) *2 +1 次，当n=39时an(39)=63245986,Fibonacci方法被调用了126491971次，效率之低可以见一斑。
   这里我做了下优化，算法如下：
[csharp]  
private long Fibonacci(int n,out long m)  
        {  
            long t, r;  
            if (n == 1)  
            {  
                m=0;  
                return 1;  
            }  
            else if (n == 2)  
            {  
                m = 1;  
                return 1;  
            }  
            else if (n > 2)  
            {  
                t = Fibonacci(n - 1, out m);  
                r = t + m;  
                m = t;  
                return r;  
            }  
            else  
            {  
                m = 0;  
                return 0;  
            }  
        }  
 
此处的最大优化在于保存计算项之前的每一项的值，每一项的计算只调用Fibonacci方法一次，实际调用Fibonacci方法的次数只有n-1次，如果n=33，那么调用Fibonacci方法只有32次。
    看看方法的调用次数就可知算法的效率了。

补充：软件开发 , C# ,