標題 淺談漢諾塔問題，以及對其遞回的分析
首先談談漢諾塔這個問題，這個問題是印度的一個古老的傳說，開天辟地的神勃拉瑪在一個廟里留下了三根金剛石的棒，第一根上面套著64個圓的金片，最大的一個在底下，其余一個比一個小，依次疊上去，廟里的眾僧不倦地把它們一個個地從這根棒搬到另一根棒上，規定可利用中間的一根棒作為幫助，但每次只能搬一個，而且大的不能放在小的上面，面對龐大的數字(移動圓片的次數)18446744073709551615，看來，眾僧們耗盡畢生精力也不可能完成金片的移動，后來，這個傳說就演變為漢諾塔游戲，
作為一個green hand，拿到這題的時候我是有些茫然的，感覺無從下手，沒有什么思路，然后我就隨手畫了3個柱子，3個盤子，沒一會就成功了，但這并沒有真正的成功，因為我的這次成功是慢慢的嘗試出來的，后來我就多畫了幾個盤子，慢慢嘗試，總結其中的規律，經過一下午的探索，也算有了一點淺薄的心得，下面我就來談談，
很明顯，這個問題需要用到遞回才能解決，而用到遞回的問題，往往可以使其簡單化，把一個復雜的問題轉化為一個個相似而簡單的小問題，而這，也正是其中之一的難點，首先要想到怎么轉化這個復雜的問題，經過一系列的嘗試后，我發現，要想解決這個問題，你總是要把最大的盤子上的小盤子想辦法移到中間的柱子上，然后再將最大的那個移到最后的一根柱子上，至此，也就發現了其中的共性點，
下面給出圖示，以便理解
**
這其中最重要的一步就是一定要將最大的一個盤子移到c柱上，下面談談我對這一步重要性的理解，其實想到這時，我不禁想到了線性代數上行列式的計算，如果要計算一個4階行列式，顯然是很復雜的，但我們可以利用代數余子式將其轉化為幾個3階行列式的和，這樣就簡便了運算，
這個問題中也是用到了同樣的思想，當把最大的單獨移到最后一個柱子上時，那樣我們就不需要考慮那個盤子了，因為那個盤子是所有盤子中最大的，然它此時正在最下面，所以如圖5個盤子的問題，當到圖2那一步后，也就轉化為4個盤子的問題.
此時也就成了這樣
此時又可以轉化一下思維，我們不妨將A,B,C三個柱子換下順序，因為這樣并不會影響結果，
此時5個盤子的問題就轉化成4個盤子的問題了，以此方法類推，最后就可以解決漢諾塔的問題了，
以上是整個問題的演算法，以及是如何想到的，接下來就是寫程式了
void move(char c1, char c2);
void hannuo(int n, char x, char y, char z)
{
if (n == 1)move(x, z); //遞回截止條件
else
{
hannuo(n - 1, x, z, y);//將 n-1個盤子先放到B座位上
move(x, z);//將A座上地剩下的一個盤移動到C盤上
hannuo(n - 1, y, x, z);//將n-1個盤從B座移動到C座上
}
}
void move(char c1, char c2)
{
printf("%c--->%c\n", c1, c2);
}
int main()
{
int n;
printf("input your number");
scanf("%d", &n);
hannuo(n, 'a', 'b', 'c');
return 0;
}
#下面來分析下這個代碼里面的遞回部分
然后我用代碼運行了一下，驗證了一下分析，與分析完全一致.
其實我個人覺得做這種遞回的題目一開始要研究的透徹一些，往后題目做多了，代碼見多了，有一定的經驗了，其實沒必要像上面分析的這么細致，因為那時已經大致培養出了一種感覺了，不需要這樣仔細的分析了.
最后，也到這，也就到了尾聲了，這是我第一次寫博客，希望各位老鐵可以給個贊，關注一下，希望多年后看到這篇博客時可以說一句，年少的感覺真好啊！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/251707.html
標籤：其他
上一篇：有 1000 瓶藥物，但是其中有一瓶是有毒的，老鼠只要服用任意量有毒藥水就會在一個星期以后死掉！請問，在一個星期內找出有毒的藥 物，最少需要多少只小白鼠？