漢諾塔問題的遞歸解法是怎麼想出來的？

01-12

你把一堆碟片從 A 移動到 B，那麼你至少得移動最底下的那一片過去吧？因此你需要把上面的碟片先給挪開，然後把底下那一批擺好，再把上面的那些給放上。

而「移動上面的碟片」的過程和移動整個碟片堆過程是相同的，只是換了幾根柱子。

你翻任意一本書其實都是告訴你這個怎麼想的了只不過國內這幾本數據結構與演算法的書大多寫的晦澀難懂

懶人想起來的。比如領導要搞一個合同，他絕對是只管審閱加最後簽字，其他的讓部門經理去干。部門經理呢，只管審閱員工們各自負責的合同條款，交給領導。遞歸的切入點就在於每個人做好自己的事，其餘的扔出去。扔出去的部分工作實際上是下級部門的整體工作。

你可以下載這個手機遊戲玩一玩

一會就會發現規律了

比如A座有五個盤12345由小到大移到C座每次只能動一個大下小上

首先你一定得先把最大的5移到C座吖在一個個往上摞那麼你要操作這個步驟前提是C座上沒盤子（因為5最大）而且A座上只有A(每次只能動一個) 這樣的話，此時1234全在B上，又因為上小下大，所以1234按順序排列，移動完5,C就差不多相當於空了，畢竟5最大，1234隨意放在上面，同理，前一步123順序排列，這是往上摞，那麼，你怎麼1234（1，2，......n-1）順序排列，這就需要你在A座上一個一個往下拆，同理，比如拆4，那麼前一個步驟必然是45在A座有一個空座以待4坐入(123都小不能放4在上面) 那麼好巧這樣的話在剩下的那個座上123還得是順序排列（畢竟他們小被欺負只有一個座，）所以得出規律移一個1移倆個1拆+1移第二塊+1摞＝3 移三個3+1+3＝7 移四個7+1+7＝15 移動n個盤子2的n次方減一這應該是一個古典數學題有趣的就是條件這麼恰好三個柱子每次只能移一個大下小上所以最少的步數解決這個問題的話用邏輯推理每一個都是必然必須那麼走的條件都充分步步邏輯可推數學還是蠻有趣的雖然我說的有點亂沒表達清楚吧不知道對你有作用嗎

很容易就想到了，三個需要移7次，四個需要移15次，很容易就從中找出規律，然後就發現符合遞歸法

老師：「搬一個會不會」

學生：「會」

老師：「好！搬n個就是

1.先搬上面的n-1個到邊上擱著。

2.搬第n個到目標軸。

3. 把前面隔著的n-1搬回到第n個上面。

」