Java 河內塔

2018-11-17

5287
0

資料結構的河內塔用 Java 來實作

目的:

三個木椿

n 盤子放第一個木椿

要從第一個木椿移到最後一個

條件:

1.每次只能移動一個盤子, 只能從最上面的移動

2.盤子可移到任一木椿

3.木樁上盤子尺寸從上到下由小變大

演算法

Step1. 最上面 n-1 個盤子從木椿 1 -> 木椿2

Step2. 木椿 1 最下面盤子移動到木椿 3

Step3. 將木椿 2 中 n-1盤子移動到木椿 1

code:

public class HanoiTower {

    static void hanoiTower(int dishs, int one, int two, int three){
        if( dishs == 1)
            System.out.println("盤從" + one + "移到" + three);
        else{
            hanoiTower(dishs-1, one, three, two);//Step1.
            hanoiTower(1, one, two, three);//Step2.
            hanoiTower(dishs-1, two, one, three);//Step3.
        }
    }

    public static void main(String [] args){
        int dishs = 3;//盤子數
        hanoiTower(dishs, 1, 2, 3);
    }

}

Output

盤從1移到3
盤從1移到2
盤從3移到2
盤從1移到3
盤從2移到1
盤從2移到3
盤從1移到3

分析:

Step1. 最上面 n-1 個盤子從 木椿 1 -> 木椿2
hanoiTower(3,1,2,3) -> hanoiTower(2,1,3,2) -> hanoiTower(1, 1, 2, 3) ->盤子從1移動到3
                                              hanoiTower(1, 1, 3, 2) ->盤子從1移動到2
                                              hanoiTower(1, 3, 1, 2) ->盤子從3移動到2

Step2. 木椿 1 最下面盤子移動到木椿 3          
                       hanoiTower(1,1,2,3) -> 盤子從1移動到3

Step3. 將木椿 2 中 n-1盤子移動到木椿 1
                       hanoiTower(2,2,1,3) -> hanoiTower(1, 2, 3, 1) ->盤子從2移動到1
                                           -> hanoiTower(1, 2, 1, 3) ->盤子從2移動到3
                                           -> hanoiTower(1, 1, 2, 3) ->盤子從1移動到3

心得:

看演算法那三個步驟看起來是不難

但是隨著盤子數增加,如果不用程式老實說要我自己擺還真的不知道怎麼擺

參考:

https://www.javaworld.com.tw/jute/post/view?bid=29&id=324308

回首頁