遞迴 01010 10101 01010 10101 01010 10101.

Presentation on theme: "遞迴 01010 10101 01010 10101 01010 10101."— Presentation transcript:

1 遞迴 01010 10101 01010 10101 01010 10101

2 遞迴的意義&設計步驟 重覆呼叫(執行)自己本身的程式片段(函數)，直到符合終止條件為止 撰寫遞迴程式的步驟: 邊際條件(最簡單情形)的解法
定義函數的參數(傳入值)和傳回值 將大小為n的問題以更小的問題(如n-1)來解答 PS.遞迴呼叫前,先檢查邊際條件,以免無窮呼叫

3 求1+2+3+...+n=? 解析 傳回值 函數名 參數 邊際條件是n=1時,總合為1 該函數可定成int sum(int )
sum(n) = n + sum(n - 1) int sum(int n) { if (n == 1) return 1; else return n + sum(n - 1); } sum(5)=15 sum(4)=10 sum(3)=6 sum(2)=3 sum(1)=1 求sum(5) 求sum(4) 求sum(3) 求sum(2) 求sum(1) n=5 5+sum(4) n=4 4+sum(3) n=3 3+sum(2) n=2 2+sum(1) n=1 return 1

4 1*2+2*3+3*4+…+(n-1)*n之和 解析 第n項 第2項 傳回值 參數 邊際條件:n=1,和為0(0*1)
該函數可定成int sum(int ) sum(n) = (n-1)*n + sum(n-1) int sum(int n) { if (n == 1) return 0; else return n*(n-1)+sum(n-1); } 傳回值 參數 函數名

5 求兩個整數m,n的最大公因數? 解析 傳回值 函數名 參數 如果n==0,則最大公因數為m int , int gcd(int , int)
gcd(m , n)=gcd(n , m%n) int gcd(int m, int n) { if (n == 0) return m; else return gcd(n, m%n); } 輸入m,n兩數後,需先判斷n=0? m>n ? … Why?

6 進階 01010 10101 01010 10101 01010 10101

7 河內塔 有三根柱子(A,B,C),n個大小不一樣的碟子,一開始時所有n個碟子以大下小上排在某根柱子(A)上。限制一次只能移動一個碟子,且不違反大下小上的原則,如何把這n個碟子全部移到另一根柱子上 遞迴的要點 已知邊際條件(最簡單的情況)如何解 假設某函數已經能解大小為n的問題,也就是要決定此函數的參數和傳回值。 如何利用大小為n的解法,來解更大的問題(n+1)

8 河內塔 當河內塔的碟子數為0時,問題已解(沒東西好搬了)。
假設三根柱子以int from,to,another來表示,碟子數為n時,要這些碟子從from柱子搬到to柱子,解此問題的函數為 move(n,from,to,another) 如何解n+1個碟子的問題呢? 我們可以把n個碟子由from搬到another 把最底下(n+1)的由from搬到to 把n個碟子由another搬到to 為甚麼上面的搬法沒問題? 當我們搬上面n個碟子時,留在from柱子上的是較大的一個碟子,因此不論我們如何搬動n個碟子,一定不會違反規則(下大),也就是說可以把最底下的當作不存在,好像地板一樣

9 輸入n=0或n<0時,程式停止 邊際條件 printf("move %d to %d\n", from, to);
… void move(int n, int from, int to, int another) { if (n > 0) { move(n - 1, from, another, to); move(n - 1, another, to, from); } int main() { int n=0; while (scanf("%d",&n) > 0) move(n,1,2,3); return 0; printf("move %d to %d\n", from, to); 輸入n=0或n<0時,程式停止