C language classic practice questions (3) - "Hanoi Tower (Hanoi)"

C语言趣味练习题——汉诺塔

---

---

汉诺塔介绍

汉诺塔（Hanoi） It is a classic problem that must be solved recursively,It comes from Indian mythology.God created the world when he created it3A diamond pillar,Stack them in order of size from bottom to top on the first column64片黄金圆盘.God commanded the Brahmins to put the disc
Rearrange from the bottom to the second post in order of size,And it is stipulated that only one disc can be moved at a time,在小圆盘上不能放大圆盘.
问：试编写,求解 n（n>1）个圆盘的汉诺塔问题.

---

一、Problem and method analysis

上图为 n( n>1 )The initial state of the Tower of Hanoi with a disc,Let's start with the simplest analysis

对于只有1个圆盘的汉诺塔问题,We just need to go directlyAA disc on the move toBcan be solved above

move_print(int n,char a,char b);//表示将第n个圆盘从a移动到b上

The function of the above function is to convert the firstn个圆盘从a移动到b上,并打印出来

Next, consider how to use recursionn个圆盘借助于 C 从 A 柱移动到 B 柱上

Hanoi(int n, char c,char b,char c);

接着,in order to find outnThe problem of a disc moving,It needs to be solved by mathematical induction：
将上面的 n-1 The disc is regarded as a whole,意思就是将 n The disc is divided into two parts：上面为 n-1 with the largest disc cap n 个,所以,nThe problem of moving a disc can be viewed as the following diagram

A -> C

A -> B

C -> B

二、Steps and code implementation

1.步骤

根据以上分析,可以将 n The solution of the tower of Hanoi is divided into 3步：
1：调用 Hanoi(n-1, a, c, b);Complete the first step above;
2：调用move_print(n, a, b);Complete the second step above;
3：调用Hanoi(n, c, b, a);Complete the third step above.

2.代码实现

代码如下（示例）：

#include <stdio.h>
void move_print(int n, char a, char b)
{
    
	printf("第%d个圆盘从 %c 移动到 %c\n", n, a, b);
}

void Hanoi(int n, char a, char b, char c)
{
    
	if (1 == n)
	{
    
		move_print(n, a, b);    // n为1时,直接由 A 移动到 B
	}
	else
	{
    
		Hanoi(n - 1, a, c, b);	// 将第 n-1 个圆盘借助 B 从 A 移动到 C
		move_print(n, a, b);    // 第 n 个圆盘从 A 移动到 B
		Hanoi(n - 1, c, b, a);	// 将第 n-1 个圆盘借助 A 从 C 移动到 B
	}
}

int main()
{
    
	int n = 0;
	printf("Please customize the number of discs:");
	scanf("%d", &n);
	printf("移动%dThe disc steps are as follows：\n", n);
	Hanoi(n, 'A', 'B', 'C');
	return 0;
}

3.运行结果图

---

总结

以上就是CThe realization of the tower of Hanoi, a classic example in the language.（如有错误请指出）
If you find it helpful, give it a like and make it difficult to add a follow. Let's go~（后续会持续更新！）