書名 Java於資料結構與演算法之實習應用

Presentation on theme: "書名 Java於資料結構與演算法之實習應用"— Presentation transcript:

1 書名 Java於資料結構與演算法之實習應用
書號　PG20098 原著　河西朝雄著 譯者　周明憲/徐堯譯 台北總公司／台北縣汐止市新台五路一段112號10樓A棟 Building A, 10F, 112, Shin-Tai-Wu Road Sec. 1, Shijr, Taipei, Taiwan. 電話／ 　傳真／ 台中辦事處／台中市文心路一段540號4樓-1 4-1F, 540, Wen Shing Road, Sec. 1, Taichung, Taiwan. 電話／ 　傳真／ 博碩網址：

2 第四章 學習重點 遞迴(recursion)是自己呼叫自己的意思，為無法知道結果的作業程序。在數學這種邏輯體系中，遞迴可簡單明快的定義出來，但人類的邏輯觀念卻不易跨越這個觀念。這樣看來，如果不熟悉遞迴演算法，就不容易理解遞迴觀念，但只要熟悉了遞迴的運作情形，在撰寫複雜的演算法時，就能發揮出其應有的效果。遞迴為現代程式設計中重要的控制結構之一。 本章從階乘、菲波納齊數列等單純的遞迴範例開始介紹，再說明透過遞迴快速地解開河內塔、迷宮等問題的方法。最後以遞迴來介紹說明速度很快的「快速排序法」。 遞迴真正發揮其威力的時候是在撰寫處理遞迴資料結構（樹Tree或圖形Graphic等）的演算法的時候。關於這點，將在第6章與第7章中說明。

3 4-0 何謂遞迴 遞迴結構(recursive structure)是指定義自己（n階）時，使用比自己低1階的部分集合來定義，而該部分集合又使用比自己低1階的部分集合來定義，如此反覆操作的結構。這種結構一般稱為遞迴(recursion)。

4 4-0 何謂遞迴 程式中的遞迴的結構如下： : rfunc(n,...); /* 遞迴程序的第1次呼叫 */ rfunc(n,...) {
4-0 何謂遞迴 程式中的遞迴的結構如下： : rfunc(n,...); /* 遞迴程序的第1次呼叫 */ rfunc(n,...) { if （脫離條件） /* 遞迴的出口 */ return rfunc(n,...) /* 遞迴呼叫 */ } 遞迴程序

5 4-1 遞迴的簡單例子 例題26 階乘的遞迴 以遞迴製作求n!的方法 n!可定義成： n!=n‧(n-1)! n>0 0!=1
4-1 遞迴的簡單例子 例題26 階乘的遞迴 以遞迴製作求n!的方法 n!可定義成： n!=n‧(n-1)! n>0 0!=1 其意義如下： ‧求n!時，先求出較低1次的(n-1)!，然後乘以n。 ‧求(n-1)!時，先求出較低1次的(n-2)!，然後乘以n-1。 ： ‧求1!時，先求出0!，然後乘以1。 ‧0!為1。

6 4-1 遞迴的簡單例子 改寫成如下的遞迴方法： long kaijo(int n) { if (n==0) return iL; else
4-1 遞迴的簡單例子 改寫成如下的遞迴方法： long kaijo(int n) { if (n==0) return iL; else return n*kaijo(n-1); } 0!的出口 求(n-1)的遞迴呼叫

7 4-1 遞迴的簡單例子

8 4-1 遞迴的簡單例子 long kaijo(int n) { // 遞迴函數 if (n==0) return 1L; else
4-1 遞迴的簡單例子 long kaijo(int n) { // 遞迴函數 if (n==0) return 1L; else return n*kaijo(n-1); } public void paint(Graphics g) { int n; for (n=0;n<13;n++) g.drawString(""+n+"!="+kaijo(n),10,n*20+20);

9 4-1 菲波納齊數列 練習問題26-1 菲波納齊數列 以遞迴求菲波納齊數列 下面的數列稱為菲波納齊數列：
練習問題26-1 菲波納齊數列 以遞迴求菲波納齊數列 下面的數列稱為菲波納齊數列： 這個數列的第n項為n-1項與n-2相加的結果，由於第1項及第2項均為1，因此以下的定義可以成立： fn=fn-1+fn-2 n≧3 f1=f2= n=1,2

10 4-1 菲波納齊數列 long fib(long n) { if (n==1 || n==2) return 1L; else
return fib(n-1)+fib(n-2); } public void paint(Graphics g) { int n; for (n=1;n<=20;n++) g.drawString(""+n+": "+fib(n),10,n*20);

11 4-1 以遞迴求nCr 練習26-2 nCr的遞迴 以遞迴求nCr 如同第1章1-1的Pascal三角形中所提到的，可定義成：
nCr = n-1Cr-1 + n-1Cr (n>r>0) rC0 = rCr = 1 (r=0 or n=r)

12 4-1 練習26-2 nCr的遞迴 long combi(int n,int r) { if (r==0 || r==n)
return 1L; else return combi(n-1,r)+combi(n-1,r-1); } public void paint(Graphics g) { int n,r; for (n=0;n<=5;n++) { for (r=0;r<=n;r++) g.drawString(""+n+"C"+r+"="+combi(n,r),r*60,n*20+20);

13 4-1 Horner法的遞迴 根據Horner法，多項式 f(x)=aNXN + aN-1XN-1 +…+ a1X1 + a0 可寫成：
fi=fi-1‧x+aN-1 f0=aN

14 4-1 Horner法的遞迴 class Dr26_3Panel extends Panel {
private final int N=4; // 階數 double fn(double x,double[] a,int i) { if (i==0) return a[N]; else return fn(x,a,i-1)*x+a[N-i]; } public void paint(Graphics g) { double[] a={1,2,3,4,5}; g.drawString(""+fn(2,a,N),10,20);

15 4-1歐基理德輾轉相除法的遞迴(1) 歐基理德輾轉相除法是根據「m、n這2個數的最大公約數可由這2個數的差與較小的數的最大公約數求出」的原理而產生的。將這步驟反覆操作直至m=n為止，這時的m值即為這2個數的最大公約數。 gcd(m,n)為求m、n的最大公約數之函數， 若m>n，則gcd(m,n)=gcd(m-n,n) 若m<n，則gcd(m,n)=gcd(m,n-m) 若m=n，則gcd(m,n)=m 以24與18為例來說明， gcd(24,18)=gcd(6,18) =gcd(6,12) =gcd(6,6) =6

16 4-1歐基理德輾轉相除法的遞迴(1) int gcd(int m,int n) { if (m==n) return m;
return gcd(m-n,n); else return gcd(m,n-m); }

17 4-1歐基理德輾轉相除法的遞迴(2) 如將歐基理德輾轉相除法中的m-n改成m%n，則效率會比較好。假設gcd(m,n)為求m、n的最大公約數之函數， 若m≠ n，則gcd(m,n)=gcd(n,m%n) 若n=0，則gcd(m,n)=m 以32與14為例來說明， gcd(32,14)=gcd(14,4) =gcd(4,2) =gcd(2,0) =2 本練習問題與練習問題26-4不同之處在於，本題不須區分m與n的大小，其原因為若m<n，則m%n為m，因此 gcd(14,32)=gcd(32,14)

18 4-1歐基理德輾轉相除法的遞迴(2) int gcd(int m,int n) { if (n==0) return m; else
return gcd(n,m % n); }

19 4-2 遞迴解法與非遞迴解法 例題27 階乘的非遞迴解法 不用遞迴來製作求n!的函數 由於 n!=n‧(n-1)‧(n-2)…3‧2‧1
4-2 遞迴解法與非遞迴解法 例題27 階乘的非遞迴解法 不用遞迴來製作求n!的函數 由於 n!=n‧(n-1)‧(n-2)…3‧2‧1 因此可以從1開始到n為止反覆乘以n次。

20 4-2 遞迴解法與非遞迴解法 long kaijo(int n) { int k; long p=1L;
4-2 遞迴解法與非遞迴解法 long kaijo(int n) { int k; long p=1L; for (k=n;k>=1;k--) p=p*k; return p; } public void paint(Graphics g) { int n; for (n=0;n<13;n++) g.drawString(""+n+"!="+kaijo(n),10,n*20+20);

21 4-2 菲波納齊數列的非遞迴解法 練習問題27 菲波納齊數列的非遞迴解法 不用遞迴來求菲波納齊數列
練習問題27 菲波納齊數列的非遞迴解法 不用遞迴來求菲波納齊數列 只要從a=1、b=1開始，反覆操作 a ← a+b a ← 前面的b 即可在b中求出菲波納齊數列。

22 4-2 菲波納齊數列的非遞迴解法 long fib(long n) { long a,b,dummy,k; a=1L;b=1L;
for (k=3;k<=n;k++) { dummy=b; b=a+b; a=dummy; } return b; public void paint(Graphics g) { int n; for (n=1;n<=20;n++) g.drawString(""+n+": "+fib(n),10,n*20);

23 4-3 排列組合的產生 例題28 排列組合的產生 1、2、3這3個數字的可組合成： 123、132、213、231、312、321
4-3 排列組合的產生 例題28 排列組合的產生 1、2、3這3個數字的可組合成： 123、132、213、231、312、321 等6個。這種組合稱為排列，n個（互相不同）組合的排列為n!。 1、2、...n個的排列問題如圖所示，可各分解成由以1～n為前頭的n-1個

24 4-3 排列組合的產生 如要使前頭具有1～n的值，需將數列的第1項～第n項的各項逐一交換。我們以1、2、3、4為例加以說明。
4-3 排列組合的產生 如要使前頭具有1～n的值，需將數列的第1項～第n項的各項逐一交換。我們以1、2、3、4為例加以說明。 1、2、3、4的排列為， ‧1與1交換分解成1、2、3、4中的2、3、4的排列問題 ‧1與2交換分解成2、1、3、4中的1、3、4的排列問題 ‧1與3交換分解成3、2、1、4中的2、1、4的排列問題 ‧1與4交換分解成4、2、3、1中的2、3、1的排列問題 而這種情形能以遞迴呼叫表現出來。進行遞迴呼叫之前，先要將第1項與第1項～第n項的各個交換處理作業放在一旁，遞迴呼叫結束後，也要放下已交換的樹列還原處理作業。 交換的基點i在遞迴呼叫達到一定深度時，會由1朝n，逐一的向右移動。

25 4-3 排列組合的產生 void perm(Graphics g,int i) { int j,t; if (i<N) {
4-3 排列組合的產生 void perm(Graphics g,int i) { int j,t; if (i<N) { for (j=i;j<=N;j++) { t=p[i];p[i]=p[j];p[j]=t; // p[i]與p[j]的交換 perm(g,i+1); // 遞迴呼叫 t=p[i];p[i]=p[j];p[j]=t; // 還原 } else { for (j=1;j<=N;j++) // 排列的顯示 g.drawString(""+p[j],j*20,y*16); y++; public void paint(Graphics g) { int i; for (i=1;i<=N;i++) // 初始設定 p[i]=i; perm(g,1);

26 4-3 按字典順序產生排列組合 例題28所產生的排列並不是按字典式的順序，如要將其改成按辭典順序排列，則須將第i項與第n項的交換作業轉換成i～i、i～i+1、i～i+2、...i～n逐一向右移動的作業。

27 4-3 按字典順序產生排列組合 void perm(Graphics g,int i) { int j,k,t; if (i<N){
for (j=i;j<=N;j++) { t=p[j]; // p[i]～p[j]的向右移動 for (k=j;k>i;k--) p[k]=p[k-1]; p[i]=t; perm(g,i+1); // 遞迴呼叫 for (k=i;k<j;k++) // 將陣列排列還原成遞迴呼叫前的狀況 p[k]=p[k+1]; p[j]=t; } else { for (j=1;j<=N;j++) g.drawString(""+p[j],j*20,y*16); y++; public void paint(Graphics g) { int i; for (i=1;i<=N;i++) // 初始設定 p[i]=i; perm(g,1);

28 4-4 河內塔 以遞迴解河內塔問題 河內塔問題常會在遞迴問題的討論中被提起。河內塔問題的定義如下： 設有a、b、c等3支棒，如圖4.10所示，已有n個中間有孔的圓盤按大小順序插入棒a，現將這些圓盤逐一移到棒b，但在移到棒b的途中，圓盤的大小順序必須反轉過來。而棒c只在移動過程中會用到。

29 4-4 河內塔

30 4-4 河內塔 hanoi(n,a,b,c); { if (n>0) { hanoi(n-1,a,c,b); (1)
4-4 河內塔 a→b至的移動 hanoi(n,a,b,c); { if (n>0) { hanoi(n-1,a,c,b); (1) 將第n個圓盤做a→b移動 (2) hanoi(n-1,c,b,a); (3) } 作業用的棒

31 4-4 河內塔

32 4-4 河內塔 void hanoi(int n,char a,char b,char c) { if (n>0) {
4-4 河內塔 void hanoi(int n,char a,char b,char c) { if (n>0) { hanoi(n-1,a,c,b); ta.setText(ta.getText()+ "將第"+n+"號板由"+a+"移往"+b+"\n"); hanoi(n-1,c,b,a); }

33 4-5 迷宮 僅尋找1個迷宮路徑的解

34 4-5 迷宮 將迷宮的每1格設為2維陣列的元素，□為可通過的格子，其值設為0，■為無法通過的格子，其值設為2，迷宮的縱向設為i，橫向設為j，迷宮內的位置則設為(i,j)。 由(i,j)位置前進到下1個位置時，會試著依照下列的 (1)、(2)、(3)、(4)等4個方向前進。如果其中1個方向可以通行就繼續前進，否則就走其他的方向。 如此反覆操作這項步驟，以走出迷宮。此外陣列元素須設為1，使前進作業不再通過已走過的位置。

35 4-5 迷宮 設拜訪(i,j)位置的步驟為visit(i,j)，走迷宮演算法的大致內容如下： (1) 將 (i,j)位置設為1
4-5 迷宮 設拜訪(i,j)位置的步驟為visit(i,j)，走迷宮演算法的大致內容如下： (1) 將 (i,j)位置設為1 (2) 在未到達迷宮出口以前，執行以下步驟： (3)若右邊是空的，則執行visit(i,j+1) (4)若下邊是空的，則執行visit(i+j,1) (5)若左邊是空的，則執行visit(i,j-1) (6)若上邊是空的，則執行visit(i-1,j) (7)若到達出口，則顯示通過的位置(i,j)。

36 4-5 迷宮 private int[][] m={{2,2,2,2,2,2,2}, {2,0,0,0,0,0,2},
4-5 迷宮 private int[][] m={{2,2,2,2,2,2,2}, {2,0,0,0,0,0,2}, {2,0,2,0,2,0,2}, {2,0,0,2,0,2,2}, {2,2,0,2,0,2,2}, {2,2,2,2,2,2,2}}; private int Si,Sj,Ei,Ej,success; int visit(int i,int j) { m[i][j]=1; //在已通過的位置上打記號 if (i==Ei && j==Ej) // 到達出口時 success=1; // 搜尋迷宮路徑 if (success!=1 && m[i][j+1]==0) visit(i,j+1); if (success!=1 && m[i+1][j]==0) visit(i+1,j); if (success!=1 && m[i][j-1]==0) visit(i,j-1); if (success!=1 && m[i-1][j]==0) visit(i-1,j); if (success==1) // 顯示通過點 ta.setText(ta.getText()+"("+i+","+j+")\n"); return success; }

37 4-5 將路徑顯示在通過順序內 例題30的程式由於會在遞迴呼叫時顯示儲存在堆疊內的i,j值，因此路徑會成為從出口而來的順序。我們將此設為由入口開始的順序。 設ri[]為儲存i的值的堆疊，rj[]為儲存j的值的堆疊，sp表儲存的大小。

38 private int[][] m={{2,2,2,2,2,2,2}, {2,0,0,0,0,0,2}, {2,0,2,0,2,0,2}, {2,0,0,2,0,2,2}, {2,2,0,2,0,2,2}, {2,2,2,2,2,2,2}}; private int Si,Sj,Ei,Ej,success,sp; private int[] ri=new int[100], // 儲存通過位置的堆疊 rj=new int[100]; int visit(int i,int j) { int k; m[i][j]=1; ri[sp]=i;rj[sp]=j;sp++; // 將通過位置儲存在堆疊 if (i==Ei && j==Ej) { // 到達出口時 for (k=0;k<sp;k++) // 顯示通過點 ta.setText(ta.getText()+"("+ri[k]+","+rj[k]+")\n"); success=1; } if (success!=1 && m[i][j+1]==0) visit(i,j+1); if (success!=1 && m[i+1][j]==0) visit(i+1,j); if (success!=1 && m[i][j-1]==0) visit(i,j-1); if (success!=1 && m[i-1][j]==0) visit(i-1,j); sp--; // 從堆疊中去除 return success;

39 4-5 搜尋所有的路徑 如要求出所有路徑，在進入死路或到達出口而返回原路時，可將已設為1的通過位置再重新設為0。圖中按 方向前進的時候設為1，以 返回原路的時候則傳回0。

40 private int[][] m={{2,2,2,2,2,2,2,2,2}, {2,0,0,0,0,0,0,0,2}, {2,0,2,2,0,2,2,0,2}, {2,0,2,0,0,2,0,0,2}, {2,0,2,0,2,0,2,0,2}, {2,0,0,0,0,0,2,0,2}, {2,2,0,2,2,0,2,2,2}, {2,2,2,2,2,2,2,2,2}}; private int Si,Sj,Ei,Ej,success,sp,path=1; private int[] ri=new int[100], // 儲存通過位置的堆疊 rj=new int[100]; int visit(int i,int j) { int k; m[i][j]=1; ri[sp]=i;rj[sp]=j;sp++; // 將通過位置儲存在堆疊 if (i==Ei && j==Ej) { // 到達出口時 ta.setText(ta.getText()+"path="+(path++)+"\n"); // 顯示通過點 for (k=0;k<sp;k++) ta.setText(ta.getText()+"("+ri[k]+","+rj[k]+"),"); ta.setText(ta.getText()+"\n"); success=1; } // 搜尋迷宮路徑 if (m[i][j+1]==0) visit(i,j+1); if (m[i+1][j]==0) visit(i+1,j); if (m[i][j-1]==0) visit(i,j-1); if (m[i-1][j]==0) visit(i-1,j); sp--; // 從堆疊中去除 m[i][j]=0; // 為了搜尋其他的路徑 return success;

41 4-6 快速排序 快速排序的原理為以數列中的適當的值（設其名稱為軸）為基準值，然後將比其小或相等的值置於其左側，將比其大或相等的值置於其右側。左側數列與右側數列再相對的反覆操作同樣的步驟，為了方便說明起見，我們將軸設為數列左側的值。

42 4-6 快速排序 設i為由數列左側巡察起的變數，j為由數列右側巡察起的變數，形成左側與右側數列的作業步驟如下：
4-6 快速排序 設i為由數列左側巡察起的變數，j為由數列右側巡察起的變數，形成左側與右側數列的作業步驟如下： (1) 將i設為數列左側+1，j設定成數列的右側 (2) 將數列向右操作，尋找有比軸大的值i的位置 (3) 將數列向左操作，尋找有比軸小的值j的位置 (4) 若i>=j，則脫離迴圈 (5) 將i項與j項互相交換 (6) 將左側的軸與j項互相交換

43 4-6 快速排序範例 交換結束後的i與j的關係如下：
4-6 快速排序範例 交換結束後的i與j的關係如下： 因此，在進行下一次交換的左側數列為從left開始j-1，右側數列為從j+1開始變成right，由於軸已在正確的位置上，因此在下交換時，便不會成為交換的對象。

44 void quick(int a[],int left,int right) {
int s,t,i,j; if(left<right) { s=a[left]; // 將左側的項設為軸 i=left;j=right+1; // 分成比軸較小的組與 while (true) { // 較大的組 while (a[++i]<s); while (a[--j]>s); if (i>=j) break; t=a[i];a[i]=a[j];a[j]=t; } a[left]=a[j];a[j]=s; // 將軸放入正確的位置 quick(a,left,j-1); // 對左側數列遞迴呼叫 quick(a,j+1,right); // 對右側數列遞迴呼叫 public void paint(Graphics g) { final int N=10; // 資料數 int[] a={41,24,76,11,45,64,21,69,19,36}; int k; quick(a,0,N-1); for (k=0;k<N;k++) g.drawString(""+a[k],30*k,20);