汉诺塔的递归算法

发表于 更新于 分类于
本文字数： 1.5k 阅读时长 ≈ 1 分钟

最早发明这个问题的人是法国数学家爱德华·卢卡斯。传说越南河内某间寺院有三根银棒，上串 64 个金盘。寺院里的僧侣依照一个古老的预言，以上述规则移动这些盘子；预言说当这些盘子移动完毕，世界就会灭亡，上述又称梵天寺之塔问题。但不知道是卢卡斯自创的这个传说，还是他受他人启发。这个传说有若干变体：寺院换成修道院、僧侣换成修士等等。寺院的地点众说纷纭，其中一说是位于越南的河内，所以被命名为“河内塔”。另外亦有“金盘是创世时所造”、“僧侣们每天移动一盘”之类的背景设定。

描述

汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

规律

归纳可得，当移动的盘子为n个时，移动的次数为2^n - 1。

调用方法的栈机制

从主线程开始调用方法/函数进行不停的压栈和出栈操作，函数的调用就是将函数压入栈中，函数的结束就是函数出栈的过程，这样就保证了方法调用的顺序流，即当函数出现多层嵌套时，需要从外到内一层层把函数压入栈中，最后栈顶的函数先执行结束（最内层的函数先执行结束）后出栈，再倒数第二层的函数执行结束出栈，到最后，第一个进栈的函数调用结束后从栈中弹出回到主线程，并且结束。

递归算法的实现(Java语言描述)

实现该递归算法可以分为三步走，首先需要把n-1个盘子从A柱移到B柱(C柱作为辅助)；然后再将第n个盘子/最大的盘子从A柱移动到C柱；最后将B柱上的n-1个盘子移动到C柱上(A柱作为辅助)即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*程序目的：利用汉诺塔函数来求出不同盘子移动的步骤
*2019-10-24 Summer
**/
import java.io.*;
public class Summer{
public static void main(String args []){
int j;
String str;
static int m =0;//标记移动次数
BufferedReader keyin=new BufferedReader(new InputStreamReader(System.in));
System.out.print("请输入盘子数量:");
str=keyin.readline();
j=Integer.parseInt(str);
hanoi(j,1,2,3);
}
public static void hanoi(int n,int p1,int p2,int p3){
if(n==1){ //圆盘仅剩一个时，直接移动到C柱。
 System.out.println("第"+(++m)+"次移动，从"+p1+"移动到"+p3+"。")
 }else{//递归算法分三步走
  hanoi(n-1,p1,p3,p2); //hanoi(int n,int p1,int p2,int p3)中，形参p2所在的位置表示过渡参数。
  System.out.println("第"+(++m)+"次移动，从"+p1+"移动到"+p3+"。");
  hanoi(n-1,p2,p1,p3);
 }
}
相关文章