C语言递归——青蛙跳台阶问题和汉诺塔问题

一、青蛙跳台阶问题

•题目描述：
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上n级台阶总共有多少种跳法。

•问题分析：
青蛙跳台阶问题可以分成n个子问题。假设青蛙要跳上n级台阶，那么它的最后一步有两种选择：
1.从第n-1级台阶跳1步到达第n级
2.从第n-2级台阶跳2步到达第n级
所以，跳到第n级台阶的跳法数等于跳到第n-1级台阶的跳法数加上跳到第n-2级台阶的跳法数，用数学函数表示为**F(n) = F(n-1) + F(n-2)**

•边界条件：
1.当n=1时，青蛙只能跳1步，因此只有一种跳法：F(n) = 1
2.当n=2时，青蛙有两种跳法：连续跳两步，或者直接跳两步，有两种跳法：F(n) = 2

1.递归解法：

优点：简单直观，易理解
缺点：效率极低，不适合较大的n，时间复杂度为2^n

#include <stdio.h>
int F(int n)
{
	if (n <= 0)
	{
		return 0;
	}
	if (n == 1)
	{
		return 1;
	}
	if (n == 2)
	{
		return 2;
	}
	return F(n - 1) + F(n - 2);
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	int count = F(n);
	printf("%d\n", count);
	return 0;
}

2.迭代（循环）方法

优点：避免重复计算，效率高

#include <stdio.h>
int F(int n)
{
	if (n <= 0)
	{
		return 0;
	}
	if (n == 1)
	{
		return 1;
	}
	if (n == 2)
	{
		return 2;
	}

	int a = 1;
	int b = 2;
	int c = 0;
	for (int j = 3; j <= n; j++)
	{
		c = a + b;
		a = b;
		b = c;
	}
	return c;
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	int count = F(n);
	printf("%d\n", count);
	return 0;
}

二、汉诺塔问题

题目描述：
有三根柱子，分别为A、B和C。在A柱子上有n个大小不一的盘子，从上到下依次增大。目标是将所有盘子从A柱子移动到C柱子上，移动过程中需要满足以下规则：
•每次只能移动一个盘子
•每次移动时，盘子必须从顶部移动到另一根柱子的顶部
•任何时候，较大的盘子不能放在较小的盘子上面

解题思路：
假设我们需要将n个盘子从A柱子移动到C柱子，可以分解为以下步骤：
•将上面的n-1个盘子从A柱子移动到B柱子（借助C柱子）
•将第n个盘子（最大的盘子）从A柱子直接移动到C柱子
•再将B柱子上的n-1个盘子移动到C柱子（借助A柱子）

递归公式：
• 如果只有一个盘子（n=1），直接将盘子从A柱子移动到C柱子
• 如果有n个盘子（n>1），按照上述三步递归解决
终止条件：
• 当n=1时，直接移动盘子，无需进一步分解

1.解法

优点：简洁易懂
缺点：计算较大的数，时间会很久

#include <stdio.h>
void hanoi(int n, char A, char B, char C)
{
	if (n == 1)
	{
		printf("将第%d个盘子从%c柱子移动到%c柱子\n", n, A, C);
		return;
	}
	//将n-1个盘子从A移动到B，借助C
	hanoi(n - 1, A, C, B);

	//将n-1个盘子从A移动到C
	printf("将第%d个盘子从%c柱子移动到%c柱子\n", n, A, C);

	//将n-1个盘子从B移动到C，借助A
	hanoi(n - 1, B, A, C);
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	hanoi(n, 'A', 'B', 'C');
	return 0;
}