[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);
    }
}

[Java]Scanner next()與nextLine()無法同時使用問題

[Java]DecimalFormat(小數格式)