要想弄清楚漢諾塔的遞回問題，我們就先得游戲的規則入手：有A,B,C三座，將塔A上N個從小到大疊放的盤子移動到塔C，一次只能移動一個，不重復移動，小盤子必須在大盤子上面，
首先，我們不談復雜的情況，我們先用最“笨”的方法來完成漢諾塔游戲，
當N=1時
很簡單，當漢諾塔只有一層，我們毫不猶豫的將塔A上的移動到塔C，sum=1；
當N=2時
我們利用B作為中轉站，把第一塊移動到B，接下來把第二塊移動到C，再把第一塊從B移動到C，sum=3；
當N=3時
我們進行如下的操作：
第一塊：A->C
第二塊：A->B
第一塊：C->B
第三塊：A->C
第一塊：B->A
第二塊：B->C
第一塊：A->C
可得sum=7;
當我們解決漢諾塔有三層的問題時，發現存在著一個中間程序，即第一塊和第二塊一起被放在了中轉站B上，若把這個狀態看作一個程序，那么三層漢諾塔不就可以被看作先移動二層漢諾塔，再移動第三層漢諾塔，再將中轉站上的二層漢諾塔移動到C上了嗎？而移動二層漢諾塔的次數是固定的，我們設移動三層漢諾塔的次數為 H3 ,移動二層漢諾塔的次數為 H2 ,于是我們有 H3 = 2 × H2 +1 . 
要解決三層漢諾塔問題，我們就先得解決兩個二層漢諾塔問題再加上1，要解決二層漢諾塔問題，我們就得解決兩個一層漢諾塔問題再加上1，以此類推，若要解決三層以上的漢諾塔問題，歸根結底都是要解決一層漢諾塔的簡單問題，
當N=n時
要解決n層漢諾塔問題，就得解決 2個 n-1 層漢諾塔問題和移動1次第 n 個漢諾塔，而這時問題就被拆解為只需研究 n-1 層漢諾塔的問題了 ，而 n-1 層漢諾塔可以一直繼續拆解，一直拆解到當 n=1 的時候， 遞推公式由此而來，可得Hn = 2× Hn-1 +1, 利用數學方法，可求得通項公式 Hn = 2n -1.
下面是遞回程式的具體實作：
#include<stdio.h>
int hanoi(char A, char B, char C, int n)
{
if (n == 1)
{
return 1;
}
return hanoi(A, C, B, n - 1) + hanoi(B, A, C, n - 1) + 1;
}
int main()
{
int n;
scanf("%d", &n);
int sum = hanoi('A', 'B', 'C', n);
printf("%d\n",sum);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/252042.html
標籤：其他