漢諾塔算法

UsherChen 發布于2019-08-21 16:55 / 1097人閱讀

摘要：漢諾塔問題描述有三個圓柱，其中上從上至下放置了從小到大個圓盤，一次只能移動一個圓盤，且大的圓盤不能放在小圓盤之上，要求打印出從將圓盤移到的方案。

漢諾塔問題描述：有A, B, C三個圓柱，其中A上從上至下放置了從小到大n個圓盤，一次只能移動一個圓盤，且大的圓盤不能放在小圓盤之上，要求打印出從A將圓盤移到C的方案。

當n = 1時， A->C
當n = 2時， A->B, A->C, B->C
當n = 3時， [A->C, A->B, C->B,] A->C,[B->A, B->C, A->C]
當n = 4時， A->B, A->C, B->C, A->B, C->A, C->B, A->B,

        A->C, 
        B->C, B->A, C->A, B->C, A->B, A->C, B->C

當n = 5時， A->C, A->B, C->B, A->C, B->A, B->C, A->C,

        A->B, 
        C->B, C->A, B->A, C->B, A->C, A->B, C->B
        
        A->C,
        
        B->A, B->C, A->C, B->A, C->B, C->A, B->A,
        B->C, 
        A->C, A->B, C->B, A->C, B->A, B->C, A->C

當n > 2時，第n項，[A->B],A->C,[B->C]

       第n-1項，A->B  [A->C],A->B,[C->B]    B->C [B->A],B->C,[A->C]
       第n-1-1項，
        第n-1項，A->C(此處的C應該是B)，A->C,和第n-1-1項，A->B(此處的B應是C)，B->C
        ……
        如此重復，可以用遞歸求得結果

由此，不難看出，計算n個圓盤，所需要的次數為f(n) = 2*f(n-1)+1

代碼：

const move=(a,c)=>{
    console.info(`${a}->${c}`)
}

const hanoi = (n,a,b,c)=>{
    if(n === 1){
        move(a,c)
    }else{
        //[A->B]
        hanoi(n-1,a,c,b);
        move(a,c);
        //[B->C]
        hanoi(n-1,b,a,c);
    }
}

參考：從fibonacci和漢諾塔看分治法

GPU云服務器云服務器簡單漢諾塔c語言算法漢諾塔漢諾塔 python 漢諾塔c語言講解

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/88905.html

【程序員必會十大算法】之分治算法（漢諾塔問題）

摘要：應用分治法是一種很重要的算法。字面上的解釋是分而治之，就是把一個復雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。 ...

codecraft 2021-09-24 09:48 評論0 收藏0
數據結構與算法之漢諾塔問題（Java遞歸）

摘要：漢諾塔問題有三根柱子，源桿，暫存桿，目的桿上有層盤子，由小到大向下排列，現需要將桿的盤子移到桿中要求大的盤在下面，小的盤在上面一次只能移動一個盤子個人思路先分析問題，用數學的歸納法當只有一個盤時，直接移動當有兩個盤時，先將小的移到暫存桿，再漢諾塔問題：有三根柱子，源桿A，暫存桿temp，目的桿C A上有n層盤子，由小到大向下排列，現需要將A桿的盤子移到C桿中 ...

yuxue 2019-08-16 15:51 評論0 收藏0
經典算法：漢諾塔

摘要：學編程，學，算法也是必不可缺的，這一次給大家帶來一個經典的遞歸算法題，漢諾塔。當我們把層都搬到了中間柱的時候，只需要把最大的那個盤，從搬到柱就好了，剩下的怎么辦呢柱永遠是目標柱，我們不需要去移動它。學編程，學IT，算法也是必不可缺的，這一次給大家帶來一個經典的遞歸算法題，漢諾塔。算是算法的入門小題目之一吧~ 視頻教程什么是漢諾塔？我這里直接拉來一個圖解釋一下（掛了請聯系我）sho...

Lin_R 2019-07-31 11:17 評論0 收藏0
經典算法：漢諾塔

摘要：學編程，學，算法也是必不可缺的，這一次給大家帶來一個經典的遞歸算法題，漢諾塔。當我們把層都搬到了中間柱的時候，只需要把最大的那個盤，從搬到柱就好了，剩下的怎么辦呢柱永遠是目標柱，我們不需要去移動它。學編程，學IT，算法也是必不可缺的，這一次給大家帶來一個經典的遞歸算法題，漢諾塔。算是算法的入門小題目之一吧~ 視頻教程什么是漢諾塔？我這里直接拉來一個圖解釋一下（掛了請聯系我）sho...

AWang 2019-08-23 12:40 評論0 收藏0