C#完美实现斐波那契数列

斐波那契数列(1,1,2,3,5,8,...)

用函数表示为f(n)=f(n-1)+f(n-2) (n>2,f(1)=1,f(2)=1)

首先一般想到递归算法:

        /// <summary>
        
/// Use recursive method to implement Fibonacci
        
/// </summary>
        
/// <param name="n"></param>
        
/// <returns></returns>
        static int Fn(int n)
        {
            if (n <= 0)
            {
                throw new ArgumentOutOfRangeException();
            }

            if (n == 1||n==2)
            {
                return 1;
            }
            return checked(Fn(n - 1) + Fn(n - 2)); // when n>46 memory will  overflow
        }

递归算法时间复杂度是O(n2), 空间复杂度也很高的。当然不是最优的。

自然我们想到了非递归算法了。

一般的实现如下:

        /// <summary>
        
/// Use three variables to implement Fibonacci
        
/// </summary>
        
/// <param name="n"></param>
        
/// <returns></returns>
        static int Fn1(int n)
        {
            if (n <= 0)
            {
                throw new ArgumentOutOfRangeException();
            }

            int a = 1;
            int b = 1;
            int c = 1;

            for (int i = 3; i <= n; i++)
            {
                c = checked(a + b); // when n>46 memory will overflow
                a = b;
                b = c;
            }
            return c;
        }

这里算法复杂度为之前的1/n了,比较不错哦。但是还有可以改进的地方,我们可以用两个局部变量来完成,看下吧:

        /// <summary>
        
/// Use less variables to implement Fibonacci
        
/// </summary>
        
/// <param name="n"></param>
        
/// <returns></returns>
        static int Fn2(int n)
        {
            if (n <= 0)
            {
                throw new ArgumentOutOfRangeException();
            }

            int a = 1;
            int b = 1;

            for (int i = 3; i <= n; i++)
            {
                b = checked(a + b); // when n>46 memory will  overflow
                a = b - a;
            }
            return b;
        }

 好了,这里应该是最优的方法了。

值得注意的是,我们要考虑内存泄漏问题,因为我们用int类型来保存Fibonacci的结果,所以n不能大于46(32位操作系统)

原文地址:https://www.cnblogs.com/ericwen/p/Fibonacci.html