191-解决变态跳台阶问题

朴灿烈づ我的快乐病毒、 2022-10-29 14:26 6阅读 0赞

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

**解题思路：**  
因为n级台阶，第一步有n种跳法：跳1级、跳2级、到跳n级  
跳1级，剩下n-1级，则剩下跳法是f(n-1)  
跳2级，剩下n-2级，则剩下跳法是f(n-2)  
所以f(n)=f(n-1)+f(n-2)+…+f(1)  
因为f(n-1)=f(n-2)+f(n-3)+…+f(1)

所以f(n)=2\*f(n-1)

f(n) = f(n-1) + f(n-2) + f(n-3) + … + f(n-n) = f(0) + f(1) + f(2) + … + f(n-1)  
又因为 f(n-1) = f(0) + f(2) + f(3) + … + f(n-2)  
**两式相减得**：f(n) = 2 \* f(n-1) ( n >= 2)  
| 0，n = 0  
f(n) = | 1, n = 1  
| 2 \* f(n-1) , n >= 2

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]

## 写法1 ##

#include<stdio.h>
    int JumpFloor(int n)
    {
        
    	if (n <= 0)
    		return 0;
    	if (n == 1)
    		return 1;
    	int f = 1;
    	for (int i = 2; i <= n; i++)
    	{
        
    		f = 2 * f;
    	}
    	return f;
    }
    
    int main()
    {
        
    	int a=0;
    	scanf("%d",&a);
    	printf("%d\n",JumpFloor(a));
    
    	return 0;
    }

**运行截图如下：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]

## 写法2 ##

#include<stdio.h>
    int JumpFloorII(int target) 
    {
        
    	if (target <= 0) 
    	{
        
    		return -1;
    	} else if (target == 1)
    	{
        
    		return 1;
    	} else 
    	{
        
    		return 2 * JumpFloorII(target - 1);
    	}
    }
    
    int main()
    {
        
    	int a=0;
    	scanf("%d",&a);
    	printf("%d\n",JumpFloorII(a));
    
    	return 0;
    }

**运行截图如下：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]

## 写法3 ##

**用位移符进行优化，更快**

#include<stdio.h>
    
    int jumpFloorII(int number)
    {
        
    	int tmp = 1;
    	tmp = tmp << (number - 1);
    	return tmp;
    }
    
    int main()
    {
        
    	int a=0;
    	scanf("%d",&a);
    	printf("%d\n",jumpFloorII(a));
    
    	return 0;
    }

**运行截图如下：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 3]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221024/53ad5d95f2964b2d9ef6bf5ae23c949c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221024/19a1e5788ae84c2ead0ceef0b3d2f807.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221024/f6d43837330b49d6a135e1893d1e8c62.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221024/eb2c7783c7b64bbfb3c0d5687cf6ec40.png