JAVA：New towers of Hanoi
1、应用新汉诺塔游戏
假设有不同大小的光碟标签ñ从1到n按照它们的大小的升序排列。在初始状态是随机的N光盘上三极堆积，现在你必须要了解最少的动作把初始状态的目标。该举措的要求为以下几种： 1）你只能一次移动一个圆盘;2）较大的光盘是不允许在一个较小的一栈
current和target分别表示开始状态的结束状态。
2、算法设计思路
3、基本的汉诺塔移动算法：
汉诺塔的分析：
第一，把a上的n-1个盘通过c移动到b。
第二，把a上的最下面的盘移到c。
第三，因为n-1个盘全在b上了，所以把b当做a重复以上步骤就好了。
4、形成一摞的k-1盘子的算法：
make_tower(k,current)
if k=1 then return
if k=2
if current[k]≠current[k-1]
then 将k移到k+1上
return
if k,k-1,k-2分别位于不同位置
then make_tower(k-2,current)
将k-1移到k上
Hanoi(current,k-2,current[k-2],current[k-1],current[k])
return
make_tower(k-1,current)
if k和k-1不在同一个位置
then temp←除k和k-1的位置
Hanoi(current,k-1,current[k-1],temp,current[k])
5、全部程序实现：
package ch2.divide;
public class NewHanoi {
public static int count = 0;
// /这个地方的用途就是找到A杆顶端要移动的盘子的编号i
// //将 这个盘子移动到C杆上，修改current[i]的值为C
// //累加移动盘子的次数然后输出A——>C的信息
// //找出当前需要移动的杆子（根据ABC符号进行识别）的顶部盘子的编号i
// //修改当前编号的盘子所在的杆子的符号
// ---这个函数的作用是寻找发现当前移动的盘子所在杆子的状态变化的一个记录修改-----//
private static int pickTopDisk(char[] current, char a) {
int i = 1;
while (current[i] != a) {
i++;
}
return i;
}
// 汉诺塔基本的搬运算法
public static void hanoi(char[] current, int n, char A, char B, char C) {
if (n == 1) {
int i;
i = 1;
i = pickTopDisk(current, A);
current[i] = C;
count++;
// /只有一块圆盘 ， 直接移至c
System.out.println("move" + count + " disk " + i + ":" + A + "——>" + C);
return;
}
// /第一，把a上的n-1个盘通过c移动到b
hanoi(current, n - 1, A, C, B);
current[n] = C;
// 这里第n个盘子就是下标为n-1，一定要记在心里
count++;
System.out.println("move" + count + " disk " + n + ":" + A + "——>" + C);
hanoi(current, n - 1, B, A, C);
}
////将小于目标盘的所有盘摞成一个塔的形状（小盘位于大盘之上）
public static void makeTower(char[] c, int n) {
char temp; //临时的字符声明
//------n=1和n=2特殊情况可以直接处理--------///
if (n == 1)
return;
///将1号盘子移动到2号盘子之上
if (n == 2) {
if (c[1] != c[2]) {
count++;
System.out.println("move" + count + " disk " + 1 + ":" + c[1] + "——>" + c[2]);
c[1] = c[2];
}
return;
}
//情况1------n=1和n=2特殊情况可以直接处理--------///
//情况2------n，n-1，n-2都不在同一个盘子上--------///
if (c[n] != c[n - 1] && c[n] != c[n - 2] && c[n - 1] != c[n - 2]) {
makeTower(c, n - 2);
// 将n-1移到n上
count++;
System.out.println("move" + count + " disk " + (n - 1) + ":" + c[n - 1] + "——>" + c[n]);
temp = c[n - 1];
c[n - 1] = c[n];
hanoi(c, n - 2, c[n - 2], temp, c[n-1]);
return;
}
//情况2------n，n-1，n-2都不在同一个盘子上--------///
makeTower(c, n - 1); //这个地方自由的递归实现不断的细化减少盘子的编号
///这个地方是一般情况下，我们会找到一个空余的位置利用hanoi的基本搬运算法把所有的n-1个盘子移动过去
if (c[n - 1] != c[n]) {
temp = (char) ('A' + 'B' + 'C' - c[n] - c[n - 1]);
hanoi(c, n - 1, c[n - 1], temp, c[n]);
}
}
public static void main(String[] args) {
///字符数组中的0用来占据位置作为数组中国0这个位置的站位字符 在实际的操作中不使用
char[] current = { 0, 'C', 'C', 'C', 'B', 'B' };
char[] target = { 0, 'C', 'A', 'C', 'B', 'C' };
int k = 5;
char temp;
//找到第一个最大的不符合要求的盘子
while (current[k] == target[k] && k > 0)
k--;
// 如果k>2，把1...k-1移到k-1上 形成一摞有序的k-1盘子
if (k > 2)
makeTower(current, k - 1);
while (k > 1) {
///腾出目标位置
if (current[k] != target[k]) {
if (current[k] == current[k - 1]) {
////如果k-1个盘子在current[k]上面，将其移动到空闲的杆子上面
temp = (char) ('A' + 'B' + 'C' - current[k] - target[k]);
hanoi(current, k - 1, current[k - 1], target[k], temp);
} else if (current[k - 1] == target[k]) {
////如果k-1个盘子在target[k]上面，将其移动到空闲的杆子上面
temp = (char) ('A' + 'B' + 'C' - current[k] - target[k]);
hanoi(current, k - 1, current[k - 1], current[k],temp);
}
count++;
///将第k个盘子移动到目标位置
System.out.println("move" + count + " disk " + k + ":" + current[k] + "——>" + target[k]);
current[k] = target[k];
}
k--;
}
if (current[1] != target[1]) {
count++;
System.out.println("move" + NewHanoi.count + " disk " + 1 + ":" + current[1] + "——>" + target[1]);
current[1] = target[1];
}
}
}
6、运行结果：
move1 disk 1:C——>B
move2 disk 2:C——>A
move3 disk 1:B——>A
move4 disk 3:C——>B
move5 disk 1:A——>C
move6 disk 2:A——>B
move7 disk 1:C——>B
move8 disk 1:B——>C
move9 disk 2:B——>A
move10 disk 1:C——>A
move11 disk 3:B——>C
move12 disk 1:A——>B
move13 disk 2:A——>C
move14 disk 1:B——>C
move15 disk 4:B——>A
move16 disk 1:C——>A
move17 disk 2:C——>B
move18 disk 1:A——>B
move19 disk 3:C——>A
move20 disk 1:B——>C
move21 disk 2:B——>A
move22 disk 1:C——>A
move23 disk 5:B——>C
move24 disk 1:A——>C
move25 disk 2:A——>B
move26 disk 1:C——>B
move27 disk 3:A——>C
move28 disk 1:B——>A
move29 disk 2:B——>C
move30 disk 1:A——>C
move31 disk 4:A——>B
move32 disk 1:C——>B
move33 disk 2:C——>A
move34 disk 1:B——>C
