演算法與資料結構之遞迴演算法
1.遞迴演算法的核心思想:
將問題轉化為同類問題的子問題進行求解。
2.遞迴演算法的應用:
- 漢諾塔
3.問題分析:
1.漢諾塔問題:
描述:64個盤子從a移到c,要求一次只能移動一個盤子,並且小盤子在上,大盤子在下。
編寫功能函式:
void hanoi(int n,char a,char b,char c)
- 含義:
n:盤子數量。
a,b,c:三個軸。 -
思路:
n=1時,只需要將盤子從a移動到C即可。記作:a->c。
n>1時,進行如下思考:
技巧:
我們知道裝大象的步驟如下:
1.開啟冰箱
2.裝大象
3.關冰箱門
觀察如下圖:
接下來,我們將要開啟冰箱
我們發現當n=2時,漢諾塔遊戲可以抽象成一個裝大象的過程,過程及其簡單易懂。
事實上,無論n為多少,我們都可以吧漢諾塔抽象成兩個來看,也就是將兩個看成一個整體!
而那兩個模組(冰箱)我們又可以把它看成一次大象裝冰箱的過程,也就是說3個盤子模組會實現2次裝大象的過程。
隨著盤子數量越來越多,裝大象的過程越來越多,我們可以利用函式呼叫自身函式達到重複迴圈裝的作用,當然你也可以選擇for迴圈,我們這裡討論遞迴思想。
語句等價翻譯
hanoi(n-1,a,c,b);//該語句代表開啟冰箱! a->c;//該語句代表裝大象! hanoi(n-1,b,a,c);//該語句代表關冰箱門!
具體分析:
hanoi(n-1,a,c,b):表示將冰箱從a這個地方繞過c軸到達b軸這個地方。其中n-1代表冰箱!
a->c:表示將a軸上的最後一個模組盤子(最大的,最底部的大象)直接送到c軸上去!
hanoi(n-1,b,a,c):表示將b軸上的的冰箱繞過a關到c軸上!
以上分析表示了裝大象的過程,也是漢諾塔遊戲的過程。
4.hanoi函式的具體實現:
void hanoi(int n, char a,char b,char c)//定義hanoi函式 { if(n==1) printf("%c->%c",a,c);//如果只有一個盤子,也就是說只有大象沒有冰箱門的時候,直接把大象裝進冰箱裡 else { hanoi(n-1,a,c,b);//開啟冰箱 printf("%c->%c",a,c);//裝大象 hanoi(n-1,b,a,c);//關冰箱門 } }
5.主函式的實現:
#include<stdio.h> int main() { int n; printf("請輸入盤子個數:\n); scanf("%d",&n); hanoi(n,a,b,c);//呼叫函式 return 0; }
6.程式碼實現: