青蛙跳台阶(递归和循环)

骑猪看日落 2024-04-01 14:49 36阅读 0赞

#### 青蛙跳台阶 ####

*  一.递归
 *  二.循环

![在这里插入图片描述][ea6948d0bc57434ea7a1668caedb39d9.png]

## 一.递归 ##

![在这里插入图片描述][499545ea728949a0a48f59e743353771.png]

> **我们可以进行一个简单的列表**

![在这里插入图片描述][1a4e33578781420ab8568ecae5f96a7d.png]

> **以上我们可以看出从第3次开始后面的次数就等于前面两次之和，实际上青蛙跳台阶问题就是变相的斐波那契函数。**

int Jump(int n)
    {
        
    	if (n == 1)
    	{
        
    		return 1;
    	}
    	else if  (n == 2)
    	{
        
    		return 2;
    	}
    	else 
    	{
        
    		return Jump(n - 1) + Jump(n - 2);
    	}
    }
    int main()
    {
        
    	int n = 0;
    	scanf("%d", &n);
    	int sum=Jump(n);
    	printf("总共有%d种跳法", sum);
    	return 0;
    }

> **根据递归的思想当n=1时,就return 1，当n=2时,就return 2，当n>2时，就return (前一函数值+后一个函数值)**

## 二.循环 ##

> **有时候当数字太大时，递归很容易导致栈溢出，程序崩溃，我们也可以用循环的方式实现它**

int a = 1;//当n=1时有a种跳法
    	int b = 2;//当n=2时有b种跳法
    	int c = 1;//c为下一项(第三项)
    	if (n == 1)
    	{
        
    		return a;
    	}
    	if (n == 2)
    	{
        
    		return b;
    	}
    	if (n > 2)
    	{
        
    		while (n - 2)
    		{
        
    			c = a + b;//将a+b的值给c
    			int tmp = b;
    			b = c;
    			a = tmp;//将b的值给a,再将c的值给b
    			n--;
    		}//循环n-2次
    		return c;
    	}

**ps：当数字太大时不能得出正确的答案，但程序一般不会崩溃**

![在这里插入图片描述][3265554ef0ff47e08c2b8b6be62ea02b.png]

[ea6948d0bc57434ea7a1668caedb39d9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/febc9b70af7e43aa89d93cf185d23ba9.png
[499545ea728949a0a48f59e743353771.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/d849668ae1c442d79d4e34c51e133b13.png
[1a4e33578781420ab8568ecae5f96a7d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/d664118ecf3440f6a7d9b44838653c91.png
[3265554ef0ff47e08c2b8b6be62ea02b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/167374ee9cea4d1a9dfbad7354874201.png