汉诺塔(Tower of Hanoi)源于印度传说中，大梵天创造世界时造了三根金钢石柱子，其中一根柱子自底向上叠着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。引自维基百科
递归求解
若给汉诺塔传说中三根柱子分别用英文字母a,b,c命名，其中只有a柱子摆放n片圆盘(1<=n<=100000), 若要把a柱子上的所有圆盘转移到c柱子上，问最少需要移动多少次圆盘。
移动圆盘的规则如下：
- 每次只能移动一片圆盘
- 直径大的圆盘必须摆放在直径小的圆盘之上
递归求解其实就是不断降低问题规模的过程，将b柱子的n-1个圆盘移至c何尝不重复上述两点的过程。
void Hanoi(int n, char a, char b, char c)
{
if(n == 1)
{
Move(a, c);
}
else
{
Hanoi(n-1, a, c, b); /*将a柱子n-1个圆盘移动到b柱子*/
Move(a, c); /*将a剩下的一个圆盘移动到c*/
Hanoi(n-1, b, a, c); /*再把b上暂时放着的n-1个圆盘移动到c*/
}
}
void Move(char a, char b)
{
printf("Move 1 disk: %c ---------> %c\n", a, b);
}上方代码可以得出汉诺塔移动圆盘次数的递推关系：
- Hanoi(n) = 1 , n =1 ;
- Hanoi(n) = 2 * Hanoi(n-1) + 1, n>1;
令b(n) = Hanoi(n)+1，可以得出b(n)是一个以2为底，公比为2的等比数列。由此可得，
- b(n) = 2n， n>0
- Hanoi(n) = 2n - 1, n>0
图形化结果
效果图：
分析
仔细看图我们发现图形呈对称形状且为奇数，且每行相差为2的倍数。也就是说我们只要把最上面的行补上“空格”就可以使图案对称。
我们以最原始的状态为例，把所有空格换成“0”：
原始图形：
A 0000A0000
AAA 000AAA000
AAAAA -> 00AAAAA00
AAAAAAA 0AAAAAAA0
AAAAAAAAA AAAAAAAAA有没有发现图案成了一个二维数组呢
图形变数组
上面我们引入了二维数组的思路，但是二维数组用来放一个图形太麻烦了。
于是我们继续找规律，我们发现：我们可以把图形每一行看作一个整体，用其所含“A”的数量表示。如下所示
0000A0000 000000000 000000000 1 0 0
000AAA000 000000000 000000000 3 0 0
00AAAAA00 000000000 000000000 -> 5 0 0
0AAAAAAA0 000000000 000000000 7 0 0
AAAAAAAAA 000000000 000000000 9 0 0是不是简单了很多，这样在每次操作时，只要把数字做移动就可以了。
输出图形
现在过程已经基本清晰：首先递归求解，在移动步骤后移动二维数组的参数，然后输出图形即可。
但是要怎么把数组变成图形呢，其实很简单。
/**
* 输出数组里的每个数据变成图形
* @param num 具体数据
* @param max 图形最大的数（max >= num）
* @return
*/
public String becomeA(int num, int max) {
String tmpStr = "";
for (int i = 0; i < ((max-num)/2); i++) {
tmpStr += " ";
}
for (int i = 0; i < num; i++) {
tmpStr += "A";
}for (int i = 0; i < ((max-num)/2); i++) {
tmpStr += " ";
}
return tmpStr;
}如图中代码所示，只需要把原始图形每一行的长度及图形参数带入其中，就可以返回出一个包含图形的字符串，然后挨个输出就可以了。
图形的移动
图形的移动也是这次作业中最难的了，简单地说就是把所要记录初始位置和最终位置的矩阵坐标，然后将这两个数换一下位置就好了。但是，所要换位置的两个数是一直变得。
/**
* 移动汉诺塔图形及其所代表的数据
* @param A
* @param C
* @param arr 存放汉诺塔形状的二维数组
*/
private void move(char A, char C, int[][] arr) { //执行最大盘子的从A-C的移动
int m = 5, n = 5, tmp = 0, i = 0, j = 0; //m、n分别代表要交换的柱子的序号 tmp为交换时的临时数据 i、j分别代表要交换的柱子上的位置
switch (A) {
case 'a':
m = 0;
i = x += 1;
break;
case 'b':
m = 1;
i = y += 1;
break;
case 'c':
m = 2;
i = z += 1;
break;
default:
break;
}
switch (C) {
case 'a':
n = 0;
j = x -= 1;
break;
case 'b':
n = 1;
j = y -= 1;
break;
case 'c':
n = 2;
j = z -= 1;
break;
default:
break;
}
count += 1;
tmp = arr[i][m];
arr[i][m] = arr[j+1][n];
arr[j+1][n] = tmp;
System.out.println("第" + count + "次 move:" + A + "--->" + C);
System.out.println();
output(arr);
System.out.println("--------------------------------------------------------------------------------");
}在代码中，我是首先使用了x y z三个参数分别记录每一列为“0”的最低的位置。m n则分别代表需要移动的两列的序号（代表横坐标），而i j根据m n的不同获取相应x y z的值（表示纵坐标）。
这样也就将两个点表示了出来。移动也变得简单了。
思路总结
- 创建一个存放图形数据的二维数组
- 开始递归求解
- 在move(a,c)中添加移动及生成图形的程序
代码展示
class Hanoi {
int count = 0; //计算步数
int x = 0, y = 0, z = 0;
int arrMax = 0; //确定图形最大的数
public static void main(String[] args) {
Hanoi hanoi = new Hanoi();
int hanoiNum = 5; //汉诺塔的层数
int[][] hanArr = hanoi.creatArr(hanoiNum);
hanoi.attach(hanArr);
hanoi.hanoi(hanoiNum, 'a', 'b', 'c', hanArr);
}
/**
* 创建一个 列数为3 行数为num 的二维数组表示汉诺塔的形状
* @param num 汉诺塔的层数
* @return
*/
public int[][] creatArr(int num) {
return new int[num][3];
}
/**
* 初始化汉诺塔形状数据 以及确定图形每列可以编辑的位置
* @param arr 存放汉诺塔形状的二维数组
*/
public void attach(int[][] arr) {
for (int i = 0; i < arr.length; i++) {
arr[i][0] = 2*i+1;
}
x = -1;
y = arr.length-1;
z = arr.length-1;
arrMax = arr[arr.length-1][0];
}
/**
* 输出汉诺塔图形
* @param arr 存放汉诺塔形状的二维数组
*/
public void output(int[][] arr) {
// int arrMax = arr[arr.length-1][0]; // 最大的点数9
for(int i = 0; i < arr.length; i++){ //行数 5
for(int j = 0; j < arr[i].length; j++){ //列数 3
System.out.print(becomeA(arr[i][j],arrMax) + "\t|\t");
}
System.out.println();
}
}
/**
* 输出数组里的每个数据变成图形
* @param num 具体数据
* @param max 图形最大的数（max >= num）
* @return
*/
public String becomeA(int num, int max) {
String tmpStr = "";
for (int i = 0; i < ((max-num)/2); i++) {
tmpStr += " ";
}
for (int i = 0; i < num; i++) {
tmpStr += "A";
}for (int i = 0; i < ((max-num)/2); i++) {
tmpStr += " ";
}
return tmpStr;
}
/**
* 实现汉诺递归
* @param n 汉诺塔的层数
* @param A 最左边的柱子
* @param B 中间的柱子
* @param C 最右边的柱子
* @param arr 存放汉诺塔形状的二维数组
*/
public void hanoi(int n, char A, char B, char C, int[][] arr) {
if (n == 1) {
move(A, C, arr);
} else {
hanoi(n - 1, A, C, B, arr);//步骤1 按ACB数序执行N-1的汉诺塔移动
move(A, C, arr); //步骤2 执行最大盘子移动
hanoi(n - 1, B, A, C, arr);//步骤3 按BAC数序执行N-1的汉诺塔移动
}
}
/**
* 移动汉诺塔图形及其所代表的数据
* @param A
* @param C
* @param arr 存放汉诺塔形状的二维数组
*/
private void move(char A, char C, int[][] arr) { //执行最大盘子的从A-C的移动
int m = 5, n = 5, tmp = 0, i = 0, j = 0; //m、n分别代表要交换的柱子的序号 tmp为交换时的临时数据 i、j分别代表要交换的柱子上的位置
switch (A) {
case 'a':
m = 0;
i = x += 1;
break;
case 'b':
m = 1;
i = y += 1;
break;
case 'c':
m = 2;
i = z += 1;
break;
default:
break;
}
switch (C) {
case 'a':
n = 0;
j = x -= 1;
break;
case 'b':
n = 1;
j = y -= 1;
break;
case 'c':
n = 2;
j = z -= 1;
break;
default:
break;
}
count += 1;
tmp = arr[i][m];
arr[i][m] = arr[j+1][n];
arr[j+1][n] = tmp;
System.out.println("第" + count + "次 move:" + A + "--->" + C);
System.out.println();
output(arr);
System.out.println("--------------------------------------------------------------------------------");
}
}最后更新 2019-05-30