經典算法：漢諾塔

AWang 發布于2019-08-23 12:40 / 3669人閱讀

摘要：學編程，學，算法也是必不可缺的，這一次給大家帶來一個經典的遞歸算法題，漢諾塔。當我們把層都搬到了中間柱的時候，只需要把最大的那個盤，從搬到柱就好了，剩下的怎么辦呢柱永遠是目標柱，我們不需要去移動它。

學編程，學IT，算法也是必不可缺的，這一次給大家帶來一個經典的遞歸算法題，漢諾塔。算是算法的入門小題目之一吧~

視頻教程 什么是漢諾塔？

我這里直接拉來一個圖解釋一下（掛了請聯系我）

就是這么一個東西了，把所有的圓盤從左邊移動到右邊，并且大的圓盤不能夠壓住小的。怎么才能完成呢？

規則理解了，開始鉆牛角尖

先來看看只有一個圓盤的情況，

嗯相當的簡單 A--->C 就可以了

兩個的情況呢？也不難 A--->B A--->C B--->C

三個的話有點挑戰了大家自己推一推

好的十個呢？就算想了半天弄好了，怎么讓程序幫我們做呢？頭大！

牛角尖鉆完了，冷靜分析

在我們每次距離對稱最近的狀態，都是把最大的圓盤放到了最右邊，剩下的圓盤放到了中間。

然后把中間的再都放到右邊就好了

這道理就跟把大象裝冰箱一樣啊都是三步呢！

這時候千萬不要去想怎么把n-1層都搬到B柱也不要想怎么把N-1層都搬到C柱，如果繼續想下去你就會進入死循環，這時候你只需要做一個思維轉換。

當我們把n-1層都搬到了中間柱的時候，只需要把最大的那個盤，從A搬到C柱就好了，剩下的怎么辦呢？C柱永遠是目標柱，我們不需要去移動它。這時候我們大點力！把B柱子掰下來！扔到A前面！無視掉C柱上面的大圓盤，因為我們不會再去動它了！是不是畫面似曾相識？對啊！遞歸啊！繼續把最左邊的n-1層都弄到中間，最大的扔到C就好了啊！

看到這里如果你還在鉆牛角尖的話，可以暫時休息一下了。

思維轉換完成的過來寫代碼！

// JS寫一下
function move(num,from,button,to){
    // 如果只有一個圓盤
    if(num==1){
        console.log(from,"---->",to)
        // 最左邊的放到最后邊完了個事！
        return
    }
    // 如果柱子有點多咋辦呢？
    // 先把n-1個左邊的放到中間唄
    move(num-1,from,to,button) //放過去了，具體過程是啥？我特么哪里知道 它里面怎么操作?管他呢,反正他自己知道自己干了啥
    console.log(from,"---->",to) // 我就干一件事，我就把左邊最大的放到右邊，雖然我不知道現在我是不是真正的左邊，我可能是被你大力從中間拽過來的左邊。
    // 放完了然后呢？
    // 把所有中間的柱子扔到最右邊去
    move(num-1,button,from,to)
}

move(3,"A","B","C") //測試一下

//golang
package main

import (
    "fmt"
)

func main() {
    move(3,"A","B","C")
}

func move(num int,from string,button string,to string){
    if num==1 {
        fmt.Printf("%s--->%s
",from,to)
        return
    }
    move(num-1,from,to,button)
    fmt.Printf("%s--->%s
",from,to)
    move(num-1,button,from,to)
}

# python

def move(num ,fro,button,to)
    if (num==1)
        print(fro,"--->",to)
        return
    move(num-1,fro,to,button)
    print(fro,"--->",to)
    move(num-1,button,fro,to)
move(3,"A","B","C")

總結

遞歸這個東西,千萬不可鉆牛角尖,把大問題分成小問題,復雜問題簡單化,如果非要把遞歸過程推出來的話,那誰都救不了你

歡迎大家關注我的博客,里面會有我所寫博客的視頻版本,如果你有更多疑問或者想學前端的話,可以加我微信shouzi_1994或者在博客下方品論留言,三大Q.

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

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

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

經典算法：漢諾塔

摘要：學編程，學，算法也是必不可缺的，這一次給大家帶來一個經典的遞歸算法題，漢諾塔。當我們把層都搬到了中間柱的時候，只需要把最大的那個盤，從搬到柱就好了，剩下的怎么辦呢柱永遠是目標柱，我們不需要去移動它。學編程，學IT，算法也是必不可缺的，這一次給大家帶來一個經典的遞歸算法題，漢諾塔。算是算法的入門小題目之一吧~ 視頻教程什么是漢諾塔？我這里直接拉來一個圖解釋一下（掛了請聯系我）sho...

Lin_R 2019-07-31 11:17 評論0 收藏0
堆棧的應用——用JavaScript描述數據結構

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

Hydrogen 2019-08-23 10:54 評論0 收藏0
漢諾塔問題

摘要：概述漢諾塔是一個經典的遞歸問題，雖說看人家寫好的算法程序就那么幾行，但著實理解有一定的難度。查閱了一些資料，參閱別人的思路，對漢諾塔算法進行一番梳理。問題來源有一個梵塔，塔內有三個座，座上有若干個盤子，盤子大小不等，大的在下，小的在上如圖。概述漢諾塔是一個經典的遞歸問題，雖說看人家寫好的算法程序就那么幾行，但著實理解有一定的難度。查閱了一些資料，參閱別人的思路，對漢諾塔算法進行一番...

RayKr 2019-08-14 15:11 評論0 收藏0
【程序員必會十大算法】之分治算法（漢諾塔問題）

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

codecraft 2021-09-24 09:48 評論0 收藏0