剑指offer_面试题9_斐波那契数列

川长思鸟来 2022-08-03 08:21 126阅读 0赞

**题目一：**写出一个函数，输入n，求斐波那契数列的第n项。

**题目二：**一只青蛙一次可以跳上1级台阶，也可以跳上2级。请求青蛙上一个 n 级的台阶总共有多少种跳法。

第二个题目，其实就是第一个题目的意思。若将 n 级台阶时的跳法看成是 n 的函数，记为 f（n）。

青蛙在第一级台阶时，有两种跳法：

第一次跳 1 级，那么，还剩 n-1 级台阶，那么其跳法总数为 f（n-1）

第一次跳 2 级，那么，还剩 n-2 级台阶，那么其跳法总数为 f（n-2）

因此：f（n） = f（n-1）+ f（n-2）

很明显，这也是一个斐波那契数列。

**一般解法：**低效却是最容易想到的：

/** 低效率解法，例 n=100，计算时间超长。有大量重复计算*/
    int Feibo1(int n)
    {
        if(n < 0)
            return -1;
    
        if(n < 2)
            return (0 == n)? 0 : 1;
        else
            return Feibo1(n - 1) + Feibo1(n - 2);
    }

如下图：可见有大量重复节点，即大量重复计算

![20150803105341988][]

**实用解法，**不用递归而实用循环：

/**实用解法：O(n)*/
    int Feibo2(int n)
    {
        if(n < 0)
            return -1;
    
        long long temp, f1, f2;
        int i;
        int r[2] = {0,1};
        if(n < 2)
            return r[n];
    
        f1 = 0;
        f2 = 1;
        for(i = 2; i <= n; i++)
        {
            temp = f1 + f2;
            f1 = f2;
            f2 = temp;
        }
        return temp;
    }

测试函数：

int main()
    {
        int n = 36;
        int x1, x2;
        x1 = Feibo1(n);
        x2 = Feibo2(n);
        cout << "x1 = " << x1 << endl;
        cout << "x2 = " << x2 << endl;
        return 0;
    }

结果如下：

![20150803110411026][]

/\*点滴积累，我的一小步O(∩\_∩)O~\*/

[20150803105341988]: /images/20220731/d13a6900f52449858482bdec292763dd.png
[20150803110411026]: /images/20220731/8eabd91ea4f349e680e806b66f9d35bc.png