青蛙跳台阶（递归和迭代）

75 阅读 0 评论 50 点赞

我是靠谱客的博主娇气手套，这篇文章主要介绍青蛙跳台阶（递归和迭代），现在分享给大家，希望可以做个参考。

题目描述：青蛙一次可以跳1级或2级台阶，n级台阶，一共有几种跳法？
分析：n = 1 时，只有1种跳法
n = 2 时，青蛙可以两次都跳1级，也可以一次跳2级，共2种跳法
n > 2 时，第一次可以跳 1 级台阶或者 2 级台阶（类似斐波那契数），即 f(n) = f(n - 1) + f(n -2);

递归

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <stdio.h>
int step(int n);
int main()
{
	int n = 0;
	scanf("%d", &n);
	printf("%d", step(n));
	return 0;
}
int step(int n)
{
	if (1 == n)
	{
		return 1;
	}
	else if (2 == n)
	{
		return 2;
	}
	else
	{
		return step(n - 1) + step(n - 2);
	}
}

迭代

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <stdio.h>
int step(int n);
int main()
{
	int n = 0;
	scanf("%d", &n);
	printf("%dn", step(n));
	return 0;
}
int step(int n)
{
	int i = 0;
	int n1 = 1;
	int n2 = 2;
	int sum = 0;
	for (i = 3; i <= n; i++)
	{
		sum = n1 + n2;
		n1 = n2;
		n2 = sum;
	}
	//n = 1 和 n = 2 需要单独讨论
	if (1 == n)
	{
		return n1;
	}
	else if (2 == n)
	{
		return n2;
	}
	else 
	{
		return sum;
	}
}