函數的進階應用 10 戰勢不過奇正，奇正之變，不可勝窮也。 奇正相生，如循環之無端，孰能窮之哉！ 《孫子兵法﹒勢篇》

Presentation on theme: "函數的進階應用 10 戰勢不過奇正，奇正之變，不可勝窮也。 奇正相生，如循環之無端，孰能窮之哉！ 《孫子兵法﹒勢篇》"— Presentation transcript:

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

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

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

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

5 //------- 主程式 ---------------------------------
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; }

6 // --- 函數的定義 -------------------------- 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

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

8 範例程式 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; }

9 預設引數函數的呼叫 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'); // 錯誤!

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

11 樣版函數(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) { 　　 // … 函數內容 }

12 樣版函數可以用來取代函數的重載 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;}

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

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

15 範例程式 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;

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

17 //------- 定義函數 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;

18 // (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;

19 程式執行結果 RAND_MAX (0x7FFFU) 的值是：32767
LRAND_MAX (0x7FFFFFFFU) 的值是： 連擲20次的結果： 點數 次數

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

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

22 #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; }

23 //------- 定義函數 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;

24 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;

25 程式執行結果 連試20次Rand()： 範圍 次數 < Rand() <= < Rand() <= < Rand() <= < Rand() <= < Rand() <= < Rand() <= < Rand() <= < Rand() <= < Rand() <= < Rand() <= 平均：

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

27 範例程式 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; }

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

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

30 範例程式 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; }

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

32 泡沫排序法 假設資料的名稱叫做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] 的值

33 範例程式 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;

34 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; }

35 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;

36 程式執行結果 執行Bubble() 之前, Data的值是： 1.9149 -2.1917 -3.7524 0.3801 -2.1551
執行Bubble() 之後, Data的值是：

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

38 範例程式 檔案 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; }

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

40 // ---- 主程式 --------------------------------------
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;

41 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;

42 程式執行結果 (第一次執行結果) Data的值是： 74 72 82 16 29 35 7 9 20 43 46 10 27 65 7
找不到 32 (第二次執行結果) 32在第18個元素的地方

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

44 當 (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;

45 範例程式 檔案 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; }

46 // ---- 主程式 -------------------------------------
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; }

47 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;