eclipse-luna
jdk1.7
应用新汉诺塔游戏假设有不同大小的光碟标签ñ从1到n按照它们的大小的升序排列。在初始状态是随机的N光盘上三极堆积，现在你必须要了解最少的动作把初始状态的目标。该举措的要求为以下几种： 1）你只能一次移动一个圆盘;2）较大的光盘是不允许在一个较小的一栈 current和target分别表示开始状态的结束状态。
算法设计思路
基本的汉诺塔移动算法：汉诺塔的分析：第一，把a上的n-1个盘通过c移动到b。第二，把a上的最下面的盘移到c。第三，因为n-1个盘全在b上了，所以把b当做a重复以上步骤就好了。
形成一摞的k-1盘子的算法：make_tower(k,current) if k=1 then return if k=2 if current[k]≠current[k-1] then 将k移到k+1上 returnif 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]) returnmake_tower(k-1,current)if k和k-1不在同一个位置 then temp←除k和k-1的位置 Hanoi(current,k-1,current[k-1],temp,current[k])
全部程序实现：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]; } }}
运行结果：move1 disk 1:C——>Bmove2 disk 2:C——>Amove3 disk 1:B——>Amove4 disk 3:C——>Bmove5 disk 1:A——>Cmove6 disk 2:A——>Bmove7 disk 1:C——>Bmove8 disk 1:B——>Cmove9 disk 2:B——>Amove10 disk 1:C——>Amove11 disk 3:B——>Cmove12 disk 1:A——>Bmove13 disk 2:A——>Cmove14 disk 1:B——>Cmove15 disk 4:B——>Amove16 disk 1:C——>Amove17 disk 2:C——>Bmove18 disk 1:A——>Bmove19 disk 3:C——>Amove20 disk 1:B——>Cmove21 disk 2:B——>Amove22 disk 1:C——>Amove23 disk 5:B——>Cmove24 disk 1:A——>Cmove25 disk 2:A——>Bmove26 disk 1:C——>Bmove27 disk 3:A——>Cmove28 disk 1:B——>Amove29 disk 2:B——>Cmove30 disk 1:A——>Cmove31 disk 4:A——>Bmove32 disk 1:C——>Bmove33 disk 2:C——>Amove34 disk 1:B——>C
maketower是程序设计的重点
注意在主程序中获取空闲位置放置current[k-1]
只要是完成前两部分基本就可以根据target实现放置