[数据结构与算法]【C语言】斐波那契数列和青蛙跳台阶（最详细的初级青蛙跳台阶）

目录

• 递归求斐波那契数的解决思路及方案
• 迭代求斐波那契数的解决思路及方案
• 青蛙跳台阶问题详解

斐波那契数列指的是这样一个数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368...这个数列从第3项开始，每一项都等于前两项之和。该数列又称黄金分割数列。

提出问题：如何用C语言求解第n个斐波那契数呢？

方案1：递归

思路：当n <= 2时，直接输出1；

? ? ? ? ? ?当n > 2时，利用公式f(n) = f(n-1) + f(n-2)实现递归运算。

#define _CRT_SECURE_NO_WARNINGS 1  

#include <stdio.h>

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

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

	return 0;
}

缺点：进行了大量重复运算！当n很大时，运算时间大大加长，效率大大降低！

方案2：迭代

思路：从前往后来，先令a = 1，b = 1，c = 1。

? ? ? ? ? 当n <= 2时，直接输出c；

? ? ? ? ? 当n > 2时，c = a + b，这样就求出第三个数，然后令a = b, b = c, 再算c = a + b，这样就求出第四个数...

int fib(n)
{
    int a = 1;
	int b = 1;
	int c = 1;
    while (n > 2)
	{
		c = a + b;
		a = b;
		b = c;
		n--;
	}
    return c;
}

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

	return 0;
}

优点：避免的大量重复的计算，大大提高运算效率！

青蛙跳台阶问题

规则：青蛙一次能跳一个或两个台阶

问题：青蛙跳n个台阶有多少种方案？

分析1：1个台阶 - 有一种方案；

分析2：2个台阶 - 有两种方案;

分析3：3个台阶 - 第一步跳1个，还剩2个；第一步跳2个，还剩1个；方案数 = 跳2个的方案数 + 跳1个的方案数；

分析4：4个台阶 - 第一步跳1个，还剩3个；第一步跳2个，还剩2个；方案数 = 跳3个的方案数 + 跳2个的方案数；

分析5：5个台阶 - 第一步跳1个，还剩4个；第一步跳2个，还剩3个；方案数 = 跳4个的方案数 + 跳3个的方案数；

...

分析n：n个台阶 - 方案数 = 跳n-1个的方案数 + 跳n-2个的方案数。

总结：这就是一个斐波那契数列问题，同样的有两个解决方案：递归和迭代

#include <stdio.h>

//递归
int solve1(int n)
{
	switch (n)
	{
	case 1:
		return 1;
	case 2:
		return 2;
	default:
		return solve1(n - 1) + solve1(n - 2);
	}
}

//迭代
int solve2(int n)
{
	int a = 1;
	int b = 2;
	int c = 0;
	
	if (n == 1)
	{
		return 1;
	}
	if (n == 2)
	{
		return 2;
	}

	while (n > 2)
	{
		c = a + b;
		a = b;
		b = c;
		n--;
	}
	return c;
}

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

	printf("递归结果：%d\n", solve1(n));
	printf("迭代结果：%d\n", solve2(n));

	return 0;
}

tips：青蛙跳台阶与斐波那契数列有一点不同的是当n = 2时的结果不同，所以部分代码存在差别，但大思路是不变的。