View Code
 /*
  * Hanoi塔游戲 問題描述：
  * 漢諾塔：漢諾塔（又稱河內(nèi)塔）問題是源于印度一個(gè)古老傳說的益智玩具。
  * 大梵天創(chuàng)造世界的時(shí)候做了三根金剛石柱子，在一根柱子上從下往上按照
  * 大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小
  * 順序重新擺放在另一根柱子上。并且規(guī)定，在小圓盤上不能放大圓盤，在
  * 三根柱子之間一次只能移動(dòng)一個(gè)圓盤。
  *
  * fuction:實(shí)現(xiàn) hanoi塔
  *             1.遞歸實(shí)現(xiàn)
  *             2.非遞歸實(shí)現(xiàn)
  * author:iGeneral
  * date:2013.04.26
  *
  * expe:
  *         1.注意：塔的狀態(tài):當(dāng)status=1時(shí)，表示可以直接將該Disk移動(dòng)到目標(biāo)塔
  *                 而不是用Disk的id來判斷輸出
  *         2.System.out.println();
           System.out.println((int)3.3%3);
           沒有(int)時(shí)，輸出：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("請(qǐng)輸入Hanoi碟子的數(shù)量：");
         int diskNum = scanner.nextInt();
         Hanoi hanoi = new Hanoi();
         System.out.println("遞歸實(shí)現(xiàn)：");
         hanoi.play_recursive(diskNum, 'A', 'B', 'C');
         System.out.println("非遞歸實(shí)現(xiàn)(模仿遞歸思想)：");
         hanoi.play_non_recursive(diskNum);
         System.out.println("非遞歸實(shí)現(xiàn)(根據(jù)Hanoi規(guī)律)：");
         hanoi.play_regular(diskNum);

     }

 }

 class Hanoi {

     // 遞歸實(shí)現(xiàn)
     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);
         }

     }

     // 非遞歸實(shí)現(xiàn)：模仿遞歸思想
     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 {
                 // 反順序添加
                 // 將執(zhí)行移動(dòng) popDisk 的下一步的Disk添加到Stack
                 stack.push(new Disk(popDisk.status - 1, popDisk.B, popDisk.A,
                         popDisk.C));
                 // 將一個(gè)status為 "1" 且移動(dòng)順序與 popDisk 相同的Disk 添加到Stack中
                 stack.push(new Disk(1, popDisk.A, popDisk.B, popDisk.C));
                 // 將執(zhí)行移動(dòng) popDisk 的前一步的Disk添加到Stack中
                 stack.push(new Disk(popDisk.status - 1, popDisk.A, popDisk.C,
                         popDisk.B));
             }
         }
     }

     // 非遞歸實(shí)現(xiàn)：根據(jù)Hanoi規(guī)律
     public void play_regular(int diskNum) {

         // 根據(jù)規(guī)律，需要根據(jù) Disk 的個(gè)數(shù)，多塔的位置進(jìn)行調(diào)整
         // 塔的個(gè)數(shù)為偶數(shù)時(shí)，將三個(gè)塔按“A->B->C”的順序排列成三角形
         // 塔的個(gè)數(shù)為奇數(shù)時(shí)，將三個(gè)塔按"A->C->B"的順序排列成三角形
         // 將diskNum個(gè)Disk按”上小下大“的順序放在A塔中（堆棧實(shí)現(xiàn)），同時(shí)將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);
         }
         // 將三個(gè)塔模擬成三角形形狀排列
         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;
         // 根據(jù)證明：n個(gè)Disk移動(dòng)完成至少需要2^n-1次
         // 不斷交替進(jìn)行以下兩步
         // 將最小的Disk按以上塔的順序下移到下一個(gè)塔
         // 對(duì)除了最小Disk所在的塔的另外兩個(gè)塔進(jìn)行操作，可能出現(xiàn)兩種情況
         // 情況一：一個(gè)塔中沒有Disk，此時(shí)將存在Disk的塔最上面的Disk移動(dòng)到?jīng)]Disk的塔上
         // 情況二：兩個(gè)塔都有Disk，此時(shí)對(duì)他們最上面的塔進(jìn)行比較，將較小的Disk移動(dòng)到較大的Disk上
         // 不會(huì)存在兩個(gè)塔都沒有Disk的情況，除非移動(dòng)已經(jīng)完成或未開始或只有一個(gè)盤子時(shí)的移動(dòng)
         int ii = 0;
         for (int i = 0; i < (Math.pow(2, diskNum) - 1);) {// --------------注意在此處不進(jìn)行i++
             // 取出三個(gè)塔，使代碼更清晰
             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)];
             // 移動(dòng)最小的盤子
             System.out.println(tower.name + " -> " + tower_1.name);
             tower_1.push(tower.pop());
             i++;// --------------注意在此處進(jìn)行i++
             towerOfMinimunDisk = (int) ((towerOfMinimunDisk + 1) % 3);
             // ------------注意此時(shí)對(duì)三個(gè)tower進(jìn)行重新賦值
             tower = towers[towerOfMinimunDisk];
             tower_1 = towers[(int) ((towerOfMinimunDisk + 1) % 3)];
             tower_2 = towers[(int) ((towerOfMinimunDisk + 2) % 3)];
             // 對(duì)另外兩個(gè)塔進(jìn)行處理
             if ((tower_2.getTop() != -1 && (tower_1.showTopDisk() > tower_2
                     .showTopDisk()))
             // --------------注意要再加上 tower_2.getTop() != -1
             // 進(jìn)行判斷，否則可能數(shù)組訪問越界
                     || (tower_1.getTop() == -1 && tower_2.getTop() != -1)) {
                 System.out.println(tower_2.name + " -> " + tower_1.name);
                 tower_1.push(tower_2.pop());
                 i++;// --------------注意在此處進(jìn)行i++
             } else if (((tower_1.getTop() != -1 && tower_1.showTopDisk() < tower_2
                     .showTopDisk()))
             // --------------注意要再加上 tower_1.getTop() != -1
             // 進(jìn)行判斷，否則可能數(shù)組訪問越界
                     || (tower_1.getTop() != -1 && tower_2.getTop() == -1)) {
                 System.out.println(tower_1.name + " -> " + tower_2.name);
                 tower_2.push(tower_1.pop());
                 i++;// --------------注意在此處進(jìn)行i++
             }
             ii = i;
         }
         System.out.println(ii);
     }

 }

 // 存放信息的結(jié)構(gòu)體
 class Disk {
     // 從A塔通過B塔移動(dòng)到C塔
     char A;
     char B;
     char C;
     // 塔的狀態(tài):當(dāng)status=1時(shí)，表示可以直接將該Disk移動(dòng)到目標(biāo)塔
     int status;

     // 重寫構(gòu)造函數(shù)
     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 {
     // 用來存儲(chǔ)盤子的數(shù)組
     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) 創(chuàng)建的 Stack 類
 // 以 diskId 來表示 Disk 對(duì)象
 class Stack_play_regular {
     // 塔名
     char name;
     // 塔頂
     private int top = -1;

     public int getTop() {
         return top;
     }

     // 通過數(shù)組實(shí)現(xiàn)Stack,最多64個(gè)Disk
     int[] stack = new int[64];

     // 重寫構(gòu)造函數(shù)，初始化塔的名字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--];
     }
 }