漢諾塔問題的算法,（漢諾）塔問題 這是一個(gè)古典的數(shù)學(xué)問題，是一個(gè)用遞歸方法解題的典型例子。問題是這樣的： 古代有一個(gè)梵塔，塔內(nèi)有3個(gè)座A、B、C，開始時(shí)座上有個(gè)盤子，盤子大小不等，大的在下，小的在上（見圖7.11）。有一個(gè)老和尚想把這個(gè)盤子從座移到座，但每次只允許移動(dòng)一個(gè)盤，且在移動(dòng)過程中在3個(gè)座上都始終保持大盤在下，小盤在上。在移動(dòng)過程中可以利用座，要求編程序打印出移動(dòng)的步驟。,此時(shí)老和尚只需這樣做： (1) 命令第2個(gè)和尚將63個(gè)盤子從A座移到B座； (2) 自己將1個(gè)盤子（最底下的、最大的盤子）從A座移到C座； (3) 再命令第2個(gè)和尚將63個(gè)盤子從B座移到C座。,老和尚想：假如有另外一個(gè)和尚能有辦法將63個(gè) 盤子從一個(gè)座移到另一座。那么，問題就解決了。,第2個(gè)和尚怎樣才能將63個(gè)盤子從A座移到B座？,他是這樣做的： (1) 命令第3個(gè)和尚將62個(gè)盤子從A座移到C座； (2) 自己將1個(gè)盤子（最底下的、最大的盤子）從A座移到B座； (3) 再命令第3個(gè)和尚將62個(gè)盤子從C座移到B座。,第2個(gè)和尚想：假如有另外一個(gè)和尚能有辦法將62個(gè)盤子從一個(gè)座移到另一座。我就能將63個(gè)盤子從A座移到B座。,如此“層層下放”， 直到找到第64個(gè)和尚，讓他完成將1個(gè)盤子從一個(gè)座移到另一座，至此問題解決,只有第64個(gè)和尚的任務(wù)完成后，第63個(gè)和尚的任務(wù) 才能完成。只有第2到第64個(gè)和尚任務(wù)完成后，第1 個(gè)和尚的任務(wù)才能完成。這是一個(gè)典型的遞歸問題,為便于理解：先分析3個(gè)盤子從座移到座的過程： (1) 將座上2個(gè)盤子先移到座上（借助）； (2) 將座上剩下的1個(gè)盤子移到座上； (3) 將座上2個(gè)盤子移到座上（借助）。,1.1 將上1個(gè)盤子從移到； 1.2 將上1個(gè)盤子從移到； 1.3 將上1個(gè)盤子從移到。,1.1,1.2,1.3,第1步 2個(gè)盤子從A移到B 可分解為：,3.1 將上1個(gè)盤子從移到上； 3.2 將上1個(gè)盤子從移到上； 3.3 將上1個(gè)盤子從移到上。,3.1,3.2,3.3,第3步 2個(gè)盤子從B移到C 可分解為：,綜合起來，可得到移動(dòng)3個(gè)盤子的步驟：,， ， ，。 共經(jīng)歷7步。 移動(dòng)n個(gè)盤子要經(jīng)歷2n-1步。,由上面的分析可知：將個(gè)盤子從座移到座可以分解為以下3個(gè)步驟： (1) 將座上n-1個(gè)盤子先移到座上（借助）； (2) 將座上剩下的1個(gè)盤子移到座上； (3) 將座上n-1個(gè)盤子移到座上（借助）。,第步，對應(yīng)關(guān)系是 ： one，two，three。 第步，對應(yīng)關(guān)系是: one，two，three。,上面3個(gè)步驟可分成兩類操作：,程序如下： #include void main() void hanoi(int n,char one,char two,char three); /* 對hanoi函數(shù)的聲明 */ int m; printf(“input the number of diskes:“); scanf(“%d”, ,void hanoi(int n,char one,char two,char three) /* 定義hanoi函數(shù),將個(gè)盤從one座借助two座，移到three座 */ void move(char x,char y); /* 對move函數(shù)的聲明 */ if(n=1) move(one,three); else hanoi(n-1, one , three , two); move(one,three); hanoi(n-1, two , one , three); void move(char x,char y) /* 定義move函數(shù) */ printf(“%c