跳台階和變态跳台階

1、跳台階

題目描述：

一隻青蛙一次可以跳上1級台階，也可以跳上2級。求該青蛙跳上一個n級的台階總共有多少種跳法（先後次序不同算不同的結果）。

思路分析：

一隻青蛙跳台階有兩種選擇，要麼跳一級，要麼跳兩級，是以可以列舉出以下幾種情況：

台階級數 跳法

1 1

2 2

3 3

4 5

5 8

… …

n n-1+n-2

經過分析可知，青蛙跳台階的跳法符合斐波那契數列，即f(n)=f(n-1)+f(n-2);

是以青蛙普通跳台階的代碼如下：

class Solution {
public:
    int FibFloor(int n)
    {
        if(n==1)
        {
            return 1;
        }
        else if(n==2)
        {
            return 2;
        }
        else
        {
            return (FibFloor(n-1)+FibFloor(n-2));
        }
    }
    int jumpFloor(int number) {
        return FibFloor(number);
    }
};
           

2、變态跳台階

題目描述：

一隻青蛙一次可以跳上1級台階，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的台階總共有多少種跳法。

思路分析：

與上題不同的是，變态青蛙一次最多可以跳n級台階，是以每一級台階的跳法有很多，下面就先列舉一段分析;

台階級數 跳法

1 1

2 2

3 4

4 8

… …

n 2^(n-1)

經過分析可知，n級台階青蛙有2^(n-1)種跳法，代碼如下：

class Solution {
public:
    int jumpFloorII(int number) {
        //利用幂函數計算函數計算2^(n-1)
        //return pow(2,number-1);
        //利用移位運算符計算2^(n-1)
        int a=1;
        return a<<(number-1);
    }
};