一個(gè)n層的漢諾塔毕籽，從A移動(dòng)到C
由于漢諾塔問題本身的限制抬闯，我們最先能思考到的點(diǎn)是第n層最后肯定是要放在C的最下面的
有了這個(gè)思考后井辆，我們又想，要想使?jié)h諾塔移動(dòng)次數(shù)最小
—— —— —— ——? ? ? ? ? ? ? ? ? ? ? ? ? 溶握？杯缺？？? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 空? ? ? ? ?
? ? ? ? ?A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? B? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? C
那么我們就要滿足可以A中只剩下n這一張圓盤了睡榆，而C中是空的萍肆，那么我們就可以直接將A中這一張圓盤直接放入C中
OK，A.C的結(jié)構(gòu)確定了肉微，那B的結(jié)構(gòu)是什么呢匾鸥？
很顯然，由于漢諾塔的特性碉纳，所以B中此時(shí)是n-1層的漢諾塔
我們?cè)賹中的n-1層漢諾塔移動(dòng)到C中即可勿负，這個(gè)操作完全等同于將n-1層漢諾塔從A中移動(dòng)至C，且B,C為空這一初始條件
因?yàn)锽中的n-1層圓盤本身滿足漢諾塔結(jié)構(gòu)劳曹，且第n-1層是小于C中的第n層的也就是可以將C也看成是空的奴愉，所以我們可以亂放，怪放铁孵，無限放锭硼，終極放，究極皮皮放蜕劝！
OK檀头，我們還要考慮的是從A中移動(dòng)n-1層到B，這個(gè)問題和從A中移動(dòng)n-1層到C完全一樣ａ妗Ｊ钍肌！
所以拋開第n個(gè)圓盤從A移動(dòng)到C這一個(gè)操作外
我們還有從A移動(dòng)整個(gè)n-1層漢諾塔到B婴削，然后從B將整個(gè)n-1層漢諾塔移動(dòng)到C的這兩步操作廊镜！
OK，無論你叫他遞歸問題也好唉俗，DP問題也好嗤朴，我覺得更像是遞歸問題，但我還是寫成DP的樣子把
DP[n] = 2*DP[n-1]+1
寫成遞歸就好
def hanoi(n):
? ? if n == 1:
? ? ? ? return 1
? ? result = 0
? ? result += hanoi(n-1)
? ? return result
如果告訴你漢諾塔盤隨機(jī)地分布在三個(gè)柱子上（前提條件是滿足每個(gè)柱子上依然滿足漢諾塔結(jié)構(gòu)）虫溜，然后問當(dāng)前狀態(tài)是不是漢諾塔從A移動(dòng)到C的必經(jīng)狀態(tài)雹姊，如果不是返回-1，如果是衡楞，返回是當(dāng)前的第幾步
可以這樣思考容为，假設(shè)第二個(gè)柱子上出現(xiàn)了n號(hào)盤子，我們可以肯定的是它不是必經(jīng)狀態(tài)因?yàn)榈趎號(hào)盤子肯定是直接從A移動(dòng)到C的
OK有了這個(gè)思路就好辦了
我們記主柱子為main,輔助柱子為sup，目的柱子為tar
這樣記錄是有目的的
假設(shè)三個(gè)漢諾塔是這樣的結(jié)構(gòu)
A:main:[X? ? X]
B:sup:[X? ? X]
C:tar:[X? ? X]
假設(shè)總共有6號(hào)盤子坎背，由上面的結(jié)論，從A移動(dòng)6個(gè)盤子到C中總共需要2^6-1 = 63種
我們檢查最大的數(shù)6在哪個(gè)位置
我們知道的是從A將第6號(hào)盤子移動(dòng)到C中是第（63+1）//2? ?+1? =? ?32步寄雀，
如果6處在sup中得滤，肯定返回-1，
不是的話盒犹，我們?cè)倏?處在哪個(gè)位置
假設(shè)6處在tar中懂更，我們可以認(rèn)為，它可能是將n-1層漢諾塔從sup（B）移動(dòng)到tar（C）的一個(gè)中間過程
那么這個(gè)狀態(tài)就有可能是第34步到第63步中的某一步
記住我們現(xiàn)在的目標(biāo)是從B中將5層漢諾塔移動(dòng)到C中急膀，那么此時(shí)就與第6個(gè)漢諾塔無關(guān)
我們將tar中隊(duì)列最前面的數(shù)字彈出tar.pop(0)
且現(xiàn)在的主柱子是B沮协，目標(biāo)柱子是C，輔助柱子是A卓嫂，即
A:sup[X? ? X]
B:main[X? ? X]
C:tar[X]
同樣的慷暂，我們看5在哪，如果5在A中晨雳，即輔助柱中行瑞，肯定沒戲，如果在主柱子中餐禁，那么肯定在第32到（63-32+1）//2 +1步中
如此循環(huán)
因此我們的程序應(yīng)該是這樣的
因?yàn)閺腁移動(dòng)n個(gè)到C中血久，所以我們記A為主，B為輔帮非，C為目標(biāo)氧吐，且把所有的盤子按1到n進(jìn)行標(biāo)號(hào)，
將狀態(tài)放入A.B.C三個(gè)列表中
main = [X,X,X,X,X]
sup? ?= [X,X,X,X,X,X,X]
tar? ? ?= [X,X,X,X]
兩個(gè)指針記錄區(qū)間
left = 1,right = 2^n-1
當(dāng)left和right重合時(shí)末盔，就是找到的次數(shù)
while? ? left筑舅！? !=????right:
? ? ? ? #如果n在輔助隊(duì)列中直接返回不在必經(jīng)之路上
? ? ? ? if? ? n? ? in? ? sup:
? ? ? ? ? ? ? ? return -1
? ? ? ? #如果n在主隊(duì)列中，將右區(qū)間縮減到原區(qū)間的終點(diǎn)的左側(cè)
? ? ? ? #且? ? 將目標(biāo)隊(duì)列和輔助隊(duì)列交換位置
? ? ? ? #且? ? 將n從main中彈出
? ? ? ? elif? ? n? ? in? ? main:
? ? ? ? ? ? ? ? right? ? =? ? (left+right)//2-1
? ? ? ? ? ? ? ? main.pop(0)
? ? ? ? ? ? ? ? sup,tar? ? =? ? tar,sup
? ? ? ? ?elif? ? n? ? in? ? tar:
? ? ? ? ? ? ? ? ? ? left? ? =? ? (left+right)//2+1
? ? ? ? ? ? ? ? ? ? tar.pop(0)
? ? ? ? ? ? ? ? ? ? sup,main? ? =? ? main,sup
reuturn left
考慮了一會(huì)兒庄岖，發(fā)現(xiàn)上面一個(gè)漏洞
我們的left和right都是指移動(dòng)了多少步
而最原始的狀態(tài)應(yīng)該表示移動(dòng)了第0步
所以left的初始值應(yīng)為0
