问题描述

有三根柱子，从左到右依次为A、B、C柱，A上有 n 个盘子，盘子从上到下依次变大。起始时所有盘子都在 A 柱上，目标是通过将这些盘子按照以下规则移动到 C 柱上：

1. 每次只能移动一个盘子。
2. 不能将较大的盘子放在较小的盘子上。
3. 使用中间的柱子（B）作为辅助柱子。

递归思想

1. 当只有一个盘子时，直接将这个盘子从起始柱子移动到目标柱子。
2. 当有多个盘子时，可以将问题分解为两个部分：
   • 先将 n-1 个盘子从起始柱子移动到辅助柱子（中途将目标柱子当作辅助柱子）。
   • 然后将最大的盘子从起始柱子移动到目标柱子。
   • 最后将那 n-1 个盘子从辅助柱子移动到目标柱子（中途将起始柱子当作辅助柱子）。

递归函数的实现

# include <stdio.h>

void move(char pos1,char pos2){
	printf("%c->%c",pos1,pos2);
}
//pos1起始位置（A柱）
//pos2中转位置（B柱）
//pos3最终位置（C柱）
void Hanoi(int n,char pos1,char pos2,char pos3){
	if(n=1)
		return 1;
	else{
		Hanoi(n-1,pos1,pos3,pos2);
		move(pos1,pos3);
		Hanoi(n-1,pos2,pos1,pos3);   
	}
}

int main(){
	int n=0;
	scanf("%d",&n);
	Hanoi(n,'A','B','C');
	return 0;
}

代码详解

示例，当 n = 4 时，汉诺塔问题的递归过程如下。逐步将问题分解为更小的子问题来解决。

问题描述：

我们有 4 个盘子在柱子 A 上，要把它们移动到柱子 C，柱子 B 作为辅助柱子。按照递归的思想，可以分解为：

将前 3 个盘子从 A 移动到 B，C 作为辅助柱子。 将第 4 个盘子从 A 移动到 C。 将前 3 个盘子从 B 移动到 C，A 作为辅助柱子。

详细步骤：

我们通过逐步展开递归，来看每一步发生了什么。

1. 将前 3 个盘子从 A 移动到 B（递归调用 hanoi(3, A, C, B)）：
   • 1.1 将前 2 个盘子从 A 移动到 C（递归调用 hanoi(2, A, B, C)）：
     • 1.1.1 将前 1 个盘子从 A 移动到 B（递归调用 hanoi(1, A, C, B)）：
       • 移动盘子 1 从 A 到 B。
     • 1.1.2 将第 2 个盘子从 A 移动到 C。
     • 1.1.3 将盘子 1 从 B 移动到 C。
   • 1.2 将第 3 个盘子从 A 移动到 B。
   • 1.3 将前 2 个盘子从 C 移动到 B（递归调用 hanoi(2, C, A, B)）：
     • 1.3.1 将前 1 个盘子从 C 移动到 A（递归调用 hanoi(1, C, B, A)）：
       • 移动盘子 1 从 C 到 A。
     • 1.3.2 将第 2 个盘子从 C 移动到 B。
     • 1.3.3 将盘子 1 从 A 移动到 B。
2. 将第 4 个盘子从 A 移动到 C。
3. 将前 3 个盘子从 B 移动到 C（递归调用 hanoi(3, B, A, C)）：
   • 3.1 将前 2 个盘子从 B 移动到 A（递归调用 hanoi(2, B, C, A)）：
     • 3.1.1 将前 1 个盘子从 B 移动到 C（递归调用 hanoi(1, B, A, C)）：
       • 移动盘子 1 从 B 到 C。
     • 3.1.2 将第 2 个盘子从 B 移动到 A。
     • 3.1.3 将盘子 1 从 C 移动到 A。
   • 3.2 将第 3 个盘子从 B 移动到 C。
   • 3.3 将前 2 个盘子从 A 移动到 C（递归调用 hanoi(2, A, B, C)）：
     • 3.3.1 将前 1 个盘子从 A 移动到 B（递归调用 hanoi(1, A, C, B)）：
       • 移动盘子 1 从 A 到 B。
     • 3.3.2 将第 2 个盘子从 A 移动到 C。
     • 3.3.3 将盘子 1 从 B 移动到 C。

最后移动顺序

Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C
Move disk 3 from A to B
Move disk 1 from C to A
Move disk 2 from C to B
Move disk 1 from A to B
Move disk 4 from A to C
Move disk 1 from B to C
Move disk 2 from B to A
Move disk 1 from C to A
Move disk 3 from B to C
Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C