河內之塔（漢諾塔）

fredshare 發布于2019-08-26 12:24 / 2189人閱讀

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

題目：

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

解題思路:

(1) 一個盤子：

1： A--->C

(2) 兩個盤子：

（3）三個盤子：

（4）四個盤子 :

總結：

用n表示盤子總數

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

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

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

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

js代碼：

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

/*
* 移動盤子的遞歸函數
* @param {number} n 當前處理的盤子
* @param {string} a , b ,c 代表當前的三根柱子
*/
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云服務器漢諾塔漢諾塔 python 漢諾塔c語言講解簡單漢諾塔c語言算法

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

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

堆棧的應用——用JavaScript描述數據結構

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

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

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

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

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

amc 2019-08-19 17:44 評論0 收藏0
數據結構與算法之漢諾塔問題（Java遞歸）

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

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

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

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