河內(nèi)之塔（漢諾塔）

fredshare 發(fā)布于2019-08-26 12:24 / 2220人閱讀

摘要：當(dāng)盤子個數(shù)超過你個時，其實就是通過遞歸處理兩個盤子每次只走三步即深度遍歷二叉樹代碼用于存放移動的每一步驟移動盤子的遞歸函數(shù)當(dāng)前處理的盤子代表當(dāng)前的三根柱子

題目：

三個柱子 A、B、C。在A柱子從上到下按照從小到大的順序放置64盤子，命令將所有的盤子從A柱子移至C柱子，并且搬運過程中小盤子不能放在大盤子上面，且在三根柱子之間一次只能移動一個盤子

解題思路:

(1) 一個盤子：

1： A--->C

(2) 兩個盤子：

（3）三個盤子：

（4）四個盤子 :

總結(jié)：

用n表示盤子總數(shù)

（1）當(dāng)只有一個盤子（n=1）的時候，直接從A到C；

（2）當(dāng)有兩個盤子（n=2）的時候，將第二根柱子B當(dāng)做輔助柱，共三步；

第一個盤子(n-1)從A到B，第二個盤子(n)從A到C，第一個盤子(n-1)從B到C。

（3）當(dāng)盤子個數(shù)超過2（你>2）個時，其實就是通過遞歸處理兩個盤子（每次只走三步）：（n-1）A—>B, （n）A-->C, （n-1）B-->C ；即：深度遍歷二叉樹

js代碼：

//allSteps ：用于存放移動的每一步驟
let allSteps=[];

/*
* 移動盤子的遞歸函數(shù)
* @param {number} n 當(dāng)前處理的盤子
* @param {string} a , b ,c 代表當(dāng)前的三根柱子
*/
function move(n,a,b,c){
  if(n===1){
    allSteps.push({
      n:n,
      from:a,
      to:c
    })
  }else{
    move(n-1,a,c,b);
    allSteps.push({
      n:n,
      from:a,
      to:c
    });
    move(n-1,b,a,c);
  }
}

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

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

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

相關(guān)文章

堆棧的應(yīng)用——用JavaScript描述數(shù)據(jù)結(jié)構(gòu)

摘要：一實現(xiàn)一個棧類基于堆棧的特性，可以用數(shù)組做線性表進(jìn)行存儲。出棧出棧同樣是利用數(shù)組的方法，在數(shù)組尾部推出數(shù)據(jù)。聚合最后，將所有功能聚合后，如下所示，一個堆棧的數(shù)據(jù)結(jié)構(gòu)就搞定了。堆棧的經(jīng)典算法應(yīng)用，首推就是漢諾塔。棧（stack）又名堆棧，它是一種運算受限的線性表。其限制是僅允許在表的一端進(jìn)行插入和刪除運算。這一端被稱為棧頂，相對地，把另一端稱為棧底。一、實現(xiàn)一個棧類Stack 基于堆...

Hydrogen 2019-08-23 10:54 評論0 收藏0
【程序員必會十大算法】之分治算法（漢諾塔問題）

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

codecraft 2021-09-24 09:48 評論0 收藏0
用自定義的拖放實現(xiàn)一個漢諾塔游戲

摘要：做這個漢諾塔游戲的想法，來自于幾個月前做百度第一期的一個題目，題目要求在兩個容器間實現(xiàn)子元素的相互拖拽效果。重構(gòu)好的代碼我放上了，實現(xiàn)的效果可見其，一起玩玩唄，覺得好玩記得給哈做這個漢諾塔游戲的想法，來自于幾個月前做百度IFE第一期的一個題目，題目要求在兩個容器間實現(xiàn)子元素的相互拖拽效果。當(dāng)時我就突發(fā)奇想：容器看成柱子，子元素看成盤子，再加一點限制底下盤子移動的判斷和勝負(fù)的判斷，不就...

amc 2019-08-19 17:44 評論0 收藏0
數(shù)據(jù)結(jié)構(gòu)與算法之漢諾塔問題（Java遞歸）

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

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

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

UsherChen 2019-08-21 16:55 評論0 收藏0