剑指offer（8）&（9）——C++实现青蛙跳台阶

痛定思痛。 2021-10-29 11:04 182阅读 0赞

# 题目 #

1.  正常跳：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
2.  变态跳：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

# 考察点 #

*  斐波那契数列[参考剑指offer（7）][offer_7]
 *  递归的理解
 *  数学建模的能力

# 解题思路 #

1.  正常跳：

*  只有一个台阶时，只有一种跳法：n=1,f(1)=1
 *  有两个台阶时，有两种跳法：每次只跳一个，或直接跳两个台阶，n=2,f(2)=2
 *  当大于两个台阶时，第一次只跳一个台阶，那么剩下的跳法数目=f(n-1),第一次跳两个台阶，剩下的跳法数目=f(n-2).所以总共的跳法数目：f(n)=f(n-1)+f(n-2)

f ( n ) = \{ 1 , n = 1 2 , n = 2 f ( n − 1 ) + f ( n − 2 ) , n > 2 f(n)=\\left\\\{ \\begin\{aligned\} &1,n=1\\\\ &2,n=2\\\\&f(n-1)+f(n-2),n>2 \\end\{aligned\} \\right. f(n)=⎩⎪⎨⎪⎧1,n=12,n=2f(n−1)\+f(n−2),n>2  
2. 变态跳：

*  只有一个台阶时，只有一种跳法：n=1,f(1)=1
 *  有两个台阶时，有两种跳法：每次只跳一个，或直接跳两个台阶，n=2,f(2)=2
 *  有n个台阶时，第一次只跳一个台阶，那么剩下的跳法数目=f(n-1),第一次跳两个台阶，剩下的跳法数目=f(n-2)，第一次只跳三个，那么剩下的跳法数目=f(n-3),所以总共的跳法数目：f(n)=f(n-1)+f(n-2)+…+f(n-n)。数学运算简化可得：f(n)=2\*f(n-1)

f ( n ) = \{ 1 , n = 1 2 , n = 2 f ( n ) = 2 ∗ f ( n − 1 ) , n > 2 f(n)=\\left\\\{ \\begin\{aligned\} &1,n=1\\\\ &2,n=2\\\\&f(n)=2\*f(n-1),n>2 \\end\{aligned\} \\right. f(n)=⎩⎪⎨⎪⎧1,n=12,n=2f(n)=2∗f(n−1),n>2

# 完整代码 #

/*08&09-青蛙跳台阶（斐波那契变形）*/
    #include<iostream>
    using namespace std;
    class Solution {
        
    public:
    	int jumpFloor(int number) //正常跳
    	{
        
    		if (number == 1)return 1;
    		if (number == 2) return 2;
    		return jumpFloor(number - 1) + jumpFloor(number - 2);
    	}
    	int jumpFloorII(int number) //变态跳
    	{
        
    		if (number == 1)return 1;
    		if (number == 2) return 2;
    		return 2*jumpFloor(number - 1);
    	}
    };
    int main()
    {
        
    	Solution s;
    	cout << s.jumpFloor(3) << endl;
    	cout << s.jumpFloorII(3) << endl;
    	return 0;
    }

[offer_7]: https://blog.csdn.net/fengwenpei/article/details/99635293