青蛙跳台（递归和非递归实现）一、问题描述：二、问题分析：三、代码实现：四、问题进阶：

53 阅读 0 评论 35 点赞

我是靠谱客的博主温暖摩托，最近开发中收集的这篇文章主要介绍青蛙跳台（递归和非递归实现）一、问题描述：二、问题分析：三、代码实现：四、问题进阶：，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

青蛙跳台

一、问题描述：
二、问题分析：
三、代码实现：
- 1、递归实现：
- 2、非递归实现：
四、问题进阶：
- 1、问题分析：
- 2、代码实现：

一、问题描述：

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

在这里插入图片描述

二、问题分析：

当n=1时，有一种跳法：
1、跳1级。
当n=2时，有两种跳法：
1、跳1级，跳1级。
2、跳2级。
当n=3时，有三种跳法：
1、跳1级，跳1级，跳1级。
2、跳1级，跳2级。
3、跳2级，跳1级。

我们可以将n级台阶时的跳法看成是n的函数f(n)。
当n>2时，青蛙跳第一步有两种选择（跳1级或者跳2级）：
1、第一步跳1级。剩下n-1级有f(n-1)中跳法。
2、第一步跳2级。剩下n-2级有f(n-2)中跳法。
所以n个台阶时有f(n)=f(n-1)+f(n-2)种跳法。

三、代码实现：

1、递归实现：

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int FrogJump(int n){
	if (n == 1){
		return n;
	}
	if (n == 2){
		return n;
	}
	return FrogJump(n - 1) + FrogJump(n - 2);//递归
}

int main()
{
	int n = 0;
	printf("请输入台阶数n:");
	scanf("%d", &n);
	int res = FrogJump(n);
	printf("%dn", res);
	system("pause");
	return 0;
}

代码分析：
重复计算次数多，运行时间较长。

2、非递归实现：

把倒数第一个台阶的跳法数设为last1，倒数第二个台阶的跳法数设为last2，第三个台阶的跳法数设为cur。
根据f(n)=f(n-1)+f(n-2)，我们可以得到：cur=last1+last2。运算完后，那么把整体的last1，last2，cur向后移动一位，重新迭代。直到你要求的第n个数，迭代结束，最后的cur就时第n级台阶的跳法数。

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int FrogJump(int n){
	if (n == 1){
		return n;
	}
	if (n == 2){
		return n;
	}
	int last1 = 2;//倒数第一个台阶的跳法数
	int last2 = 1;//倒数第二个台阶的跳法数
	int cur = 0;//当前台阶的跳法数
	for (int i = 3; i <= n; i++){
		cur = last1 + last2;
		last2 = last1;
		last1 = cur;
	}
	return cur;
}

int main()
{
	int n = 0;
	printf("请输入台阶数n：");
	scanf("%d", &n);
	int res = FrogJump(n);
	printf("%dn", res);
	system("pause");
	return 0;
}

代码分析：
代码不够整洁，运行时间短。

四、问题进阶：

这时候青蛙变的很变态了，不仅一次可以跳上1级台阶，也可以跳上2级……甚至它还可以跳上n级台阶，此时该青蛙跳上一个n级的台阶总共有多少种跳法？

1、问题分析：

我们还是将n级台阶时的跳法看成是n的函数f(n)。

当n=1时，有一种跳法。
1、跳1级。
当n=2时，有两种跳法。
1、跳1级。
2、跳2级。
当n=3时，有四种跳法。
1、跳1级，跳1级，跳1级。
2、跳1级，跳2级。
3、跳2级，跳1级。
4、跳3级。
当第一次跳1级时，后面还有f(3-1)种跳法。
当第一次跳2级时，后面还有f(3-2)种跳法。
当第一次跳3级时，后面还有f(3-3)种跳法。

当有n级台阶时，
第一次跳1级时，后面还有f(n-1)种跳法，第一次跳2级时，后面还有f(n-2)种跳法，第一次跳3级时，后面还有f(n-3)种跳法……第一次跳n级时，后面还有f(n-n)种跳法。
所以，f(n)=f(n-1)+f(n-2)+……+f(n-n)=f(0)+f(1)+f(2)+……+f(n-2)+f(n-1)。
因为：f(n-1)=f(0)+f(1)+f(2)+……+f(n-2)，
所以，f(n)=2*f(n-1)。

2、代码实现：

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int FrogJump(int n){
	if (n == 1){
		return n;
	}
	if (n == 2){
		return n;
	}
	return 2 * FrogJump(n - 1);
}

int main()
{
	int n = 0;
	printf("请输入台阶数n:");
	scanf("%d", &n);
	int res = FrogJump(n);
	printf("%dn", res);
	system("pause");
	return 0;
}