递归的应用，这是新汉诺塔，在这个程序以及算法的设计实现中我学习到了很多的逻辑处理的能力，算法很有意思，值得好好的推敲学习。
前期准备工作（包括相关工具或所使用的原料等）eclipse-lunajdk1.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上
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])
全部程序实现：
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——>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
注意事项maketower是程序设计的重点注意在主程序中获取空闲位置放置current[k-1]只要是完成前两部分基本就可以根据target实现放置经验内容仅供参考，如果您需解决具体问题(尤其法律、医学等领域)，建议您详细咨询相关领域专业人士。作者声明：本教程系本人依照真实经历原创，未经许可，谢绝转载。
- 评论列表（网友评论仅供网友表达个人看法，并不表明本站同意其观点或证实其描述）
-