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

57 阅读 0 评论 38 点赞

我是靠谱客的博主老实小鸭子，最近开发中收集的这篇文章主要介绍C语言递归问题【青蛙跳台阶】和【汉诺塔】，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

青蛙跳台阶

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

分析：
当n为1时，有1种方法；
当n为2时，有2种方法；
当n为3时，有3种方法；
当n为4时，有5种方法；
当n为5时，有8种方法；
当n为6时，有13种方法；
当n为7时，有21种方法；
|n| sum|
|-1-|-1-|
| 2 |2
3 |3
4 |5
5 |8
6 |13
7 |21

这个数列为：1,2,3,5,8，…
我们不难发现：第n次的跳法数为第n-1次和第n-2次之和
规律如下：
f(n)=f(n-1)+f(n-2)

具体实现如下：

#include<stdio.h>
int sum(int n)
{
	if (n <= 2)
	{
		return n;
	}
	else
		return sum(n - 1) + sum(n - 2);
}
int main()
{
	int n = 0;
	printf("请输入总的台阶数：");
	scanf("%d", &n);
	int ret = sum(n);
	printf("一共有%d种方法  ", ret);
	return 0;
}

//上述方法如果值过大时，会造成很大的浪费的情况，做了很多重复的计算，大家可以试试！

汉诺塔

**定义：**汉诺塔（Tower of Hanoi），又称河内塔，是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
在这里插入图片描述
那么我们把n个盘子从A柱移动至C柱的问题可以表示为：
Hanio(n,A,B,C);
那么从上面的分析得出：
该问题可以分解成以下子问题：
第一步：将n-1个盘子从A柱移动至B柱（借助C柱为过渡柱）
第二步：将A柱底下最大的盘子移动至C柱
第三步：将B柱的n-1个盘子移至C柱（借助A柱为过渡柱）

分析：
1.当n = 1的时候，这时只有一个个盘子，那么直接将其移动至C就可以，移动过程为： A -> C
2.当n = 2的时候，这时候有两个盘子，那么在一开始移动的时候，我们需要借助B柱作为过渡的柱子，即将A柱最上面的那个小圆盘移至B柱，然后将A柱底下的圆盘移至C柱，最后将B柱的圆盘移至C柱。完整移动过程为：A -> B , A -> C , B -> C
3.当n>2时，我们可以大概分为三部分来理解这个过程：

①.把n上面的所有圆盘移动到B柱，C作为辅助，此时A是起始柱，B是目标柱，C只是作为辅助柱
②.把最大的圆盘n直接从A移动到C柱
③.把B柱上的圆盘全部移到C柱，A作为辅助，此时B是起始柱，C是目标柱，A只是作为辅助柱

代码如下：

void hanoi(int n, char a, char  b, char c) {
	if (1 == n)
	{
		printf("t%c--->>%cn", a, c);
	}
	else
	{
		hanoi(n-1, a, c, b);
		printf("t%c---->>%cn", a, c);
		hanoi(n-1, b, a, c);
	}
}
int main()
{
	int n = 0;
	printf("请输入数字：");

	scanf("%d", &n);
	hanoi(n, 'A', 'B', 'C');
	return 0;
}