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

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

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

題目：

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

解題思路:

(1) 一個(gè)盤子：

1： A--->C

(2) 兩個(gè)盤子：

（3）三個(gè)盤子：

（4）四個(gè)盤子 :

總結(jié)：

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

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

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

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

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

js代碼：

//allSteps ：用于存放移動(dòng)的每一步驟
let allSteps=[];

/*
* 移動(dòng)盤子的遞歸函數(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);
  }
}

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

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/108626.html

相關(guān)文章

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

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

Hydrogen 2019-08-23 10:54 評(píng)論0 收藏0
【程序員必會(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 2021-09-24 09:48 評(píng)論0 收藏0
用自定義的拖放實(shí)現(xiàn)一個(gè)漢諾塔游戲

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

amc 2019-08-19 17:44 評(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 2019-08-16 15:51 評(píng)論0 收藏0
漢諾塔算法

摘要：漢諾塔問(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-...

UsherChen 2019-08-21 16:55 評(píng)論0 收藏0