【牛客网】跳台阶 and 变态跳台阶

缺乏、安全感 2021-12-19 00:37 197阅读 0赞

### 1. 跳台阶 ###

##### 题目描述： #####

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种方法？

##### 解题思路 #####

这种问题一般是有规律的，跳1级台阶，只有1种方法；跳2级台阶，有2种方法；跳3级台阶，有3种方法；跳4级台阶，有5种方法，依次下去…  
跳一个n级的台阶的方法数是跳n - 1级台阶的方法数与跳n - 2阶台阶的方法数的总和。这种思路可以用逆推去想，要跳上一个n级台阶，可以从n - 1级台阶跳1级，也可以从n - 2级台阶跳2级，这就相当于跳上n - 1级台阶的方法加上跳上n - 2级台阶的方法。  
注意：这个问题的规律和斐波拉契数列是一样的  
即公式如下：

n==1: return 1
    n==2: return 2
    n> 2: return f(n)=f(n-1)+f(n-2)

#### 完整代码 ####

代码很简单，用个递归就好了。

#include <iostream>
    #include <math.h>
    
    using namespace std;
    
    int JumpFloor(int n)
    {
    	if (n == 1)
    		return 1;
    	if (n == 2)
    		return 2;
    	if (n>2)
    		return JumpFloor(n - 1) + JumpFloor(n - 2);
    }
    int main()
    {
    	int n = 0;
    	while (cin >> n)
    	{
    		int sum = JumpFloor(n);
    		cout << sum<<endl;
    	}
    	system("pause");
    	return 0; 
    }

### 2. 变态跳台阶 ###

##### 题目描述 #####

一只青蛙一次可以跳上1级台阶，也可以跳上2级，。。。，它也可以跳上n级，求该青蛙跳上一个n级的台阶总共有多少种方法？

##### 解题思路 #####

1.  这道题可以用逆推的思路去想，跳n级台阶，可以从n - 1级跳上来，也可以从n - 2级跳上来，从n - 3级跳上来，依次下去，从第1级跳上去，或直接跳上去，所以，跳n级台阶的方法数相当于其它所有台阶数的方法的总和再加上从0级跳上去，表达式为 f(n) = f(n - 1) + f(n - 2) + … + f(2) + f(1) + 1。
2.  即公式如下：

n==1: return 1    n> 1: return f(n)=2*f(n-1) 
    或者直接f(n)=2^(n-1)

##### 完整代码 #####

int JumpFloorII(int n)
    {
    	if (n == 1)
    		return 1;
    	if (n > 1)
    		return 2 * JumpFloorII(n - 1);
    }
    
    int main()
    {
    	int n = 0;
    	while (cin >> n)
    	{
    		int sum = JumpFloorII(n);
    		cout << sum<<endl;
    	}
    	system("pause");
    	return 0; 
    }

一句代码搞定！

int JumpFloorII(int n)     //变态跳台阶
    {
    	return pow(2, n - 1);
    }