成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

漢諾塔算法

UsherChen / 1099人閱讀

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

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

當(dāng)n = 1時(shí)， A->C
當(dāng)n = 2時(shí)， A->B, A->C, B->C
當(dāng)n = 3時(shí)， [A->C, A->B, C->B,] A->C,[B->A, B->C, A->C]
當(dāng)n = 4時(shí)， 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

當(dāng)n = 5時(shí)， 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

當(dāng)n > 2時(shí)，第n項(xiàng)，[A->B],A->C,[B->C]

       第n-1項(xiàng)，A->B  [A->C],A->B,[C->B]    B->C [B->A],B->C,[A->C]
       第n-1-1項(xiàng)，
        第n-1項(xiàng)，A->C(此處的C應(yīng)該是B)，A->C,和第n-1-1項(xiàng)，A->B(此處的B應(yīng)是C)，B->C
        ……
        如此重復(fù)，可以用遞歸求得結(jié)果

由此，不難看出，計(jì)算n個(gè)圓盤，所需要的次數(shù)為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和漢諾塔看分治法

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/88905.html

相關(guān)文章

  • 【程序員必會(huì)十大算法】之分治算法（漢諾塔問(wèn)題）

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

    codecraft 評(píng)論0 收藏0

  • 數(shù)據(jù)結(jié)構(gòu)與算法之漢諾塔問(wèn)題（Java遞歸）

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

    yuxue 評(píng)論0 收藏0

  • 經(jīng)典算法：漢諾塔

    摘要：學(xué)編程，學(xué)，算法也是必不可缺的，這一次給大家?guī)?lái)一個(gè)經(jīng)典的遞歸算法題，漢諾塔。當(dāng)我們把層都搬到了中間柱的時(shí)候，只需要把最大的那個(gè)盤，從搬到柱就好了，剩下的怎么辦呢柱永遠(yuǎn)是目標(biāo)柱，我們不需要去移動(dòng)它。 學(xué)編程，學(xué)IT，算法也是必不可缺的，這一次給大家?guī)?lái)一個(gè)經(jīng)典的遞歸算法題，漢諾塔。算是算法的入門小題目之一吧~ 視頻教程 什么是漢諾塔？ 我這里直接拉來(lái)一個(gè)圖解釋一下（掛了請(qǐng)聯(lián)系我）sho...

    Lin_R 評(píng)論0 收藏0

  • 經(jīng)典算法：漢諾塔

    摘要：學(xué)編程，學(xué)，算法也是必不可缺的，這一次給大家?guī)?lái)一個(gè)經(jīng)典的遞歸算法題，漢諾塔。當(dāng)我們把層都搬到了中間柱的時(shí)候，只需要把最大的那個(gè)盤，從搬到柱就好了，剩下的怎么辦呢柱永遠(yuǎn)是目標(biāo)柱，我們不需要去移動(dòng)它。 學(xué)編程，學(xué)IT，算法也是必不可缺的，這一次給大家?guī)?lái)一個(gè)經(jīng)典的遞歸算法題，漢諾塔。算是算法的入門小題目之一吧~ 視頻教程 什么是漢諾塔？ 我這里直接拉來(lái)一個(gè)圖解釋一下（掛了請(qǐng)聯(lián)系我）sho...

    AWang 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<