剑指Offer的学习笔记（C#篇）-- 斐波那契数列

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。

一 . 理解概念

斐波那契数列概念：斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”（来自百度百科）。具体可由以下公式表示：

二.C#代码如何实现

由上述公式可知，斐波那契数列存在两个特殊值，即当n=0和n=1时，因此，可将n等于0与1时提出来作单独处理，而剩下的部分再作单独处理，基于这种想法，实现该目标可使用两种方法：

方法1：递归法。

斐波那契数列是递归法最典型的一种体现，但又存在着很多的不足。

其中，递归的实现是通过调用函数本身，函数调用的时候，每次调用时要做地址保存，参数传递等，这是通过一个 递归工作栈 实现的。具体是每次调用函数本身要保存的内容包括： 局部变量、形参、调用函数地址、返回值 。那么，如果递归调用 N 次，就要分配 N*局部变量、N*形参、N*调用函数地址、N*返回值，这势必是影响效率的，该题目中，用递归方法计算的时间复杂度是以n的指数的方式递增的，此段来自Edison Zhou的博文。

如下代码是使用递归实现的斐波那契数列（该题目中可以看出，若你>1,计算f(n)需要不断重新的调用Fibonacci函数）：

class Solution{

     public int Fibonacci(int n)

    {

        //当n小于等于0时，返回0

        if (n <= )

        {

            return ;

        }

        //当n等于1时，返回1

        if (n == )

        {

            return ;

        }

        //否则，返回前两个数之和

        else

       {

             return Fibonacci(n - ) + Fibonacci(n - );

        }

    }

}

很显然，递归虽然可以实现斐波那契数列，但却存在着一定的问题。

方法二：循环法。

由于递归存在着效率低问题，为解决该问题，引入循环的方法避免了递归法重复计算的弊端，从而运算的时间复杂度变为是O(n)。

具体实现代码如下：

class Solution

{

    public int Fibonacci(int n)

    {

        // write code here

        int x = ;

        int y = ;

        int result = ;

        if (n == )

        {

            return ;

        }

        if (n == )

        {

            return ;

        }

        else

        {

            for (int i=;i<=n;i++)

        {

            result = x + y;

            x = y;

            y = result;

        }

            return result;

        }

    }

}