快捷導(dǎo)航

Java SE求解漢諾塔問(wèn)題的示例代碼

更新時(shí)間：2022年03月14日 17:20:33 作者：K媾?

漢諾塔問(wèn)題是一個(gè)經(jīng)典的問(wèn)題。漢諾塔（Hanoi Tower），又稱河內(nèi)塔，源于印度一個(gè)古老傳說(shuō)。本文將用Java SE求解這一問(wèn)題，感興趣的可以學(xué)習(xí)一下

1.問(wèn)題描述

漢諾塔問(wèn)題是一個(gè)經(jīng)典的問(wèn)題。漢諾塔（Hanoi Tower），又稱河內(nèi)塔，源于印度一個(gè)古老傳說(shuō)。

大梵天創(chuàng)造世界的時(shí)候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤(pán)。

大梵天命令婆羅門(mén)把圓盤(pán)從下面開(kāi)始按大小順序重新擺放在另一根柱子上。

并且規(guī)定，任何時(shí)候，在小圓盤(pán)上都不能放大圓盤(pán)，且在三根柱子之間一次只能移動(dòng)一個(gè)圓盤(pán)。問(wèn)應(yīng)該如何操作？

2.畫(huà)圖分析

一個(gè)圓盤(pán)的情況：移動(dòng)前

移動(dòng)后

1個(gè)盤(pán)子：A直接移動(dòng)到C

二個(gè)圓盤(pán)的情況：移動(dòng)前

移動(dòng)后

2個(gè)圓盤(pán)：A->B A->C B->C

三個(gè)圓盤(pán)的情況：移動(dòng)前

移動(dòng)后

三個(gè)圓盤(pán)：A->C A->B C->B A->C B->A B->C A-C

3.問(wèn)題講解

當(dāng)有3個(gè)盤(pán)子的時(shí)候，你就會(huì)發(fā)現(xiàn)一個(gè)問(wèn)題，你肯定是要先將上面的兩個(gè)盤(pán)子移動(dòng)到B柱，再把最底下的一個(gè)盤(pán)子移動(dòng)到C柱，最后再把B柱的盤(pán)子移動(dòng)到C柱。4個(gè)盤(pán)子的話也是一樣，要先將上面的3個(gè)盤(pán)子移動(dòng)到B柱，在把最底下的一個(gè)盤(pán)子移動(dòng)到C柱，最后再把B柱的盤(pán)子移動(dòng)到C柱。這樣我們就有了一個(gè)思路，不管多少個(gè)盤(pán)子，都要先將n - 1個(gè)盤(pán)子移動(dòng)到B柱，最底下的一個(gè)盤(pán)子移動(dòng)到C柱，最后再把B柱的盤(pán)子移動(dòng)到C柱。

我們先來(lái)看一下規(guī)律：

1個(gè)盤(pán)子：A->C 1次

2個(gè)盤(pán)子：A->B A->C B->C 3次

3個(gè)盤(pán)子：A->C A->B C->B A->C B->A B->C A-C 7次

這樣你就能看出移動(dòng)的次數(shù)其實(shí)就是2^n - 1(n是盤(pán)子的數(shù)量）

4.代碼實(shí)現(xiàn)

ublic class TestDemo {
    //首先要寫(xiě)個(gè)模擬鼠標(biāo)移動(dòng)過(guò)程的函數(shù)，我們要打印出移動(dòng)的全部過(guò)程
    //這個(gè)move函數(shù)做到的就是從1位置移動(dòng)到2位置，有可能是A->B,A->C,C-B......等各種可能
    public static void move(char pos1,char pos2){//所以說(shuō)這里只需要傳對(duì)應(yīng)的位置就可以了
        System.out.print(pos1+"->"+pos2+" ");//pos1移動(dòng)到pos2
    }
 
    /**
     *
     * @param n  n代表你盤(pán)子的個(gè)數(shù)
     * @param pos1 盤(pán)子所在的位置
     * @param pos2 盤(pán)子的中轉(zhuǎn)位置
     * @param pos3 盤(pán)子的結(jié)束位置
     */
    public static void hanio(int n,char pos1,char pos2,char pos3){
        if(n == 1){
            move(pos1,pos3);//如果只有一個(gè)盤(pán)子那就從A柱挪到C柱上
        }else{
            hanio(n-1,pos1,pos3,pos2);//這里是把n-1個(gè)盤(pán)子從A柱借助C柱移動(dòng)到B柱
            move(pos1,pos3);//底下剩下的最后一個(gè)盤(pán)子從A柱移動(dòng)到C柱
            hanio(n-1,pos2,pos1,pos3);//這里是把n-1個(gè)盤(pán)子從B柱借助A柱移動(dòng)到C柱
 
        }
 
 
    }
    public static void main(String[] args) {
        hanio(1,'A','B','C');//一開(kāi)始我們的漢諾塔要規(guī)定一下，我們第一次給它傳過(guò)去的位置
        System.out.println();
        hanio(2,'A','B','C');
        System.out.println();
        hanio(3,'A','B','C');
        System.out.println();
    }
 
 
 
 
}

打印結(jié)果：