汉诺塔——递归算法（c语言实现）-Toy模板网

这篇具有很好参考价值的文章主要介绍了汉诺塔——递归算法（c语言实现）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

每日一题

文章来源地址https://www.toymoban.com/news/detail-693226.html

文章目录

汉诺塔问题：

一、递归算法

二、解决汉诺塔问题

1.找规律，确定思路

2.代码实现

总结

汉诺塔问题：

1.有三根杆(编号A、B、C)
2. 在A杆自下而上、由大到小按顺序放置n个金盘
3.把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。

操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，
小盘在上，操作过程中盘子可以置于A、B、C任一杆上。

c语言递归解决汉诺塔,算法,c#

提示：以下是本篇文章正文内容，下面案例可供参考

一、递归算法

递归算法是算法中很常用的一种方法，是一种逆行思维，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

大事化小，由小引大。

通俗的讲：就是找规律（类似数学归纳法）

二、解决汉诺塔问题

1.找规律，确定思路

(1）当 n = 3 时 (详细步骤)

0. A(1.2.3),B(), C()

1.A->C A(2.3), B(), C(1)

2.A->B A(3), B(2), C(1)

3.C->B A(3), B(1.2), C()

4.A->C A(), B(1.2), C(3)

5.B->A A(1), B(2), C(3)

6.B->C A(1), B(), C(2.3)

7.A->C A(), B(), C(1.2.3)

可以发现：可分为两步 1~~~4和4~~7

所以总结可得：

汉诺塔解题步骤：
第一步：
把 n-1 个模块从塔 1 移动到塔 2
把第 n 个模块从塔 1 移动到塔 3
第二步:
把 n-1 个模块从塔 2 移动到塔 3

所以求 n = 4 时

如下：

c语言递归解决汉诺塔,算法,c#

2.代码实现

代码如下（示例）：

#include <stdio.h>
int count;
void move(char A, char C, int n)
{
	printf("把第%d个圆盘从%c->%c\n", n, A, C);
	count++;
}

void Hanno(char A, char B, char C, int n)
{
	if (n == 1)
	{
		move(A, C, n);
	}
	else
	{
		//将n-1个圆盘从A柱借助于C柱移动到B柱上
		Hanno(A, C, B, n - 1);
		//将A柱子最后一个圆盘移动到C柱上
		move(A, C, n);
		//将n-1个圆盘从B柱借助于A柱移动到C柱上
		Hanno(B, A, C, n - 1);
	}
}

int main()
{
	int n = 0;
	printf("输入A柱子上的圆盘个数：");
	scanf("%d", &n);
	//将n个圆盘从A柱借助于B柱移动到C柱上
	Hanno('A', 'B', 'C', n);
	printf("一共移动了%d次圆盘",count);
	return 0;
}

运行结果

输入A柱子上的圆盘个数：3
把第1个圆盘从A--->C
把第2个圆盘从A--->B
把第1个圆盘从C--->B
把第3个圆盘从A--->C
把第1个圆盘从B--->A
把第2个圆盘从B--->C
把第1个圆盘从A--->C
一共移动了7次圆盘
--------------------------------

输入A柱子上的圆盘个数：4
把第1个圆盘从A--->B
把第2个圆盘从A--->C
把第1个圆盘从B--->C
把第3个圆盘从A--->B
把第1个圆盘从C--->A
把第2个圆盘从C--->B
把第1个圆盘从A--->B
把第4个圆盘从A--->C
把第1个圆盘从B--->C
把第2个圆盘从B--->A
把第1个圆盘从C--->A
把第3个圆盘从B--->C
把第1个圆盘从A--->B
把第2个圆盘从A--->C
把第1个圆盘从B--->C
一共移动了15次圆盘