這就是算法! 【遞歸算法】直到世界毀滅都完不成的漢諾塔遊戲

神奇的科普
12粉絲
41 次觀看·2025年9月19日
從前有座山 山裏有個廟 廟裏有個老和尚
在給小和尚講故事 講的是
從前有座山 山裏有個廟 廟裏有個老和尚
在給小和尚講故事 講的是
從前有座山 山裏有個廟 廟裏有個老和尚
誒 停停停 小和尚大侃
師父 您這故事怎麼像鬼打墻一樣 沒完沒了
老和尚捋著白鬍子 傻孩子 這就是地規呀
地規 什麼是地規 是地之烏龜嗎
老和尚神祕一想 要理解地規 就得先理解地規
來 聽個更有趣的故事
很久很久以前 大梵天在創造世界的時候
留下了三根鑽石神柱
第一根柱子上 疊著64片黃金圓盤
大若車輪 小如銅錢
自下而上 層層收縮 宛若通天之塔
大梵天命令婆羅們
將所有金盤搬到第三根柱子上
並立下神諭
一次只能挪動一個
大圓盤不能壓在小盤之上
傳說 當最後一個盤子被移動到第三根柱子上時
便是天崩地裂 世界毀滅之日
小和尚噗哧一笑
搬個盤子要搬到世界末日
師父別唬我 64個金盤
一炷香的功夫 我就能搬完
老和尚碾了碾長鬍子
牛皮吹的太早
等你真正算出結果 就傻眼了
來吧 讓我們從頭到尾推導一下
移動這64個圓盤需要多長時間
不過咱們不能一口吃個大胖子
先從三個圓盤開始吧
註意看 你的面前有三根柱子
第一根柱子上有三個圓盤
從上往下尺寸依次變大
按照大梵天的指令
每次只能移動一個
大的圓盤不能在小的之上
現在由你來把圓盤移動到第三個柱子上
你能用幾步完成呢
屏幕前的各位施主也可以暫停視頻
在紙上推理一下
小和尚十分自信的開始操作
第一步把小圓盤放到C上
第二步把中圓盤放到B上
第三步小和尚拿著手裡的大圓盤傻了
無論放到哪兒都會壓住小圓盤
做不出來了
老和尚早料到如此
結果大圓盤來摸摸小和尚的腦袋
沒事的 大不了我們再簡化一下問題
只移動兩個圓盤試試看
先把小圓盤放到B上
再把大圓盤放到C上
最後小圓盤放到C上
三步完成
如此可見
那麼我們再回到剛才卡住的地方
從哪裏跌倒再從哪裏站起來
既然大圓盤無處可放
我們不妨換個思路
先移動小圓盤試試
小和尚試著把C上的小圓盤放到B上
這下終於能夠移動大圓盤了
把它放到C上
現在不就剩下兩個圓盤在B了嗎
等等
我剛剛不是才練過怎麼移動兩個盤子嗎
他照著操作
果然又用三步就順利完成了
小和尚說
沒錯
這就是地規的精髓
看似是七步
其實只有三招
第一招
你先把兩個圓盤從A移到B
然後第二招
把大圓盤放到C上
最後第三招
把兩個圓盤從B移到C
小和尚一拍腦袋
我明白了
這就像把大象裝進冰箱
也分三步一樣
師傅
你不說我還沒有發現
第一招和第三招
都是移動兩個圓盤
而且都是三步
可是為什麼從A到B
和從A到C是一樣的呢
他們明明是不同的柱子
老和尚大笑
我們只是為了方便稱呼
才給它起名叫ABC的
實際上你移動圓盤的時候
並不知道柱子的名字
只需要知道圓盤
從哪來到哪去
中間經過誰
從A到B的時候
A是開始的柱子
B是目標柱子
C是做輔助的柱子
哦
也就是說
我們只用關註柱子
和要移動的圓盤
是什麼關系
而不用關註柱子的位置和名字
老和尚笑道
聰明
你再猜猜
五個圓盤最少需要幾步
小和尚掰著手指頭
第一招
從A到B移動四個圓盤
第二招
從A到C移動一個大圓盤
第三招
從B到C移動四個小圓盤
可是我不知道移動四個圓盤
需要幾步
老和尚大笑
五個圓盤會拆招
四個圓盤就不會了
小和尚恍然大悟
這不就跟套娃一樣嗎
大問題套小問題
小問題再套更小的問題
四個圓盤的話
第一招
從A到B移動三個圓盤
第二招
從A到C移動一個大圓盤
第三招
從B到C移動三個小圓盤
一共是7加1加7等於15
那麼五個圓盤的時候
就是15加1加15等於31
老和尚讚許的點頭
這就叫地規分解
就像剝洋蔥
核心就是兩個要點
一找到洋蔥芯
也就是初始情況
比如一個圓盤只需要一步
二找到一層層洋蔥皮
也就是地規情況
移動N個圓盤
可以拆分成
N-1個圓盤的方法來解決
五個可以拆成四個
四個可以拆成三個
老和尚在地上列出剛才的結果來
圓盤數量從1到5
最少需要的步數是
1 3 7 15 31
你看出什麼規律了嗎
小和尚皺眉
說的是基數吧
中間還缺了好幾個數
而且為什麼越往後
增大的越快
老和尚邪魅一笑
你把它們都加1看看
2 4 8 16 32
哇 全變成2的次方了
沒錯
步數就是2的N次方-1
那64個盤子需要多少步呢
小和尚掏出手機計算器
2的64次方-1
等於巴拉巴拉巴拉
這數字比我手機號還長
你馬上會發現
這數字比咱倆命都長
假設移動一個圓盤用1秒
這些數除以60秒得到分鐘
再除以60分鐘得到小時
除以24小時得到天
除以365天得到5849億年
也就是說
普羅門移動64個金盤
至少需要5849億年
要知道
地球存在至今
不過45億年
太陽系的預期壽命
據說也是百億年
真的過了5000多億年
別說世界末日
說不定連銀河系都灰飛煙滅了
說著
他從懷裡掏出一本經書
孩子
我看你骨骼驚奇
這是算法心經
只要你勤加練習
將來必成一代算法宗師
裏面記載著地規四要訣
一明確中止條件
二找出問題最好單元
三相信地規關系成立
四切勿深究地規過程
否則將走火入魔
小和尚點頭若有所思
難怪都說
地規只應天上有
迭代凡人用的歡
沒想到您還懂這麼深奧的東西
師傅
您之前是做什麼工作的
老和尚深呼一口氣
仰望天空
唉
想當年
我只是個計算機專業的大學生
我是淳于宇宙
講有溫度的故事
做有思考的科父
咱們下期再見
