簡單又常見的算法題:漢諾塔

2021-01-14 算法愛好者

(給算法愛好者加星標,修煉編程內功)

來源:山大王wld

算法題儘量做到難易結合,在我們看一些難題的時候偶爾也可以看一些非常簡單又非常容易看懂的題,要不然算法題一直看不懂,容易打擊大家的興趣,今天來看一道非常簡單又非常常見的算法題,就是漢諾塔問題,這道題我想只要是學過編程的同學都應該知道的。



關於漢諾塔的傳說


漢諾塔:漢諾塔(又稱河內塔)問題是源於印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子,在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。並且規定,在小圓盤上不能放大圓盤,在三根柱子之間一次只能移動一個圓盤。


漢諾塔還有另外一個版本


漢諾塔(Towers of Hanoi)是法國人M.Claus(Lucas)於1883年從泰國帶至法國的,河內為越戰時北越的首都,即現在的胡志明市;1883年法國數學家 Edouard Lucas曾提及這個故事,據說創世紀時Benares有一座波羅教塔,是由三支鑽石棒( Pag)所支撐,開始時神在第一根棒上放置64個由上至下依由小至大排列的金盤(Disc) ,並命令僧侶將所有的金盤從第一根石棒移至第三根石棒,且搬運過程中遵守大盤子在小盤子之下的原則,若每日僅搬一個盤子,則當盤子全數搬運完畢之時,此塔將毀損, 而也就是世界末日來臨之時


我們這裡不去追本溯源,追究他哪個版本是正確的,我們知道有這樣一道題就行,直接文字敘述可能不太直觀,我們畫個圖來分析一下


1,當只有一個的時候



2,當只有2個的時候

      


3,當只有3個的時候


當n等於3的時候移動的步數就比較多了,我們就不再畫圖了,我們來看一個動畫



4,當只有4個的時候



5,當有n個的時候



這裡主要還是考察對遞歸的理解,其實遞歸我們沒必要把每一步都推出來,我們只需要找到他的規律和邊界條件就行了,就像前面我們講356,青蛙跳臺階相關問題的時候,我們提到了斐波那契數列,我們只需要找到斐波那契的規律f(n)=f(n-1)+f(n-2),和他的邊界條件f(0)=f(1)=1我們就可以寫出代碼了,其他的我們就不用管了。


故事篇


這裡我來給大家講個故事吧,很久很久以前有一個人,名叫「孤獨求敗」,他和家人住在山下過著與世無爭的生活,就這樣每天日出而作日落而息。有一天他從山上砍柴回來,突然看到家人遇害,他悲痛欲絕,於是決定給家人報仇,但他武藝不行,而仇人的功夫很高,如果硬拼不但報不了仇,而且還會白白丟了性命,所以他決定先去習武。


那天他來到一座山上,看到一個老和尚,向他說明了緣由,老和尚聽聞之後怒火中燒,一腳把門前的一個千斤石獅踢開,想幫孤獨求敗報仇,但又怕得罪他的仇人導致引火燒身,所以他就對孤獨求敗說:「此仇只有你自己能報」。


孤獨求敗:「可我功夫不行,根本報不了仇」。


老和尚;「別急,請跟我來」。


於是老和尚帶他來到了一間很破舊的房子裡,指著裡面的一個滿是灰塵的破柜子說;「武功秘籍就鎖在這裡面,你拿到鑰匙打開它,把它拿回去自己修煉,等你功夫達到十級之後就可以找你的仇人報仇了」。


然後找來了他的大徒弟對孤獨求敗說,這是你的大師兄,鑰匙你找他要,我要回去睡覺了。然後大師兄說鑰匙鎖在我自己的小盒子裡了,我小盒子的鑰匙在二師兄拿著,你先去找二師兄把我這小盒子的鑰匙拿到,我把這個小盒子打開,就可以把鎖柜子的鑰匙給你了。


於是孤獨求敗又去找到了二師兄,然後二師兄說,大師兄的鑰匙被我鎖在了我自己的小盒子裡了,我自己的小盒子的鑰匙在三師兄拿著……


就這樣,孤獨求敗一直找下去,直到找到最小的100師兄拿到鑰匙,然後交給第99師兄,打開第99師兄的小盒子,拿到第98師兄的鑰匙,又交給第98師兄……一直到大師兄,然後大師兄拿到鑰匙打開自己的小盒子,把藏有武功秘籍的柜子鑰匙交給孤獨求敗,這樣孤獨求敗就拿到了武功秘籍,回家修煉去了……


孤獨求敗從大師兄開始到拿到武功秘籍的過程其實就是遞歸


讀懂了上面的故事,再來看漢諾塔問題就容易多了,我們來看下代碼。


1//表示的是把n個圓盤成功的從A移動到C
2public static void hanoi(int n, char A, char B, char C) {
3    if (n == 1) {
4        //如果只有一個,直接從A移動到C即可
5        System.out.println("從" + A + "移動到" + C);
6    } else {
7        //表示先把n-1個圓盤成功從A移動到B
8        hanoi(n - 1, A, C, B);
9        //把第n個圓盤從A移動到C
10        System.out.println("從" + A + "移動到" + C);
11        //表示把n-1個圓盤再成功從B移動到C
12        hanoi(n - 1, B, A, C);
13    }
14}


我們還可以把每個柱子看作是一個棧,大的在下面,小的在上面,所以我們也可以使用棧來實現


1//stackA 源柱  stackB 藉助柱  stackC目的柱
2public static void move(Stack stackA, Stack stackB, Stack stackC, int n) {
3    if (n == 1) {
4        stackC.push(stackA.pop());
5    } else {
6        move(stackA, stackC, stackB, n - 1);
7        stackC.push(stackA.pop());
8        move(stackB, stackA, stackC, n - 1);
9    }
10}


如果想要統計總共移了多少次,可以使用公式(2^n)-1,代碼如下


1public static long hanoiCount(int n) {
2    return (1L << n) - 1;
3}


當n=63的時候,我們得到9223372036854775807,當n=64的時候就已經出現了數字溢出。





覺得本文有幫助?請分享給更多人

關注「算法愛好者」加星標,修煉編程內功

好文章,我在看❤️

相關焦點

  • 64階漢諾塔完成需要5800億年?手寫一個漢諾塔遞歸算法
    漢諾塔是一個非常經典的數學模型,它有一個古老的傳說。相傳印度主神大梵天在創造世界的同時,也造了三根金剛石柱子。其中一根柱子上放著64個大小均不相同的圓盤。大梵天命令婆羅門將這64個圓盤按照從大到小的順序移動到另一根柱子上,在移動的過程中始終要保持大盤在下,小盤子在上。
  • 畢業生求職必會算法 漢諾塔
    漢諾塔:漢諾塔(又稱河內塔)問題是源於印度一個古老傳說的益智玩具。二、漢諾塔移動過程漢諾塔動畫: 演示圓盤移動過程(此動圖來源於網絡)下面分三種情況分別演示每個盤子的移動過程(n 代表圓盤數量):1個圓盤的情況:
  • 漢諾塔遊戲:遞歸經典問題
    漢諾塔遊戲,是非常著名的智力趣味題,在很多算法書籍和智力競賽中都有涉及。
  • 你會玩漢諾塔嗎?——讓遞歸算法來幫你,只需「3步」
    今天我們來介紹一種很常見的算法——遞歸。遞歸函數什麼是遞歸?簡單的說,遞歸就是通過不斷調用自己,來完成不斷循環的一個過程。可能概念有些拗口,我們編寫一個遞歸函數來說明。斐波那契數列大家都知道,它從第三項開始,每一項都是前面兩項的和:1,1,2,3,5,8,13,21......
  • 漢諾塔的神秘步伐
    快問快答:漢諾塔什麼形狀?
  • 啟迪智慧的漢諾塔遊戲
    1883年法國的數學家 Edouard Lucas(愛德華·盧卡斯) 提出漢諾塔問題。這個小小的遊戲裡邊包含著巨大的數學智慧,塔遊戲中蘊藏著豐富的數學思想方法:包括分類討論的思想與方法、最優化選擇的方法、數學歸納的方法、數學遞歸的思想等,因此 ,玩好漢諾塔遊戲不僅可以從中獲得快樂 ,還能夠學到許多數學知識 。
  • 一起玩轉漢諾塔
    漢諾塔(又稱河內塔)問題是源於印度一個古老傳說的益智玩具。
  • 荒野日記漢諾塔怎麼玩
    本次給大家帶來的是荒野日記中的漢諾塔,漢諾塔如果過不去的話就會沒辦法通過遺蹟,這裡就給大家講解一下,卡關的玩家可以看一下,希望能夠幫助到各位玩家~下面就一起來看看吧! 本次給大家帶來的是荒野日記中的漢諾塔,漢諾塔如果過不去的話就會沒辦法通過遺蹟
  • 強迫症玩家的最愛 書本漢諾塔讓一切歸於有序
    漢諾塔是一種非常古老的益智遊戲,小編在很小的時候就接觸過這種遊戲,對這類遊戲雖談不上喜歡,但卻有著很深刻的印象,今天小編就為大家帶來就是一款名為書本漢諾塔的休閒益智遊戲,遊戲好不好,大家看過評測就知道了。
  • 數學奧秘——漢諾塔的秘密
    今天帶來了一個有趣的數學思維遊戲——漢諾塔遊戲。相傳神創造了3根杆子,就有了這個遊戲,分別是起始杆、過渡杆和目標杆,起始杆上擺放著大小不同的圓盤。其中起始杆上擺放一個圓盤表示第一關,擺放兩個圓盤表示第二關,擺放三個圓盤表示第三關,依次類推。
  • 關於漢諾塔的步驟
    畫之前,我們先了解一個有趣的問題~如何理解漢諾塔到底幾個步驟的問題?看看熱心知友的回覆漢諾塔永遠只有三步:ok,進入教程。準備工具:尺子,鉛筆,剪刀。先來看效果圖:▼第一步:我們用尺子劃分好由小到大的格子。
  • 程式設計師面試題,200億個數字找中位數,不給分桶算法,怎麼辦?
    海量數據裡面如何尋找一堆數字的中位數,是一道非常常見的面試題。據稱,這個題目是騰訊前首席技術執行官Tony推崇的一個面試題,被加入的騰訊的面試題題庫。今天我們就來討論下這個題目,有一個存放著200億個數字的文件,存放著32位整型,可能會有重複的數字,現在想從這堆數字中找到他們的中位數。
  • 網際網路公司最常見的面試算法題大集合
    LeetCode是一個美國的在線編程網站,收集了各個大廠的筆試面試題,對找工作的畢業生和開發者來說,非常有價值。不過LeetCode上面的題目很多都是考察應聘者對基礎知識的應用,適合進行練習編程基礎或者準備面試。很多求職者都會在LeetCode刷上一遍,面試官也喜歡在上面挑選各類題目。
  • JAVA必須掌握的數據結構和算法
    常見的數據結構鍊表LinkedHashSet LinkedList 底層數據結構由鍊表和哈希表組成。數據的添加和刪除都較為方便,就是訪問比較耗費時間。數組ArrayList 訪問數據十分簡單,而添加和刪除數據比較耗工夫堆堆是一種圖的樹形結構,被用於實現「優先隊列",優先隊列是一種數據結構,可以自由添加數據,但取出數據時要從最小值開始按順序取出
  • 每天一道算法題(第三十二期)
    這周的題是隨機抽取,沒有特定的主題。算法題解沒有特定的思路,可能一人有一個思路,例如有的題既可以使用動規,又可以使用分治。殊途同歸,算法的目的就是提升效率。連續數列給定一個整數數組,找出總和最大的連續數列,並返回總和。
  • 漢諾塔TowerOfHanoi 工作學習之餘娛樂一番
    漢諾塔(又稱河內塔)是一款WP7平臺上源於印度一個古老傳說的益智類遊戲。傳說上帝創造世界的時候做了三根金剛石柱子,在一根柱子上從下往上按大小順序摞著64片黃金圓盤。上帝命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。
  • C語言+EasyX庫:漢諾塔移動動畫
    漢諾塔(又稱河內塔)是一款源於印度一個古老傳說的益智類遊戲。傳說上帝創造世界的時候做了三根金剛石柱子,在一根柱子上從下往上按大小順序摞著7片黃金圓盤。上帝命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。並且規定,在小圓盤上不能放大圓盤,在三根柱子之間一次只能移動一個圓盤。遊戲裡有三根金剛石柱子,在一根柱子上從下往上按大小順序摞著7片黃金圓盤。
  • Top30數據分析師常見面試題(附答案)!
    快來看看,以下30道數據分析相關面試題,你會多少?1、分析數據還要寫java代碼是不是效率有點低?2、成為一名數據分析師需要具備哪些技能?一些數據清理的最佳實踐包括:按不同的屬性排序數據對於大數據集,逐步清理並改進數據,直到獲得良好的數據質量對大型數據集,可以先將其分解為小數據集,使用更少的數據將增加迭代速度要處理常見的清理任務,請創建一組實用程序函數/工具/腳本。
  • 8種常見機器學習算法比較
    對小規模的數據表現很好,能個處理多分類任務,適合增量式訓練;對缺失數據不太敏感,算法也比較簡單,常用於文本分類。優點: 實現簡單,計算簡單;缺點: 不能擬合非線性數據.4.最近領算法——KNNKNN即最近鄰算法,其主要過程為:1. 計算訓練樣本和測試樣本中每個樣本點的距離(常見的距離度量有歐式距離,馬氏距離等);2.
  • 漢諾塔——我其實還在第一層
    漢諾塔問題描述假設有3個分別命名為A,B,C的塔座,在塔座A上插有n個直徑大小各不相同,依小從大編號為1,2,........,n的圓盤。