第八章 方法 在程式設計時，常會遇到某些程式片段需要在同一個類別或不同的類別重覆出現許多次，如果這些程式片段都分別在每個地方寫一次，那是一件非常浪費時間的事，且會使程式變得冗長而不易閱讀。更糟的是，萬一要調整此程式片段的部份功能，更要至不同的地方修改，造成程式維護困難，此時可透過本章所要介紹的方法解決以上困難。方法的使用方式為將此常用的程式片段賦予一個名稱，此稱為方法名稱，寫在某一類別的最前面或最後面，當程式設計者需要使用此程式片段時，只要鍵入此方法名稱，即可執行此程式片段。

8-1 方法的設計與呼叫 方法的設計簡要語法如下： [存取範圍修飾字] 傳回值型別方法名稱(參數列){ 敘述1； 敘述2； 8-1 方法的設計與呼叫 方法的設計簡要語法如下： [存取範圍修飾字] 傳回值型別方法名稱(參數列){ 敘述1； 敘述2； return 傳回值； 敘述n； } 以上語法說明如下：

存取範圍修飾字 存取修飾字是可以省略的，常用的存取範圍修飾字有public、private及protected，關於存取範圍修飾字，請看9-2與9-3節。

傳回值型別 方法可能會有傳回值，傳回值型別即為規範此傳回值的型別，若該方法未有傳回值，則應使用保留字void。

方法名稱 方法名稱應滿足3-1節的識別字命名規則。

參數列 當呼叫此方法時，所要傳遞的參數，請放在參數列。關於參數列的進一步用法請看8-2節。 以下程式片段即為判斷所傳入參數d是否及格，d在此稱為形式參數(Formal Parameter)，方法名稱為work，傳回值型別為String。 static String work(int d) { //static之用法詳見第9章 String e="不及格"; if (d >= 60) e="及格"; return e; }

以下程式片段可印出“Office XP快樂上手”，方法名稱為printBook，沒有參數的傳遞，亦未有傳回值。 void printBook(){ System.out.println(“Office XP快樂上手”) }

方法的呼叫 方法的呼叫為鍵入方法的名稱與參數列，並用適當的變數接收方法的傳回值。例如，以下程式片段可呼叫以上的work()方法，並以b接收所傳回的值。 String b; b=work(78); 以上程式會呼叫work()方法，並且將常數78指定給work()方法中的形式參數d。此外，參數亦可用變數，此稱為實際參數(Actual Parameter)，且實際參數的型別與形式參數的型別應相同。例如，以下程式片段亦可呼叫work()方法。 int a=78; b=work(a);

以上均使用變數接收方法所傳回的值，若不接收方法所傳回的值，亦可直接鍵入方法名稱。例如，以下敘述並不接收回傳的值，而是將回傳的值直接輸出。 System.out.println(work(78)); 以下程式片段可呼叫不用傳遞參數的printBook()方法。 printBook();

範例8-1a 請以呼叫方法的方式重作範例5-1a。

範例8-1b 請以呼叫方法的方式重作範例5-4a

8-2 參數的傳遞 Java對於參數的傳遞有兩種方式。首先，參數若是內建資料型別，則以傳值呼叫(Call By Value)。其次，參數若是陣列與物件，則是採用傳址呼叫(Call By Reference)。

傳值呼叫 傳值呼叫是將該筆資料複製一份，然後將複製的資料傳給指定的方法，所以該方法對所傳遞的參數若有異動，亦不會影響主程式的值。例如，swap 方法如下，其功能是將所傳入的參數交換。 void swap(int a,int b) { int t; t=a;a=b;b=t; System.out.println(a); //4 System.out.println(b);//3 } 其次，主程式如下： int p=3,q=4; swap(p,q); System.out.println(p); //3 System.out.println(q);//4 以上即為傳值呼叫，主程式只將參數傳給方法，方法對參數的異動並不回傳。

傳址呼叫 傳址呼叫則是將原始資料的位址傳遞至對應的方法，所以若該方法對該參數有所異動，皆可將異動的結果回傳主程式。以下將分別示範物件與陣列的船址呼叫。

物件的傳址呼叫 首先，實做Object 類別如下：（關於類別的使用請看第九章） class Object { int p,q; } 其次，實做swap 方法如下，其功能為將所得的參數交換。 void swap (Object ob) int t; t=ob.p;ob.p=ob.q;ob.q=t;

以上即為參數是物件的傳址呼叫，方法內對參數的異動，將可回傳主程式，所以p,q成員已經是交換的結果。 最後，主程式如下： Object obj=new Object(); obj.p=3; obj.q=4; swap(obj); System.out.println(obj.p); //4 System.out.println(obj.q); //3 以上即為參數是物件的傳址呼叫，方法內對參數的異動，將可回傳主程式，所以p,q成員已經是交換的結果。

陣列的傳址呼叫 首先，實做doubleData 方法如下： doubleData(int b[]) { int i; for (i=0;i<=4,i++) b[I]=b[I]*2; } 其次，主程式如下： int a[]={0,1,2,3,4}; doubleData(a); for (int i=0;i<=4;i++) System.out.println(a[i]); //0 2 4 6 8 以上即為參數是陣列型別的傳址呼叫，方法內對參數的異動，將可回傳主程式，所以主程式中的陣列值皆已經改變。

範例8-2a 示範內建資料型別的傳遞。

範例8-2b 示範陣列的傳址呼叫。

範例8-2c 示範物件的傳址呼叫。（本例可待第九章的類別研讀之後再看，較容易理解）

8-3 遞迴 於類別的方法中，若呼叫自己的方法，則稱此類程式稱為遞迴。遞迴的使用必須同時滿足以下兩個條件，否則程式會沒完沒了，終至堆疊用盡而使程式當掉。使用遞迴解題的兩個條件如下： 1. 問題須具有重複的特性，也就是在某些特性之下，可以繼續呼叫自己。 2. 重複的問題須有結束的條件。如階乘的結束條件為n=1時1!=1，費式數列的結束條件為n≦2時f(2)=1，f(1)=1。

階乘 階乘的定義是求小於等於某一數至1的連續整數之積。本例重複的特性為每次減1，即可自己呼叫自己。例如， 6!=6*5! 5!=5*4! 本例結束遞迴的條件是當遞減至1時，結束遞迴。所以，其演算法如下： public static int product(int n) { if (n==1) return n; else return n*product(n-1); }

範例8-3a 請使用遞迴求某一整數的階乘。 例如6!=6*5*4*3*2*1

費式數列 費式數列的定義如下： 當n≧3時，則分解為2項，如下： fn = fn-1 + fn-2 依以上定義，費氏數列前10項如下： 1，1，2，3，5，8，13，21，34，55 例如，以n=5，解說如下：

= f(4)+f(3) f(4)繼續分解，f(3)先放在堆疊。 = f(3)+f(2)+f(3) f(5) n=5，分解成兩項，如下： = f(4)+f(3) f(4)繼續分解，f(3)先放在堆疊。 = f(3)+f(2)+f(3) f(3)繼續分解，f(2)=1，後面的f(3)還是在堆疊。 = f(2)+f(1)+1+f(3) f(2)=1，f(1)=1，f(3)從堆疊取之分解。 = 1+1+1+f(2)+f(1) f(2)=1，f(1)=1，堆疊已空無一物，離開方法， 並傳回結果5。 = 5 以上說明的演算法如下： static int product(int n) { int p; if (n>2) p=product(n-1)+product(n-2); else p=1; return (p); }

範例8-3b 請用遞迴法求費式數列(Filbonacci)的第n項。

二分猜值法 1.二分猜值法的演算法如下： （1）設求解的正數為x2，則其平方根必在x1=0與x2之間。 （5）重複步驟（2）、（3）、（4），直到〔x1，x2〕的範圍很小為止，此時的x1或x2即為平方根。 2. 以實例9分析如下： （1）根必在0與9之間。 （2）首先猜4.5，因4.5的平方大於9，表示猜的太大所以縮小範圍為〔0，4.5〕。 （3）其次猜2.25，因2.25的平方小於9，表示猜的太小，所以縮小範圍為〔2.25，4.5〕。 （4）重複以上動作，直到猜值的範圍很小時，此範圍內的任意數即為解。

3.以上說明的演算法如下： tatic double sqrt(double x1,double x2,double x3) {   if (Math.abs(x1-x2)<=0.1) return (x1);   x=(x1+x2)/2;   if (x*x-x3<=0)  return(sqrt(x,x2,x3));   else  return(sqrt(x1,x,x3)); } 若要提升精確度，只要將0.1變小即可。例如，調整為0.000001,即可提高精確度。

範例8-3c 請用二分猜值法，求解平方根。

迴圈的二分猜值法 同理，若要提升精確度，只要將0.1變小即可。例如，調整為0.000001,即可提高精確度。 使用迴圈的二分猜值法，其演算法如下：  double x1=0,x2,x3,x; x2=Integer.parseInt(str); //欲求解的平方根 x3=x2; while (Math.abs(x1-x2)>0.1) { x=(x1+x2)/2; if (x*x -x3<0) x1=x; //猜的太小，調整下界為 x else x2=x; //猜的太大，調整上界為 x } System.out.print(“其平方根值為 ”); System.out.println(x1); 同理，若要提升精確度，只要將0.1變小即可。例如，調整為0.000001,即可提高精確度。

範例8-3d 同上範例，但不使用遞迴。

範例8-3e 請以遞迴法重作範例6-2c中兩數的最大公因數。

8-4 多型 (Polymorphism) 多型(Polymorphism)有些書譯成同名異式，它的原文是希臘文，意思是說，一種樣式有多種表現方式。例如，你有一個僕人專門幫你開門，那麼不論這個門是內推、外拉或向旁邊推，你都是下同一指令“開門”，然後你的僕人即會依照門的結構而完成開門的動作。物件導向的程式設計亦發揚此理念，讓程式設計者於程式設計階段使用相同的指令，而編譯器能於執行階段依據不同的需求，執行不同的程式片段，此即為多型。於Java有許多種多型的效果，本書僅舉三種例子，分別是多載(Overloading)與改寫(Overriding)及介面（改寫請看9-3節，介面請看9-4節）。

方法多載 (Overloading Methods) 於方法的設計裏，有時會有兩種以上的方法功能接近，例如只是參數型別或參數個數不同，是否可以使用相同的方法名稱，以減少程式設計者的困擾？答案是肯定的。因為物件導向的程式設計均允許程式設計者在參數型別與參數個數不同時，使用相同的方法名稱，這些相同的方法即稱為方法多載。例如，若以實做add 方法如下： int add(int c,int d); (1) 亦可在實做add方法如下： int add(int c,int d,int e) (2) double add(int c,int d,double e) (3)

其次，當呼叫add方法時，編譯器集會依照參數的數量與型別，而呼叫對應的方法。例如， 即會執行以上第（1）式。而， add(3,4,5); 即會執行以上第（2）式。同理， add(3,4,3.4) 即會執行以上第（3）式。但是，當有相同的參數個數與型別時，絕不可有相同的船回值。例如，絕不能在實做add 方法如下： double add(int c,int d);

以下範例將示範方法的多載。其次，Java類別庫所提供的方法，亦有許多多載的實例，例如Applet類別的Play方法，即有2種多載，如下所示。 public void play(URL url)public void play(URL url, String name)

範例8-4a 示範方法多載。

8-5 抽象化 (Abstraction) 將具體的東西，依據某一需求或意念，以另一具體的成果表現，稱為抽象化。例如，當你看到某處某一幅景色，而要將此景色描述下來，你當然不可能鉅細靡遺的所見即所得，而是有所取捨的描繪此景色，當你完成此畫時，你即完成此景色的抽象化，而你那張畫當然稱為此景色的抽象畫。其次，每個人抽象的程度也都不同，有的人連地上的垃圾都不放過，有的人希望不同時代或背景的人有不同的體會，這就是為什麼畢卡索的畫可以流傳至今，還廣受人們討論。程式設計領域的最高境界何嘗不應如此，你的觀念或程式，是否能讓不同背景或不同需求的使用者都能使用這一程式，且這些不同需求的人都可能得到他們所要的結果，此即為抽象化的最高境界。 本章已介紹方法、遞迴、多載，下一章將介紹類別、繼承、改寫與介面，這些都是程式設計的抽象化工具，還盼讀者進一步琢磨與體會，而能在程式設計的領域創造超越畢卡索的成就，使你的觀念或作品流傳後世。

8-6 實例探討

漢諾塔 如下圖有三根柱子A、B及C，A柱有幾個大小逐一遞增的套環，現在要將A柱的套環逐一搬至B柱，且要遵守以下規則： 1. 一次只能搬一個套環，且只有最上面的套環可以被搬動。 2. 每個柱子被置入套環時，套環僅能由小而大排列。也就是不可以有較大的套環壓到較小的套環。

如上圖，若A柱有3個套環，要將A柱上的所有套環移至B柱，則其過程如下： 1. 將Ring 1由A搬到B。 2. 將Ring 2由A搬到C。 3. 將Ring 1由B搬到C。 4. 將Ring 3由A搬到B。 5. 將Ring 1由C搬到A。 6. 將Ring 2由C搬到B。 7. 將Ring 1由A搬到B。

以上是3個套環，所以人腦可輕鬆推算而得，若有4個、5個或6個套環時，則此問題的解又如何呢？所幸，這個問題可用遞迴求解如下： 1. 當n = 1時，只要將套環1由A柱搬到B柱。 2. 當n > 1時，則要將此問題分解如下： （1）將A柱上面的n–1個套環透過B的協助由A搬到C。 （2）將A柱最下面的第n個套環由A搬到B，且此套環已達定點。 （3）將C柱上面的n–1個套環透過A柱的協助，由C柱搬到B柱。

若將以上演算法，以Java描述，則其程式如下，為了提高程式的可讀性，我們將A、B及C柱，分別以sourceTower、goalTower及auxTower命名。 static void moveRings(int n,char sourceTower,char goalTower ,char auxTower) { if (n==1) s=s+"Ring " + n + " 由 " + sourceTower +" 搬到 " +goalTower+"\n\r"; else moveRings(n-1,sourceTower,auxTower,goalTower); moveRings(n-1,auxTower,goalTower,sourceTower); }

範例8-6a 求解漢諾塔。

迷宮問題 老鼠走迷宮是實驗心理學家常做的一項實驗，在這實驗中老鼠被置於一個無頂大盒子的入口處，盒子中利用牆將大部份移動去向阻隔，這樣科學家們就可以仔細觀察老鼠在迷宮中如何移動，直到最後抵達另一端出口為止。從出口到入口只有一條路徑，而在最後出口處有一塊香甜的乳酪在等著。在這實驗中每當老鼠走錯路徑時就得重頭來，一直到它能正確無誤地一次走到出口為止，而這個實驗的次數也就代表老鼠學習的曲線。 我們可以寫一個程式來作走迷宮的實驗，第一次走的時候電腦的表現不見得比老鼠高明，它也可能要經過多次的試驗才能找到正確的路。但電腦有一點比老鼠強，就是它能將正確的路線記住，所以第二次走的時候就不會再犯同樣的錯誤。因此，重新再執行一次程式，也就變得沒有意義了。讀者不妨先試著自行撰寫這個程式，而不要急著去看我們所提供的解答。將折返的次數及修正的情形記錄下來；這樣，當我們在本書中再進行這個實驗時，你可以瞭解一下自己的學習曲線。

現在我們以一個二維陣列，maze [1..m，1..p]代表迷宮，其中1代表不能通行。0代表可以通過。迷宮的入口為maze [1，1]。出口為maze [m，p]，如下圖   由於迷宮是以二維陣列表示，因此老鼠所在的位置可以以列數i和行數j表示。現在考慮老鼠在[i，j]點可能移動的情形。下圖顯示出在任何點[i，j]所有可能移動的情形，我們將這點用X表示。如果X點的周圍都是0的話，老鼠可以在這4條路中任選一條作為下次移動的方向。我們稱4個方向為西、南、東、北；用代號表示則分別為W、S、E、N。 以上4個方向，我們可以以一個二維陣列move儲存老鼠所有可能的方向，如右圖所示，所以陣列move的宣告如下： int move[][]={{0,1},{1,0},{0,1},{-1,0}}; 如果我們位於迷宮的[i，j]位置，同時想找在我們南方的位置[g，h]，dire = 2，那麼我們就設： g=i+move(2,1);h=j+move(2,2);

舉例來說，如果我們位於（3，4），則（3 + (1) = 4，4 + (0) = 4）是我們的南方。 我們必須注意，並非每個位置都有4個相鄰點可以移動，若[i，j]是在邊緣上，即i = 1或m，j = 1或p，則只有三個相鄰點，而不是4個。為了避免要檢查這種邊緣的狀況，可以假設迷宮最外圍包著一層值為1的邊線；因此這個二維陣列要宣稱為maze [0..m + 1，0..p + 1]。 當我們在迷宮想移動時，有好幾個方向都可以移動，但由於不知道那一個方向才是正確，我們只好選一個試試，但是必須將此時所在位置及選擇之方向記錄在一串列上；這樣假如所選的方向錯了，我們才能回到原先位置再試其他方向。每一個位置都需要測試各種方向是否可行，測試時是從西開始，然後依順時鐘方向進行。最後為了防止同一路徑走了兩次，我們用另外一個二維陣列mark [0:m + 1，0:p + 1]，這個陣列的起始值均設為0，而當走到某一點[i，j]時，mark [i，j]就改為1。我們又設maze[m，p] = 0，如果不是這樣的話就沒有路通到出口。以下為迷宮的演繹邏輯。 1.只要堆疊不是空的表示還有路可以走。 while (t != 0) 2.每一個位置均有4個方向，每個方向皆要嘗試走走看。 while (dire <= 4)

3. 計算下一步的座標。 g = i + move[dire][1] ; h = j + move[dire][2] ; 4. 假如(g, h)為終點座標(m, p)，則探索成功。此時堆疊的內容即為老鼠每一步的路徑，印出此路徑即為所求。 if (g == m & h == p) { mark[i][j] = 1 ; mark[g][h] = 1 ; System.out.println("走過路徑: "); System.out.println("(1代表走過路徑)"); PrintMark() ; return ; }

6. 假如4個方向都已試過，如全無路徑，則應自堆疊取一個位置，重新嘗試可能的路徑。 pop() ; 5. 假如(g, h)為通路，且(g, h)還未走過，則將此點作記號、將目前座標放入堆疊、踏入這一點，且設dire = 1，否則繼續嘗試下一個方向。 if (maze[g][h] == 0 & mark[g][h] == 0) { push(i,j,dire) ; i = g ; j = h ; dire = 1; } else dire ++ ; 6. 假如4個方向都已試過，如全無路徑，則應自堆疊取一個位置，重新嘗試可能的路徑。 pop() ;

範例8-6b 示範老鼠走迷宮，並印出老鼠所走的路徑。

快速排序法 本書於第七章已探討兩種常用的排序方法，分別是泡沫與計數排序法，本單元將要介紹另一種使用遞迴的排序法，其名稱為快速排序法，它的執行效率可說是所有排序法中表現最為優異的。假設有一序列其首末編號分別是m、n，且已放入a陣列，則其演算法如下：

static void QSort(int m,int n) 1.宣告快速排序方法 static void QSort(int m,int n) 2.每個序列只要其長度大於2，均要以以下方式將序列的第一個元素放至整個序列的定點，且將此序列一分為二。 if (m < n ) i=m; j =n+1 ; (1)從序列的第m個元素往後找，直到有一元素大於等於此序列的第m個元素，設此元素的編號為i。 do i++ ; while(a[i] <a[m] );

從序列的第n+1個元素往前找，直到有一元素小於等於此序列的第m個元素，設此元素的編號為j。 do j-- ; while( a[j] > a[m] ); 假如i < j則將編號為i, j的元素交換，且重複步驟（1）與（2）。 if (i < j){ t = a[i] ; a[i] = a[j] ; a[j]=t ; } 將編號為m，j的元素交換，此時，此序列已一分為二，前半段的所有元素都小於等於a [j]，後半段的元素都大於等於a [j]。 t = a[j] ; a[j] = a[m] ; a[m]=t ; 3. 前半段繼續呼叫快速排序法。 QSort(m,j-1) ; 4. 後半段繼續呼叫快速排序法。 QSort(j+1,n) ;

2. 將序列的第一個元素放至整個序列的正確位置，且將整個序列一分為二。 例如，有一序列如下： 7 2 9 3 8 則此序列的排序過程如下： 1. m = 1, n = 5呼叫QSort(1,5) 2. 將序列的第一個元素放至整個序列的正確位置，且將整個序列一分為二。 （1）得到i = 3，a[3]=9；得到j = 4，a[4]=3； （2）因為i < j成立，交換a[3]與a[4]a[3]=3，a[4]=9， （3）所以序列演變如下： 7 2 3 9 8 （4）因為i < j成立，重複以上步驟 得到i = 4，a[4]=9； 得到j = 3，a[3]=3； i < j不成立 （5）交換 a[m]與a[j]（m=1，j=3），所以序列演變如下，7已達定點。 3 2 7 9 8 3. 前半段繼續呼叫QSort。 QSort(1,2); 4. 後半段繼續呼叫QSort。 Qsort(4,5);

範例8-6c 示範以上快速排序法。