今天我想分享給大家漢諾塔問題的一個巧妙的解法，它隻用到了另一個計數系統中的數數過程，而且它竟還能幫你找到填充謝爾賓斯基三角形的一條曲線。本來我不是喜歡小謎題和小遊戲的那類人，不過我就是愛看這些謎題的解析，也愛看其中的數學規律，并且思考這究竟是怎麼來的。要是你不熟悉這個的話，我們首先解釋一下什麼是漢諾塔問題。

我們有三根柱子，還有從大到小的幾個圓盤，這些圓盤都被穿了孔，這樣就可以被串到柱子上。這裡我畫了5個圓盤，依次标記為0 1 2 3 4。不過理論上你想放多少個圓盤都行。一開始圓盤從大到小依次疊放在一根杆上，你的目标是把整個塔從一根杆子移動到另一根杆子上。它的規則是，一次隻能移動一個圓盤，而且大圓盤不能疊在小圓盤上面。例如，第一步你隻能移動0号圓盤，因為其他盤上面都有東西，不先移開的話它們是動不了的。接下來，你可以移動1号盤，但它隻能移動到沒有0号盤的柱子上，不然大圓盤會被放到小圓盤的上面，這就犯規了。

第一次聽說這遊戲的同學們，我強烈建議你們暫停視頻，拿出不同大小的書本，自己試試看，感受感受這個問題。假如你認為它難的話，難在哪裡？簡單的話，簡單在哪裡?想想這樣的問題。令人驚訝的是想解開漢諾塔問題，你隻需要用二進制來數數，然後用計數的節奏來對應出移動圓盤的節奏。要是你不熟悉二進制的話，我首先會簡短地概括一遍。其實，就算你已經很懂二進制，我還是想着重解釋一下用它計數時的節奏，因為你以前說不定沒這樣想過。一般我們解釋二進制時，首先會重新審視我們平常表示數字的方法，也就是十進制。因為我們會用到十個不同的數字，從0到9。這樣數數的節奏是，首先把十個數字都數一遍，當每個數字都用完之後，你需要數"十"，于是用2位數來表示:一零，這個"1"位于十位，因為它代表了你之前數過的那十個數。然後把個位數清零，變成0。數數的節奏是這樣重複的：數到9 然後十位進1，再數9個數然後十位再進1，如此類推。直到重複9遍之後，你就會向百位進1，百位記錄的是你數過了多少個一百，這時後兩位數就被清零了。

從這個角度看，計數的節奏有點自相似性：即使在更大的尺度上，整個過程也還是這樣的，做一個動作進一位，做同樣的動作再進一位，重複9次之後再進更大的一位。在二進制中你隻能用兩個數字 0和1，它們叫比特，這其實是"二進制數位"的簡稱。這樣一來，計數時你就得經常進位了。當你數完0和1後，比特就全用完了，于是你就要進到二位寫作"10"。習慣了十進制的你千萬要忍住别把它讀作"十"，而是要把它想成是1個二加上0，下一個數是11，表示數字三。接着你就又要進位了，但二位上已經是1了，所以你得再進一位。結果就是100，表示1個四，加0個二，加0。十進制裡的數位表示10的幂，同理二進制中的數位表示不同的2的幂。因此，十進制中有十位、百位、千位等等的概念。在二進制中有二位、四位、八位等等的概念。

于是數數的節奏就快了很多，不過同時也變得更加明顯了，末位加一，進一位；末位再加一，進兩位；末位又加一，進一位；末位再加一，進三位。這個規律再次展現了自相似性，在不同的尺度上，這個過程都是做一個動作，進位再重複動作。在小尺度下，例如數到三，也就是二進制中的11，我們先讓個位數加一，然後進到二位，再讓個位數加一。在大尺度上，例如數到十五，也就是二進制的1111，則先讓後三位數數到七，進到八位，然後再讓後三位數到七，數到255也就是二進制裡的8個1的話，你需要先數完最後7個比特，進到128位，然後再數完最後7個比特。

好了，說完了二進制簡介，我們可以給出驚人的事實是，能用這個節奏解開漢諾塔問題。你從零開始數起，每當你隻是把末位數從0變成1的時候，就把0号盤移到它右邊的柱子上，如果0已經在最右的柱子上了 就把它移回第一根柱子，要是在二進制計數中，你進到了二位，也就是把末兩位數從01變成10的話，你就移動1号盤，也許你會問移到哪裡呢？其實，你并沒有什麼選擇，你不能把它放到0号上，而剩下的隻有另一根柱了。所以你該往哪裡移就往哪裡移，接下來數到11，隻需要個位加一，于是你再次移動0号盤，然後二進制中進到四位，所以你移動2号圓盤，接下來的規律是類似的。個位加一，移動0号盤，二位進一，移動1号盤，末位加一，移動0号盤，接着我們要進位三次，到八位，相應地我們移動3号圓盤。這個解法相當奇妙，我第一次看到的時候在想，這不可能。我不懂這個原理，不懂為什麼能行，現在我懂了，不過看一遍還是覺得奇妙。我記得曾經制作了一個動畫演示，怎麼說呢，我懂得原理，知道發生了什麼。但坐下來完整地看一遍，還是覺得很有意思？

你想想，一開始你都說不準為什麼每一步都不會犯規，例如怎麼保證每次進到八位時3号盤都一定能夠移動呢？同時，這個解法馬上引出了其他的問題。例如這是怎麼來的，為什麼能行？有沒有比2的(n-1)次方步更快的解法呢？其實這個解法不僅能解漢諾塔問題，而且還是個最優解。想要理解這為什麼，怎麼能行，究竟是什麼道理，你得用某一個思想來看這個謎題，這個思想在計算機科學裡叫做遞歸。3号盤心想，210你們好，你們挪個地兒呗。這麼大堆玩意兒擱我身上叫我可咋整，于是從3号盤的角度想，你要是想要移動3号的話，不管你怎麼做 2 1 0号盤必須得移動到B柱，它們必須得這麼挪，任何一個盤在3号上面的話，3号都動不了。任何盤在C柱上的話 3号就不能移過去了，所以我們得移開2 1 0号，這樣以後，我們就可以把3号移到C柱。然後3号說，我完事兒了，幹啥都别搗鼓我了，你們能耐就都往我身上堆。于是，你就會得到同一個更小的問題。現在0 1 2号盤在B柱上，要把它們移動到C柱上，所以思路是，每次隻看一個圓盤，然後想，要移動這個盤必須做什麼。這樣我就把大問題變成小一點的問題了，那小問題怎麼解呢？一模一樣的道理，2号盤說，1号0号，你們那個我不是說誰，就是我想要一點空間，請下去吧。1号0号得移走，2号就能到想去的地方了，然後1号0号再移回來。重點是每個圓盤的策略都是一樣的，它們都說。樓上的下來。然後我就要動了。好之後大家就可以回來了，想到這個要點之後，你就能寫出解漢諾塔的代碼了，也就是五六行的事。估計這是史上每一行動腦量最大的代碼，多想一想的話，你會發現這明顯是最高效的解法。

在每一步上，你做的不過是你必須要做的事，在移動3号之前，必須移開0到2号，然後你必須移動3号，然後你必須把0到2号移回來。這樣看，根本沒有浪費步數的餘地。那為什麼二進制計數可以表示這個算法呢？是這樣的，解決小問題，移動大圓盤，再解決小問題的這個規律，跟二進制計數是完全一緻的。即數到一個數，進位，再數到同一個數。而且漢諾塔的算法和二進制計數都是自相似的過程，我的意思是，要是你多數一些，數到2的更高次幂，或者解圓盤數更多的漢諾塔，兩者的結構都是一樣的：子問題，動一步什麼，同樣的子問題。舉個例子，解兩個圓盤的漢諾塔時，移動0号，移動1号，移動0号，對應着用二進制來數到三。末位加一，進一位，末位加一。大一點的例子，3個圓盤的漢諾塔是這樣解的，想辦法解決2個盤的問題：移動2号盤，再想辦法解決2個盤的問題。同樣地，二進制中數到111，要先數三個數到11，最高位進一，再數三個數，在任何尺度下，兩個過程的結構是一樣的。

所以可以說，二進制解法可行的原因，至少是原因之一吧，并沒有唯一的正确解釋。但我覺得最自然的解釋是，寫出這些二進制數所用到的規律和解決漢諾塔問題所用到的規律，結構是一模一樣的。因此如果你去看比特的跳動方式，你實際上是在反過來思考，也就是在問，二進制數是怎麼寫出來的。就像當我想要理解比特是如何通過跳動來解答的時候，實際上你就是在逆向地找出漢諾塔的遞歸算法，這就是解法成功的原因。很酷對吧，不過其實還有更酷的，以後有機會的話我們再講這和謝爾賓斯基三角形之間的關系。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!