学步园

我的 Hanoi 算法Java实现。

通过三个函数，分别对Hanoi进行递归、非递归和非递归规律实现。

程序如下：

/*
 * Hanoi塔游戏 问题描述：
 * 汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。
 * 大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照
 * 大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小
 * 顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在
 * 三根柱子之间一次只能移动一个圆盘。
 * 
 * fuction:实现 hanoi塔
 *             1.递归实现
 *             2.非递归实现
 * author:iGeneral
 * date:2013.04.26
 * 
 * expe:
 *         1.注意：塔的状态:当status=1时，表示可以直接将该Disk移动到目标塔
 *                 而不是用Disk的id来判断输出
 *         2.System.out.println();
          System.out.println((int)3.3%3);
          没有(int)时，输出：0.299999
          加上(int)后，输出：0
 */
package part03.chapter10;

import java.util.Scanner;

public class _2exercise {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入Hanoi碟子的数量：");
        int diskNum = scanner.nextInt();
        Hanoi hanoi = new Hanoi();
        System.out.println("递归实现：");
        hanoi.play_recursive(diskNum, 'A', 'B', 'C');
        System.out.println("非递归实现(模仿递归思想)：");
        hanoi.play_non_recursive(diskNum);
        System.out.println("非递归实现(根据Hanoi规律)：");
        hanoi.play_regular(diskNum);

    }

}

class Hanoi {

    // 递归实现
    public void play_recursive(int num, char A, char B, char C) {
        if (num == 1) {
            System.out.println(A + " -> " + C);
            return;
        } else {
            play_recursive(num - 1, A, C, B);
            System.out.println(A + " -> " + C);
            play_recursive(num - 1, B, A, C);
        }

    }

    // 非递归实现：模仿递归思想
    public void play_non_recursive(int diskNum) {
        Stack stack = new Stack();
        stack.push(new Disk(diskNum, 'A', 'B', 'C'));
        Disk popDisk = null;
        while ((popDisk = stack.pop()) != null) {
            if (popDisk.status == 1) {
                System.out.println(popDisk.A + " -> " + popDisk.C);
            } else {
                // 反顺序添加
                // 将执行移动 popDisk 的下一步的Disk添加到Stack
                stack.push(new Disk(popDisk.status - 1, popDisk.B, popDisk.A,
                        popDisk.C));
                // 将一个status为 "1" 且移动顺序与 popDisk 相同的Disk 添加到Stack中
                stack.push(new Disk(1, popDisk.A, popDisk.B, popDisk.C));
                // 将执行移动 popDisk 的前一步的Disk添加到Stack中
                stack.push(new Disk(popDisk.status - 1, popDisk.A, popDisk.C,
                        popDisk.B));
            }
        }
    }

    // 非递归实现：根据Hanoi规律
    public void play_regular(int diskNum) {

        // 根据规律，需要根据 Disk 的个数，多塔的位置进行调整
        // 塔的个数为偶数时，将三个塔按“A->B->C”的顺序排列成三角形
        // 塔的个数为奇数时，将三个塔按"A->C->B"的顺序排列成三角形
        // 将diskNum个Disk按”上小下大“的顺序放在A塔中（堆栈实现），同时将B塔和C塔置空
        Stack_play_regular A = new Stack_play_regular('A');
        Stack_play_regular B = new Stack_play_regular('B');
        Stack_play_regular C = new Stack_play_regular('C');
        for (int i = diskNum; i > 0; i--) {
            A.push(i);
        }
        // 将三个塔模拟成三角形形状排列
        Stack_play_regular[] towers = new Stack_play_regular[3];
        towers[0] = A;
        if (diskNum % 2 == 0) {
            towers[1] = B;
            towers[2] = C;
        } else {
            towers[1] = C;
            towers[2] = B;
        }
        // 最小Dish所在的塔，通过该塔在towers中的
        int towerOfMinimunDisk = 0;
        // 根据证明：n个Disk移动完成至少需要2^n-1次
        // 不断交替进行以下两步
        // 将最小的Disk按以上塔的顺序下移到下一个塔
        // 对除了最小Disk所在的塔的另外两个塔进行操作，可能出现两种情况
        // 情况一：一个塔中没有Disk，此时将存在Disk的塔最上面的Disk移动到没Disk的塔上
        // 情况二：两个塔都有Disk，此时对他们最上面的塔进行比较，将较小的Disk移动到较大的Disk上
        // 不会存在两个塔都没有Disk的情况，除非移动已经完成或未开始或只有一个盘子时的移动
        int ii = 0;
        for (int i = 0; i < (Math.pow(2, diskNum) - 1);) {// --------------注意在此处不进行i++
            // 取出三个塔，使代码更清晰
            Stack_play_regular tower = towers[towerOfMinimunDisk];
            Stack_play_regular tower_1 = towers[(int) ((towerOfMinimunDisk + 1) % 3)];
            Stack_play_regular tower_2 = towers[(int) ((towerOfMinimunDisk + 2) % 3)];
            // 移动最小的盘子
            System.out.println(tower.name + " -> " + tower_1.name);
            tower_1.push(tower.pop());
            i++;// --------------注意在此处进行i++
            towerOfMinimunDisk = (int) ((towerOfMinimunDisk + 1) % 3);
            // ------------注意此时对三个tower进行重新赋值
            tower = towers[towerOfMinimunDisk];
            tower_1 = towers[(int) ((towerOfMinimunDisk + 1) % 3)];
            tower_2 = towers[(int) ((towerOfMinimunDisk + 2) % 3)];
            // 对另外两个塔进行处理
            if ((tower_2.getTop() != -1 && (tower_1.showTopDisk() > tower_2
                    .showTopDisk()))
            // --------------注意要再加上 tower_2.getTop() != -1
            // 进行判断，否则可能数组访问越界
                    || (tower_1.getTop() == -1 && tower_2.getTop() != -1)) {
                System.out.println(tower_2.name + " -> " + tower_1.name);
                tower_1.push(tower_2.pop());
                i++;// --------------注意在此处进行i++
            } else if (((tower_1.getTop() != -1 && tower_1.showTopDisk() < tower_2
                    .showTopDisk()))
            // --------------注意要再加上 tower_1.getTop() != -1
            // 进行判断，否则可能数组访问越界
                    || (tower_1.getTop() != -1 && tower_2.getTop() == -1)) {
                System.out.println(tower_1.name + " -> " + tower_2.name);
                tower_2.push(tower_1.pop());
                i++;// --------------注意在此处进行i++
            }
            ii = i;
        }
        System.out.println(ii);
    }

}

// 存放信息的结构体
class Disk {
    // 从A塔通过B塔移动到C塔
    char A;
    char B;
    char C;
    // 塔的状态:当status=1时，表示可以直接将该Disk移动到目标塔
    int status;

    // 重写构造函数
    public Disk(int status, char A, char B, char C) {
        this.status = status;
        this.A = A;
        this.B = B;
        this.C = C;
    }
}

// 存放Disk的栈
class Stack {
    // 用来存储盘子的数组
    Disk[] disks = new Disk[10000];
    // 塔顶
    private int top = 0;

    // 查看栈顶
    public Disk stackTop() {
        return disks[top];
    }

    // 出栈
    public Disk pop() {
        if (top != 0) {
            top--;
            return disks[top + 1];
        } else {
            return null;
        }
    }

    // 入栈
    public void push(Disk disk) {
        top++;
        disks[top] = disk;
    }
}

// 为 play_regular(int diskNum) 创建的 Stack 类
// 以 diskId 来表示 Disk 对象
class Stack_play_regular {
    // 塔名
    char name;
    // 塔顶
    private int top = -1;

    public int getTop() {
        return top;
    }

    // 通过数组实现Stack,最多64个Disk
    int[] stack = new int[64];

    // 重写构造函数，初始化塔的名字name
    public Stack_play_regular(char name) {
        this.name = name;
    }

    // 查看栈顶
    public int showTopDisk() {
        if (top == -1) {
            return -1;
        }
        return stack[top];
    }

    // 入栈
    public void push(int diskId) {
        stack[++top] = diskId;
    }

    // 出栈
    public int pop() {
        return stack[top--];
    }
}