使用递归的汉诺塔
汉诺塔
汉诺塔是一个数学谜题，由三座塔（桩）和多个如图所示的圆环组成。
这些圆环大小不一，按升序堆叠，即较小的圆环位于较大的圆环之上。该谜题还有其他变体，其中圆盘数量增加，但塔的数量保持不变。
规则
任务是将所有圆盘移动到另一个塔中，且不违反排列顺序。汉诺塔需要遵循以下几条规则：−
- 每次只能在塔之间移动一个圆盘。
- 只能移除"顶部"的圆盘。
- 大圆盘不能放在小圆盘上方。
以下是使用三个圆盘解决汉诺塔谜题的动画演示。
使用 n 个圆盘的汉诺塔谜题最少可以用 2n−1 步解决。本演示显示，解决包含 3 个圆盘的难题需要 23 - 1 = 7 步。
算法
要编写汉诺塔算法，首先我们需要学习如何使用较少的圆盘数量（例如 1 或 2 个）来解决这个问题。我们为三个塔分别标记了名称、源、目标 和 辅助（仅用于帮助移动圆盘）。如果我们只有一个圆盘，那么它可以轻松地从源柱移动到目标柱。
如果我们有两个圆盘 −
- 首先，我们将较小的（顶部）圆盘移动到辅助柱。
- 然后，我们将较大的（底部）圆盘移动到目标柱。
- 最后，我们将较小的圆盘从辅助柱移动到目标柱。
现在，我们可以设计一个包含两个以上圆盘的汉诺塔算法了。我们将圆盘堆分成两部分。最大的盘子（第 n 个盘子）位于一个部分，所有其他 (n-1) 个盘子位于另一个部分。
我们的最终目标是将盘子 n 从源移动到目标，然后将所有其他 (n1) 个盘子放到上面。我们可以想象以递归的方式对所有给定的盘子集合应用相同的操作。
步骤如下：−
步骤 1 − 将 n-1 个盘子从源移动到辅助步骤 2 − 将第 n 个盘子从源移动到目标步骤 3 −将 n-1 个盘子从aux移动到dest
汉诺塔的递归算法可以如下实现 −
START
Procedure Hanoi(disk, source, dest, aux)
IF disk == 1, THEN
move disk from source to dest
ELSE
Hanoi(disk - 1, source, aux, dest) // Step 1
move disk from source to dest // Step 2
Hanoi(disk - 1, aux, dest, source) // Step 3
END IF
END Procedure
STOP
示例
以下是该方法在各种编程语言中的实现 −
#include <stdio.h>
void hanoi(int n, char from, char to, char via) {
if(n == 1){
printf("Move disk 1 from %c to %c
", from, to);
}
else{
hanoi(n-1, from, via, to);
printf("Move disk %d from %c to %c
", n, from, to);
hanoi(n-1, via, to, from);
}
}
int main() {
int n = 3;
char from = 'A';
char to = 'B';
char via = 'C';
//calling hanoi() method
hanoi(n, from, via, to);
}
#include <iostream>
using namespace std;
void hanoi(int n, char from, char to, char via) {
if(n == 1){
cout<<"Move disk 1 from "<<from<<" to "<<to<<endl;
}
else{
hanoi(n-1, from, via, to);
cout<<"Move disk "<<n<<" from "<<from<<" to "<<to<<endl;
hanoi(n-1, via, to, from);
}
}
int main() {
int n = 3;
char from = 'A';
char to = 'B';
char via = 'C';
//calling hanoi() method
hanoi(n, from , via, to);
}
import java.util.*;
public class Demo {
public static void hanoi(int n, String from, String to, String via) {
if(n == 1){
System.out.println("Move disk 1 from " + from + " to " + to);
}
else{
hanoi(n-1, from, via, to);
System.out.println("Move disk " + n + " from " + from + " to " + to);
hanoi(n-1, via, to, from);
}
}
public static void main(String[] args) {
int n = 3;
String from = "A";
String to = "B";
String via = "C";
//calling hanoi() metod
hanoi(n, from, via, to);
}
}
def hanoi(n, f, to, via):
if n == 1:
print("Move disk 1 from",f,"to",to);
else:
hanoi(n-1, f, via, to)
print("Move disk",n,"from",f,"to",to);
hanoi(n-1, via, to, f)
n = 3
f = 'A'
to = 'B'
via = 'C'
hanoi(n, f, via, to)
输出
Move disk 1 from A to C Move disk 2 from A to B Move disk 1 from C to B Move disk 3 from A to C Move disk 1 from B to A Move disk 2 from B to C Move disk 1 from A to C
