计算机初级选手的成长历程——青蛙跳台阶问题详解

大家好，很高兴又和你们见面啦！在上一篇的内容中，我们把汉诺塔问题从头到尾剖析了一遍，我自己在剖析的过程中，对这个问题的理解也得到了提升，不知道朋友们你们在看完上一篇的内容有什么感受，今天我们来解决第二个经典问题——青蛙跳台阶问题。

编写函数来求解青蛙跳台阶问题：

（1）什么是青蛙跳台阶？

一只青蛙跳台阶时，一次可以跳1级台阶，一次也可以跳2级台阶，问青蛙跳上n级台阶共有多少种跳法？

（2）解题思路

台阶跳法

这里我们将台阶数定位n,跳跃的方式定为f(n)，下面我们来枚举一下跳台阶的方式：

已知当n=1时，青蛙只能跳1级台阶，即f(1)=1,当n=2时，青蛙可以跳两次1级台阶，也可以跳一次2级台阶，即f(2)=2；

当n=3时，青蛙有两种情况来跳台阶，分别是先完1级台阶和先跳完2级台阶：

当先跳完1级台阶时，青蛙还剩2级台阶，此时青蛙跳台阶的方式为f(2);

当先跳完2级台阶时，青蛙还剩1级台阶，此时青蛙跳台阶的方式为f(1)；

即青蛙跳台阶的方式为f(1)+f(2)，具体方式如下：

1. 跳1次1级台阶和2次1级台阶——1+1+1；
2. 跳1次1级台阶和跳1次2级台阶——1+2；
3. 跳1次2级台阶和跳一次1级台阶——2+1；

当n=4时，青蛙有两种情况来跳台阶，分别是先完1级台阶和先跳完2级台阶：

当先跳完1级台阶时，青蛙还剩3级台阶，此时青蛙跳台阶的方式为f(3);

当先跳完2级台阶时，青蛙还剩2级台阶，此时青蛙跳台阶的方式为f(2)；

即青蛙跳台阶的方式为f(2)+f(3)，具体方式如下：

1. 跳1次1级台阶和3次1级台阶——1+1+1+1；
2. 跳1次1级台阶和跳1次1级台阶与跳1次2级台阶——1+1+2；
3. 跳1次1级台阶和跳1次2级台阶和跳1次1级台阶——1+2+1；
4. 跳1次2级台阶和跳2次1级台阶——2+1+1；
5. 跳2次2级台阶——2+2；

当n=5时，青蛙有两种情况来跳台阶，分别是先完1级台阶和先跳完2级台阶：

当先跳完1级台阶时，青蛙还剩4级台阶，此时青蛙跳台阶的方式为f(4);

当先跳完2级台阶时，青蛙还剩3级台阶，此时青蛙跳台阶的方式为f(3)；

即青蛙跳台阶的方式为f(3)+f(4)，具体方式如下：

1. 跳1次1级台阶和跳4次1级台阶——1+1+1+1+1；
2. 跳1次1级台阶和跳2次1级台阶与跳1次2级台阶——1+1+1+2；
3. 跳1次1级台阶和跳1次1级台阶与跳1次2级台阶与跳1次1级台阶——1+1+2+1；
4. 跳1次1级台阶和跳1次2级台阶和跳2次1级台阶——1+2+1+1；
5. 跳1次1级台阶和跳2次2级台阶——1+2+2；
6. 跳1次2级台阶和跳3次1级台阶——2+1+1+1；
7. 跳1次2级台阶和跳1次1级台阶和跳1次2级台阶——2+1+2；
8. 跳1次2级台阶和跳1次2级台阶与跳1次1级台阶——2+2+1；

以此类推……

当n=n时，青蛙青蛙有两种情况来跳台阶，分别是先完1级台阶和先跳完2级台阶：

当先跳完1级台阶时，青蛙还n-1剩级台阶，此时青蛙跳台阶的方式为f(n-1);

当先跳完2级台阶时，青蛙还剩n-2级台阶，此时青蛙跳台阶的方式为f(n-2)；

即青蛙跳台阶的方式为f(n-2)+f(n-1)，具体方式如下：

1. 跳1次1级台阶和跳n-1次1级台阶——1+……+1；
2. 跳1次1级台阶和跳n-3次1级台阶与跳1次2级台阶——1+……+1+2；
3. 跳1次1级台阶和跳n-4次1级台阶与1次2级台阶与1次1级台阶——1+……+2+1；
4. ……跳完先跳1级台阶的所有情况；
5. 跳1次2级台阶和跳n-2次1级台阶——2+1+……+1；
6. 跳1次2级台阶和跳n-4次1级台阶与1次2级台阶——2+1+……+1+2；
7. 跳1次2级台阶和跳n-6次1级台阶与2次2级台阶——2+1……+1+2+2；
8. ……跳完2级台阶的所有情况；

下面我们通过表格将上述情况汇总起来：

从这里我们可以看到，从第3项开始，跳跃方式为前两项的和，这种情况是不是有点熟悉啊，我们之前在哪里见过来着？对了就是斐波那契数列。接下来我们顺着解决斐波那契数的思路来求解这个问题：

功能编写

功能一——从第3项起，每一项为前两项之和

int a = 1, b = 2, c = 0;
  //第3项起，每一项为前两项之和
	c = a + b;
	a = b;
	b = c;

这里我们通过加法以及互换完成这个功能；

功能二——求第n项

这里我们有两种方式来实现，函数递归与迭代，我们先从简单的方式函数迭代来介绍。

函数迭代

函数迭代——在函数中使用循环语句，通过循环语句来重复进行一件事情，在这个问题中我们需要重复进行的事情就是计算两项之和，再将结果进行互换，完成数的推进，代码如下：

int jump(int n)
{	
	int a = 1, b = 2, c = 0;
	//判断台阶数
	if (n <= 2)//当n<=2时，n的值=跳台阶的方式
	{
		return n;
	}
	else//n>2时开始进行迭代
	{
		//在jump函数内进行迭代
		for (int i = 3; i <= n; i++)
		{
			//第3项起，每一项为前两项之和
			c = a + b;
			a = b;
			b = c;
		}
		return c;
	}
}

因为跳台阶的方式是从第3项开始才等于前两项之和，所以我们要在jump函数内将前两项后n项给分开，这里我们可以通过选择语句来实现，要注意的是，因为我们是从第3项开始的，所以这个循环变量的初始值应该为3。

接下来我们来通过函数递归的方式来实现青蛙跳台阶的问题：

函数递归

函数递归——在函数中嵌套函数本身来重复完成一件事，思考方式是大事化小。

在这个问题中，我们需要搞清楚两个问题，如何递进，如何回归：

1. 如何递进？

通过递推公式可知，我们在递进的时候只需要完成一个工作，将前两项求和就行。前两项通过函数的参数来确定，如下所示：

这里我们就可以得到jump(n)=jump(n-1)+jump(n-2)这个递进公式，递进的条件是n>=3当n<3时函数不需要递进，只需要将参数值返回给函数就行。

1. 如何回归？

在这个函数中，我们只需要将后前两项求和并将这个值返回给主函数就可以了，这里我们就可以直接返回前两项的和，也就是：

return jump(n-1)+jump(n-2)

接下来我们开始编写代码：

int jump(int n)
{
	//n值判断
	if (n < 3)//当n<3时，返回n值
	{
		return n;
	}
	else//当n>=3时，返回前两项之和
	{
		//前两项每一项的和都通过递归的方式求解
		return jump(n - 1) + jump(n - 2);
	}
}

与迭代一样，我们同样需要利用选择语句来对n值进行判定，从而区分开台阶数为1和2时的情况与台阶数大于2时的情况。接下来我们就来实现jump函数求解青蛙跳台阶的方式；

（3）函数的实现

函数迭代实现：

int jump(int n)
{	
	int a = 1, b = 2, c = 0;
	//判断台阶数
	if (n <= 2)//当n<=2时，n的值=跳台阶的方式
	{
		return n;
	}
	else//n>2时开始进行迭代
	{
		//在jump函数内进行迭代
		for (int i = 3; i <= n; i++)
		{
			//第3项起，每一项为前两项之和
			c = a + b;
			a = b;
			b = c;
		}
		return c;
	}
}
int main()
{
	//定义第n项的变量
	int n = 0;
	//通过输入函数进行赋值
	scanf("%d", &n);
	//通过传值调用，将实参n的值传给jump函数
	int m = jump(n);
	printf("青蛙跳%d级台阶总共有%d种方式\n", n, m);
	return 0;
}

下面我们测试一下n=5与n=10000：

我们可以看到通过函数迭代能够很好的实现求解青蛙跳台阶的方式。下面我们来看一下函数递归的方式实现；

函数递归实现：

int jump(int n)
{
	//n值判断
	if (n < 3)//当n<3时，返回n值
	{
		return n;
	}
	else//当n>=3时，返回前两项之和
	{
		//前两项每一项的和都通过递归的方式求解
		return jump(n - 1) + jump(n - 2);
	}
}
int main()
{
	//定义第n项的变量
	int n = 0;
	//通过输入函数进行赋值
	scanf("%d", &n);
	//通过传值调用，将实参n的值传给jump函数
	int m = jump(n);
	printf("青蛙跳%d级台阶总共有%d种方式\n", n, m);
	return 0;
}

同样也是输入5和10000进行测试：

我们可以从结果中看到，当n=5时，程序能正常运行，但是当n=10000时，程序却无法运行。这是为什么呢？

在函数递归这个篇章中我们有讨论过递归的限制条件是为了防止递归进入死循环从而导致栈溢出；

但是这个限制条件并不是万能的，当你的条件只有下限没上限或者只有上限没下限时，又或者你的上限太大或者下限太小，都会导致栈溢出的问题。

究其原因就是因为递归是不断地进行函数调用，不断地向内存的栈区申请空间，这个空间是有限的，只要你申请的次数足够多，它的空间就会被申请完，此时你想继续申请，它就会导致栈溢出。

总结

在青蛙跳台阶的问题，我们可以通过函数递归或者函数迭代的方式去实现，但是使用函数递归时，只要参数足够大就会存在栈溢出的问题，所以建议大家尽量使用函数迭代的方式实现，

（4）涉及知识点

这个例子也是一个综合性很强的例子，它的综合性体现在我可以通过多种方式去实现，咱们这里使用的是函数递归与迭代的方式，这里涉及到的函数知识点有：

• 函数的组成
• 函数参数
• 函数的传值调用
• 函数的声明与定义
• 函数的递归与迭代

结语

到这里咱们本章的内容就全部结束了，希望今天的内容能帮助大家更好的理解函数递归与迭代的区别。接下来随着学习的深入，我会继续给大家分享我在学习过程中的感受。如果各位喜欢博主的内容，还请给博主的文章点个赞支持一下，有需要的朋友也可以收藏起来反复观看哦！感谢各位的翻阅，咱们下一篇见。