[DataStructure]Towers of Hanoi(河內塔)

河內塔是一個數學遊戲：有三個塔柱A、B、C，遊戲的目的就是將A塔柱的圓盤全數移到C塔柱

遊戲有幾個規則：
1. 一次只能搬移一個圓盤
2. 小圓盤可以移到大圓盤上面，大圓盤不可以移到小圓盤上面。

事實上，可以從河內塔移動次數中，發現這是有遞迴規則的。
以最小的圓盤 n 為例：
當圓盤總數為 1 時， n 移動了 1 次
當圓盤總數為 2 時， n 移動了 2 次
當圓盤總數為 3 時， n 移動了 4 次
當圓盤總數為 4 時， n 移動了 8 次

為了要讓大盤可以移出來到目的柱，當盤數越多，其他較小圓盤就必須先移到暫存柱(三柱其中一柱)
若有n個盤子，則移動完畢所需的次數為2^n - 1

Java

import java.util.Scanner;
public class HanoiTower
{
    public static void main(String args[]) {
        System.out.print("請輸入盤數：");
        Scanner s = new Scanner(System.in);
        hanoi(s.nextInt(), 'A', 'B', 'C');
    }

    public static void hanoi(int n, char start, char temp, char end) {
        if(n > 0){
            //將所有盤子移到暫存區
            hanoi(n - 1, start, end, temp);
            //將最後一個盤子移到目的區
            display(n, start, end);
            //把暫存區的盤子移回目的區
            hanoi(n - 1, temp, start, end);
        }
    }

    public static void display(int n, char start, char end) {
        System.out.println("Move ring " + n + " from " + start + " to " + end);
    }
}