青蛙跳台阶(C语言)

1.代码:

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>

int func(int n)
{
	if (n == 1)
	{
		return 1;
	}
	else if (n == 2)
	{
		return 2;
	}
	return func(n - 1) + func(n - 2);
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = func(n);
	printf("%d\n", ret);

	return 0;
}

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

3.答案:

我们用递归方法来解题:

秉持着大事化小原则:

假设让青蛙跳上一个台阶,那么还有(n - 1)个台阶要跳

假设让青蛙跳上二个台阶,那么还有(n - 2)个台阶要跳

那么每一次跳台阶都可以分成跳一次和跳二次,在调完一或二次之后,又可以分为跳一次或跳二次,以此类推

但要注意,在最后两个台阶的时候,青蛙有两种跳法,在最后一个台阶的时候,青蛙有一种跳法

4.该问题实质是一个斐波那契数数列

上边为递归

下边为迭代

与斐波那契数相似

代码:

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>

int main()
{
	int n = 0;
	scanf("%d", &n);


	int a = 1;
	int b = 2;
	int c = 1;
	//3步
	int i = 0;
	for (i = 0; i < n - 2; i++)
	{
		c = a + b;
		a = b;
		b = c;
	}
	printf("%d\n", c);








	return 0;
}