函數的進階應用 10 戰勢不過奇正，奇正之變，不可勝窮也。 奇正相生，如循環之無端，孰能窮之哉！ 《孫子兵法﹒勢篇》 戰勢不過奇正，奇正之變，不可勝窮也。 奇正相生，如循環之無端，孰能窮之哉！ 《孫子兵法﹒勢篇》 介紹函數的重載、參數的預設值、樣版函數，等等讓 C++ 的函數在使用上更方便的語法。此外，也討論了幾個非常實用的問題，包括如何取得亂數、遞迴函數的設計以及排序與搜尋的相關演算法。

Chap 10 函數的進階應用 10.1 函數的重載 10.2 參數的預設值 10.3 樣版函數 10.4 亂數的取得 10.5 遞迴函數 10.1　函數的重載 10.2　參數的預設值 10.3　樣版函數 10.4　亂數的取得 10.5　遞迴函數 10.6　排序與搜尋

函數的重載 int Max(int, int); double Max(double, double); // 參數的資料型態不同 double Area(double x); double Area(double x, double y); // 參數的數目不一樣

範例程式 Overload.cpp: 函數的重載 #include <iostream> using namespace std; // 函數的原型 double Max(double, double); double Max(double, double, double);// 參數的數目不一樣

//------- 主程式 --------------------------------- int main() { double a=5.0, b=6.0, c=7.0; cout << "Max(a, b) 的值是： " << Max(a, b) << endl; cout << "Max(a, b, c) 的值是： " << Max(a, b, c) << endl; return 0; }

// --- 函數的定義 -------------------------- double Max(double x, double y) { return (x>=y) ? x ： y;} double Max(double x, double y, double z) { double Temp = x; if (x<y) Temp = y; if (Temp<z) Temp = z; return Temp; } 程式執行結果 Max(a, b) 的值是： 6 Max(a, b, c) 的值是： 7

預設引數 (default arguments) 函數原型： double Area(double Width, double Length = 12.0); 函數定義(兩個參數的乘積)： double Area(double Width, double Length) { return Width*Length; } A = Area(6.5); // 只用一個引數呼叫

範例程式 Default.cpp: 預設引數 // Default.cpp #include <iostream> using namespace std; // --- 宣告函數Area() -------------------- double Area(double Width, double Length = 12.0); // --- 主程式 ---------------------------- int main() { double A; A = Area(6.5); // 只用一個參數呼叫 return 0; } // --- 定義函數Area() -------------------- double Area(double Width, double Length) { return Width*Length; }

預設引數函數的呼叫 void Fune (float, float x = 0,int n = 5,char = "r"); 下面的呼叫都是正確的： Func(1.5); Func(3.2, 1.0); Func(0.0, 1.0, 10, 'a'); 不可以有下列的呼叫方式： Func(1.0, 2.0, 'a'); // 錯誤!

具有預設參數的重載函數 兩個具有預設參數的重載函數Func()之原型： int Func(int n, int m = 0, float x = 1.0); int Func(int n, int m); 這兩個函數無法以下列呼叫敘述正確區分： M = Func(2,3); 　　 // 錯誤!

樣版函數(Function Template) template <class T> T Sum(T x, T y)　{return x+y;} 相當於同時宣告了許多名稱都叫做Sum() 的函數，但其輸入和輸出的資料型態未定。 樣版函數內可以使用不只一種暫定的資料型態： template <class T1, class T2, class T3> T1 Func(T1 x,T2 y, T3 z) { 　　 // … 函數內容 }

樣版函數可以用來取代函數的重載 template<class T> T Abs(T x) {return (x>0)? x ： -x;} 相當於同時定義了三個函數: int Abs (int x) {return (x>0)? x ： -x;} float Abs (float x) {return (x>0)? x ： -x;} double Abs (double x) {return (x>0)? x ： -x;}

準亂數產生器(pseudo-random number generator) rand() ：可以產生0到RAND_MAX的整數。 RAND_MAX定義在 <cstdlib> 裏面，RAND_MAX的值通常為 0x7FFFU (32767)。 srand() 用來給予這個準亂數產生器一個臨時的初始值 (稱為種子，seed)。 srand(int(time(0)));

產生指定範圍內的整數亂數 獲得一個介於0到N-1之間的整數亂數： rand()%N 我們可以包裝成inline 函數以方便使用： inline int RandI(int N) {return 1 + rand()%N;}

範例程式 TestDice.cpp // TestDice.cpp #include <iostream> 以inline 函數 RandI() 為基礎，寫成一個函數TestDice() 以模擬擲骰子的 現象 (骰子的值為整數1~6)。 // TestDice.cpp #include <iostream> #include <iomanip> #include <ctime> using namespace std; inline int RandI(int N) // 定義 inline 函數 RandI() { return rand()%N+1; } void TestDice(); // 宣告函數 TestDice() const int TestNum = 6000;

//------- 主程式 ---------------------- int main() { cout << right << fixed << showpoint << setprecision(4); cout << "RAND_MAX (0x7FFFU) 的值是 :" << setw(7) << RAND_MAX << endl; TestDice(); return 0; }

//------- 定義函數 TestDice() --------- void TestDice() { int Freq[6], Face, i; for (i=0; i<6; i++) Freq[i]=0; // (1) 初始化 srand(int(time(0))); // (2) 連擲 20 次 cout << "連擲 20 次的結果: " << endl; for (i=1; i<=20; i++) cout << setw(5) << RandI(6); if (i%5 == 0) cout << endl; } cout << endl;

// (3) 統計連擲 TestNum 次的結果 for (int Roll=0; Roll< TestNum; Roll++) { Face = RandI(6); Freq[Face-1]++; } cout << " 點數 次數 " << endl; cout << "------------------ " << endl; for (i=0; i<6; i++) cout << setw(5) << (i+1) << setw(10) << Freq[i] << endl; cout << "------------------ " << endl;

程式執行結果 RAND_MAX (0x7FFFU) 的值是：32767 LRAND_MAX (0x7FFFFFFFU) 的值是：2147483647 連擲20次的結果： 1 1 4 3 4 2 6 2 5 1 4 6 1 4 5 2 2 3 1 4 點數 次數 ------------------ 1 1002 2 1027 3 1005 4 980 5 972 6 1014

隨機獲得一個介於0到1之間的浮點數 inline double Rand() {return double(rand())/RAND_MAX;}

範例程式　檔案 TestRand.cpp 藉由程式模擬連續隨機產生20個浮點數的過程。接著，統計連連續產生6000次的結果，以查看各個範圍內出現的次數是否均勻(每個範圍間隔0.1)。最後，將6000次的結果平均 (理想值為中間值0.5)，以驗證準亂數產生器的性能。

#include <iostream> #include <iomanip> #include <stdlib> using namespace std; // 定義 inline 函數 Rand() 產生 0 ~ 1 之間的亂數 inline double Rand()　{return double(rand())/RAND_MAX;} //------- 宣告函數 TestRand() --------- void TestRand(); const int TestNum = 6000; //------- 主程式 ---------------------- int main() { cout << right << fixed << showpoint　<< setprecision(4); TestRand(); return 0; }

//------- 定義函數 TestRand() --------- void TestRand() { int Freq[10]; double Sum, Temp; // (1) 初始化 srand(int(time(0))); // 也可寫成 randomize(); for (int i=0; i<10; i++) Freq[i]=0; // (2) 連試 20 次 Rand() cout << "連試 20 次 Rand(): " << endl; for (int i=1; i<=20; i++) cout << setw(10) << Rand(); if (i%5 == 0) cout << endl; } cout << endl; // (3) 統計連試 TestNum 次的結果 Sum = 0.0;

for (int Roll=0; Roll< TestNum; Roll++) { Temp = Rand(); for (int i=1; i<=10; i++) if ((Temp<=i*0.1) && (Temp>(i-1)*0.1)) Freq[i-1]++; Sum += Temp; } cout << " 範圍 次數 " << endl; cout << "--------------------------------- " << endl; cout << ((i-1)*0.1) << " < Rand() <= " << (i*0.1) << setw(6) << Freq[i-1] << endl; cout << "平均: " << Sum/double(TestNum) << endl; return;

程式執行結果 連試20次Rand()： 0.1886 0.3008 0.6612 0.6320 0.0216 0.1375 0.7226 0.3215 0.0080 0.6875 0.7928 0.5995 0.7400 0.4369 0.8018 0.9930 0.6493 0.0373 0.8551 0.6647 範圍 次數 --------------------------------- 0.0000 < Rand() <= 0.1000 605 0.1000 < Rand() <= 0.2000 601 0.2000 < Rand() <= 0.3000 560 0.3000 < Rand() <= 0.4000 600 0.4000 < Rand() <= 0.5000 602 0.5000 < Rand() <= 0.6000 648 0.6000 < Rand() <= 0.7000 550 0.7000 < Rand() <= 0.8000 643 0.8000 < Rand() <= 0.9000 608 0.9000 < Rand() <= 1.0000 583 平均： 0.5014

遞迴函數: 階乘(factorial) n的階乘，寫成 n !，的定義式為

範例程式 Factorial.cpp: 遞迴函數Factorial() #include <iostream> using namespace std; // --- 宣告遞迴函數 Factorial() -------------------- int Factorial(int); // ---- 主程式 ------------------------------------- int main() { int N; cout << "請輸入一個 12 以下的正整數: "; cin >> N; if ( N < 0 ) cout << "錯誤! 您輸入了負數." << endl; else cout << N << " ! = " << Factorial( N ) << endl; return 0; }

// --- 定義遞迴函數 Factorial() ---------------------- int Factorial(int N) { if ( N <= 1 ) return 1; else return N * Factorial(N-1); // 呼叫自己! } 程式執行結果 請輸入一個 12 以下的正整數： 10 10 ! = 3628800

最大公約數 (Greatest Common Divider，簡寫為GCD) 正整數M和N的最大公約數，寫成GCD(M,N)，的定義式為 可以使用C++寫成遞迴函數GCD()，列於檔案GCD.cpp中。

範例程式 GCD.cpp // GCD.cpp #include <iostream> using namespace std; int GCD(int, int); // ---- 主程式 ---------------------------------- int main() { int Num1, Num2; cout << "請輸入第一個正整數 (共兩個): " << endl; cin >> Num1; cout << "請輸入第二個正整數 (共兩個): " << endl;; cin >> Num2; cout << Num1 << " 和 " << Num2 << " 的最大公約數是 " << GCD(Num1, Num2); return 0; }

// --- 定義函數 GCD() -------------------------- int GCD(int M, int N ) { if ( (M%N) == 0 ) return N; else return GCD(N, M%N); }

泡沫排序法 假設資料的名稱叫做Data，而且資料的數量是Size，則泡沫排序法 的虛擬程式碼 (pseudocode)： for (int i = 0; i < Size; i++) for (int j = Size; j > i; j--) if (Data[j] < Data[j-1]) 交換 V[j] 和V[j-1] 的值

範例程式 Bubble.cpp // Bubble.cpp #include <iostream> #include <iomanip> using namespace std; // --- 定義樣版函數 Exchange() ---------------------- template <class T> void Exchange(T& A, T& B) { T Temp; Temp = A; A=B; B=Temp; } template <class T> // --- 定義樣版函數 Bubble() void Bubble(T *V, int N ) for (int i=0; i<N; i++) for (int j=N-1; j>i; j--) if (V[j]<V[j-1]) Exchange(V[j],V[j-1]); return;

inline double Rand() // 定義 inline 函數 Rand() {return double(rand())/RAND_MAX;} // ---- 主程式 ------------------------------------- int main() { srand(int(time(0)));; const int Size = 20; double Data[Size]; for (int i=0; i<20; i++) Data[i]= 10.0*Rand()-5.0; // 隨機產生 Data[i] cout << setiosflags(ios::right) << setiosflags(ios::fixed) << setiosflags(ios::showpoint)<< setprecision(4); cout << "\n執行 Bubble() 之前, Data 的值是:\n"; for (int i=0; i<Size; i++) cout << setw(10) << Data[i]; if (i%5 == 4) cout << endl; }

Bubble(Data, Size); cout << "\n執行 Bubble() 之後, Data 的值是:\n" for (int i=0; i<Size; i++) { cout << setw(10) << Data[i]; if (i%5 == 4) cout << endl; } return 0;

程式執行結果 執行Bubble() 之前, Data的值是： 1.9149 -2.1917 -3.7524 0.3801 -2.1551 1.9149 -2.1917 -3.7524 0.3801 -2.1551 -2.6949 4.9835 -2.7267 -0.1643 4.3005 0.2831 1.3082 2.4410 -4.0802 4.0301 1.3158 0.8391 -2.1691 -1.3640 -3.8464 執行Bubble() 之後, Data的值是： -4.0802 -3.8464 -3.7524 -2.7267 -2.6949 -2.1917 -2.1691 -2.1551 -1.3640 -0.1643 0.0000 0.2831 0.3801 0.8391 1.3082 1.3158 1.9149 2.4410 4.0301 4.3005

線性搜尋法 假設資料的名稱叫做 Data，而且資料的數量是 Size，比對的標準為 key，則線性搜尋法的虛擬程式碼為： for (int i = 0; i < Size; i++) if (Data[i] == Key) 傳回 i; 傳回 -1;

範例程式 檔案 LinearSearch.cpp #include <iostream> #include <iomanip> #include <stdlib> using namespace std; // --- 定義樣版函數 LinSearch() ----------------------- template <class T> int LinSearch(T *V, int N , T Key) { for (int i=0; i<N; i++) { if (V[i] == Key) return i; } return -1; }

// -- 定義 inline 函數 RandI() 產生 1~N 之間的亂數 ------ inline int RandI(int N) {return rand()%N+1;}

// ---- 主程式 -------------------------------------- int main() { int Index; int Key = 32; srand(int(time(0))); const int Size = 20; int Data[Size]; for (int i=0; i<20; i++) Data[i]= RandI(85); // 隨機產生 Data[i] cout << "\nData 的值是:" << endl;

for (int i=0; i<Size; i++) { cout << setw(10) << Data[i]; if (i%5 == 4) cout << endl; } Index = LinSearch(Data, Size, Key); if (Index > -1) cout << Key << " 在第 " << Index+1 << " 個元素的地方." << endl; else cout << "找不到 " << Key << endl; return 0;

程式執行結果 (第一次執行結果) Data的值是： 74 72 82 16 29 35 7 9 20 43 46 10 27 65 7 74 72 82 16 29 35 7 9 20 43 46 10 27 65 7 47 49 18 58 50 找不到 32 (第二次執行結果) 52 31 27 30 73 83 5 33 33 67 58 17 61 39 84 67 80 32 79 52 32在第18個元素的地方

二分搜尋法 (binary search) 如果資料本身已經按照大小排序，就可以用二分搜尋法 以提高搜尋的效率。 假設資料的名稱叫做Data，而且資料的數量是Size，比對的標準為key，中間元素的下標叫做Mid，元素值較小的那一邊的下標範圍從Left到Mid-1，元素值較丈的那一邊的下標範圍從Mid+1到Right，則二分搜尋法的虛擬程式碼為： int Left =0, Right, Mid; Right = N-1;

當 (Left <= Right) 時執行下列敘述 { Mid = (int) ((Left+Right)/2); if (Key == Data[Mid]) 傳回 Mid; else if (Key > Data[Mid]) Left = Mid +1; else Right = Mid -1; } 傳回 -1;

範例程式 檔案 BinarySearch.cpp // --- 定義樣版函數 Bubble() ----------------------- template <class T> void Bubble(T *V, int N ) { for (int i=0; i<N; i++) for (int j=N; j>i; j--) if (V[j]<V[j-1]) Exchange(V[j],V[j-1]); return; }

// ---- 主程式 ------------------------------------- int main() { int Index, Key = 32; srand(int(time(0))); const int Size = 20; int Data[Size]; for (int i=0; i<20; i++) Data[i]= RandI(85); // 隨機產生 Data[i] cout << "\nData 原來的值是:\n"; for (int i=0; i<Size; i++) { cout << setw(10) << Data[i]; if (i%5 == 4) cout << endl; }

Bubble(Data, Size); cout << "\n執行 Bubble() 之後, Data 的值是:\n"; for (int i=0; i<Size; i++) { cout << setw(10) << Data[i]; if (i%5 == 4) cout << endl; } Index = BiSearch(Data, Size, Key); if (Index > -1) cout << Key << " 在第 " << Index+1 << " 個元素的地方.\n"; else cout << "找不到 " << Key << endl; return 0;