青蛙跳台阶（详解）_楼梯有n阶台阶,青蛙每次可以跳1~n阶台阶,问青蛙共有多少种上楼梯的方法。

问题描述

一只青蛙可以一次跳 1 级台阶或一次跳 2 级台阶,例如:
跳上第一级台阶只有一种跳法:直接跳 1 级即可.
跳上两级台阶,有两种跳法: 每次跳 1 级,跳两次; 或者一次跳 2 级.
问要跳上第 n 级台阶有多少种跳法?

解题思路

当只有一层台阶时，青蛙当然只有一种跳法；
当有两层台阶时，青蛙可以先跳一层，再跳一层；或者直接跳两层，这是两种跳法；
当有三层台阶时，青蛙可以选择先跳一层，剩下两层台阶，所以此时就是有两层台阶时的跳法，有2种，
当青蛙选择第一次跳两层台阶时，剩下一层台阶，此时时有一层台阶时的跳法，有1种
所以3层台阶时的方法是：2层台阶的方法 + 1层台阶的方法。
以此类推可以得到：4层台阶 = 3层台阶方法 + 2层台阶方法
.
.
.
n层台阶 = n - 1层台阶方法 + n - 2层台阶方法。

就是斐波那契数列的变形

递归实现

这里需要注意的是，该递归算法为两路递归，当n值太大会出现栈溢出的现象

//递归实现  青蛙跳台阶问题
#include <stdio.h>

int frog(int n)
{
	//递归的两个终止条件
	//1、台阶数n=1时
	//2、台阶数n=2时
	if (n == 1)
	{
		return 1;
	}
	else if (n == 2)
	{
		return 2;
	}
	else
	{
		//台阶数n=n时，有n-1个台阶数跳法 + n-2个台阶数跳法的和
		return frog(n - 1) + frog(n - 2);
	}
}


int main()
{
	//count 用于记录青蛙跳到终点有多少种跳法
	int count = 0;
	//用于记录一共有多少个台阶
	int n = 0;
	printf("请输入台阶数>:");
	scanf("%d", &n);
	count = frog(n);

	printf("一共有多少种跳法%d\n", count);
	return 0;
}
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
37

迭代实现

迭代可以理解为循环

//迭代实现青蛙跳台阶问题
#include <stdio.h>

int frog(int n)
{
	int f1 = 1, f2 = 2, fn = 0;
	int i = 2;
	if (n == 1)
	{
		return f1;
	}
	else if (n == 2)
	{
		return f2;
	}
	else
	{
		while (i < n)
		{
			i++;
			fn = f1 + f2;
			f1 = f2;
			f2 = fn;
		}
		return fn;
	}
}

int main()
{
	//count 用于记录青蛙跳到终点有多少种跳法
	int count = 0;
	//用于记录一共有多少个台阶
	int n = 0;
	printf("请输入台阶数>:");
	scanf("%d", &n);
	count = frog(n);

	printf("一共有多少种跳法%d\n", count);
	return 0;
}
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
37
38
39
40
41

变态青蛙跳台阶

问题描述

（1）一只青蛙一次可以跳上 1 级台阶，也可以跳上2 级。求该青蛙跳上一个n 级的台阶总共有多少种跳法。
（2）一只青蛙一次可以跳上1级台阶，也可以跳上2 级……它也可以跳上n 级，此时该青蛙跳上一个n级的台阶总共有多少种跳法？
（3）一只青蛙一次可以跳上1级台阶，也可以跳上2 级……它也可以跳上n 级（青蛙一次最多跳的台阶数由用户指定），此时该青蛙跳上一个n级的台阶总共有多少种跳法？

解决思路

n=1时，f(n)=1
n=2时，f(n)=2
n=3时，f(n)=4
n=4时，f(n)=8
…
n=n时，f(n)=2*f(n-1)
f(n)是等比数列，其通项为f(n)=2^(n-1)

代码演示

#include <stdio.h>

int frog(int n)
{
	int fn = 1;
	int i = 2;
	for (i; i <= n; i++)
	{
		fn = fn * 2;
	}
	return fn;
}

int main()
{
	//count 用于记录青蛙跳到终点有多少种跳法
	int count = 0;
	//用于记录一共有多少个台阶
	int n = 0;
	printf("请输入台阶数>:");
	scanf("%d", &n);
	count = frog(n);

	printf("一共有多少种跳法%d\n", count);
	return 0;
}
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

到这里这篇博客已经结束啦
这份博客