【青蛙跳台阶问题】c语言实现

1.问题描述

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

2.问题分析

假设跳上一个n-1级的台阶有x种跳法，跳上一个n-2级的台阶有y种跳法，那么跳上一个n级的台阶总共有x+y种跳法，因为可能性只有两种：

1. 先完成跳到第n-1级台阶这件事，再跳上1级台阶

2. 先完成跳到第n-2级台阶这件事，再跳上2级台阶

即完成n级台阶的最后一步只有两种可能性，这是由前面的步骤决定的。

以上分析发现：

无论n等于多少，青蛙第一次只能决定跳一级台阶或者两级台阶，以此来规划后面的跳法，这就是动态规划的思想，如同斐波拉契数列，用前面的量，推出后面的量。

所以可以采用求斐波拉契数的方法来解决。

3.C语言代码实现及测试

int main(int argc, char **argv)
{
	int f_jump(int);
	int n;
	printf("Please enter the number of steps:>");
	scanf("%d", &n);
	
	int ret = f_jump(n);
	printf("%d\n", ret);
	return 0;
}

int f_jump(int n)
{
	int a = 1;
	int b = 2;
	int c = 1;
	
	if (n == 2)
		c = 2;
	while(n > 2)
	{
		c = a + b;
		a = b;
		b = c;
		n--;
	}
		
	return c;
}
/*测试
Please enter the number of steps:>5
8
*/

4.参考

1.用c语言解决青蛙跳台阶问题