起源
漢諾塔（又稱河內(nèi)塔）問題是源于印度一個(gè)古老傳說的益智玩具展氓。大梵天創(chuàng)造世界的時(shí)候做了三根金剛石柱子荞驴，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤策治。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上拐云。并且規(guī)定田炭，在小圓盤上不能放大圓盤查吊，在三根柱子之間一次只能移動(dòng)一個(gè)圓盤谐区。
抽象為數(shù)學(xué)問題
如下圖所示，從左到右有A逻卖、B宋列、C三根柱子，其中A柱子上面有從小疊到大的n個(gè)圓盤评也，現(xiàn)要求將A柱子上的圓盤移到C柱子上去炼杖，期間只有一個(gè)原則：一次只能移到一個(gè)盤子且大盤子不能在小盤子上面，求移動(dòng)的步驟和移動(dòng)的次數(shù)盗迟。
問題分析
當(dāng)n == 1時(shí)坤邪，
1. A---->C sum = 1 次
當(dāng)n == 2時(shí)，
1. A---->B
2. A---->C
3. B---->C sum = 3 次
當(dāng)n == 3時(shí)罚缕，
1. A---->C
2. A---->B
3. C---->B
4. A---->C
5. B---->A
6. B---->C
7. A---->C sum = 7 次
不難發(fā)現(xiàn)規(guī)律：移動(dòng)次數(shù)為：2^n - 1
遞歸算法
實(shí)現(xiàn)這個(gè)算法可以簡(jiǎn)單分為三個(gè)步驟：
把n-1個(gè)盤子由A 移到 B艇纺；
把第n個(gè)盤子由 A移到 C；
把n-1個(gè)盤子由B 移到 C；
Prolog實(shí)現(xiàn)
執(zhí)行prolog得到：
總結(jié)
prolog非常適合解決類似于邏輯推理的問題黔衡，例如數(shù)獨(dú)問題消约、八皇后問題，使用prolog實(shí)現(xiàn)非常漂亮员帮。接下來小編會(huì)邊學(xué)習(xí)邊實(shí)現(xiàn)相關(guān)代碼或粮，希望大家多多支持。
