函數(shù)的進階應(yīng)用.ppt

1、1/47,函數(shù)的進階應(yīng)用,戰(zhàn)勢不過奇正，奇正之變，不可勝窮也。 奇正相生，如循環(huán)之無端，孰能窮之哉！ 孫子兵法勢篇 介紹函數(shù)的重載、參數(shù)的預設(shè)值、樣版函數(shù)，等等讓 C+ 的函數(shù)在使用上更方便的語法。此外，也討論了幾個非常實用的問題，包括如何取得亂數(shù)、遞迴函數(shù)的設(shè)計以及排序與搜尋的相關(guān)演算法。,10,2/47,Chap 10 函數(shù)的進階應(yīng)用,10.1函數(shù)的重載 10.2參數(shù)的預設(shè)值 10.3樣版函數(shù) 10.4亂數(shù)的取得 10.5遞迴函數(shù) 10.6排序與搜尋,3/47,函數(shù)的重載,int Max(int, int); double Max(double, double); / 參數(shù)的資料型態(tài)不同

2、double Area(double x); double Area(double x, double y); / 參數(shù)的數(shù)目不一樣,4/47,範例程式 Overload.cpp: 函數(shù)的重載,5/47,6/47,7/47,預設(shè)引數(shù) (default arguments),函數(shù)原型： double Area(double Width, double Length = 12.0); 函數(shù)定義(兩個參數(shù)的乘積)： double Area(double Width, double Length) return Width*Length; A = Area(6.5); / 只用一個引數(shù)呼叫,8/47,

3、範例程式 Default.cpp: 預設(shè)引數(shù),9/47,預設(shè)引數(shù)函數(shù)的呼叫,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/47,具有預設(shè)參數(shù)的重載函數(shù),兩個具有預設(shè)參數(shù)的重載函數(shù)Func()之原型： int Func(int n, int m = 0, float x = 1.0); int Func(int n, int m); 這兩

4、個函數(shù)無法以下列呼叫敘述正確區(qū)分： M = Func(2,3); / 錯誤!,11/47,樣版函數(shù)(Function Template),template T Sum(T x, T y)return x+y; 相當於同時宣告了許多名稱都叫做Sum() 的函數(shù)，但其輸入和輸出的資料型態(tài)未定。 樣版函數(shù)內(nèi)可以使用不只一種暫定的資料型態(tài)： template T1 Func(T1 x,T2 y, T3 z) / 函數(shù)內(nèi)容 ,12/47,樣版函數(shù)可以用來取代函數(shù)的重載,template T Abs(T x) return (x0)? x ： -x; 相當於同時定義了三個函數(shù): int Abs (int

5、x) return (x0)? x ： -x; float Abs (float x) return (x0)? x ： -x; double Abs (double x) return (x0)? x ： -x;,13/47,準亂數(shù)產(chǎn)生器(pseudo-random number generator),要得到準亂數(shù)可以呼叫函數(shù)rand()： rand() ：可以產(chǎn)生0到RAND_MAX的整數(shù)。 RAND_MAX定義在 裏面，RAND_MAX的值通常為 0 x7FFFU (32767)。 srand() 用來給予這個準亂數(shù)產(chǎn)生器一個臨時的初始值 (稱為種子，seed)。 srand(int(t

6、ime(0);,14/47,產(chǎn)生指定範圍內(nèi)的整數(shù)亂數(shù),獲得一個介於0到N-1之間的整數(shù)亂數(shù)： rand()%N 我們可以包裝成inline 函數(shù)以方便使用： inline int RandI(int N) return 1 + rand()%N;,15/47,範例程式 TestDice.cpp,以inline 函數(shù) RandI() 為基礎(chǔ)，寫成一個函數(shù)TestDice() 以模擬擲骰子的 現(xiàn)象 (骰子的值為整數(shù)16)。 / TestDice.cpp #include #include #include using namespace std; inline int RandI(int N) /

7、 定義 inline 函數(shù) RandI() return rand()%N+1; void TestDice(); / 宣告函數(shù) TestDice() const int TestNum = 6000;,16/47,/- 主程式 - int main() cout right fixed showpoint setprecision(4); cout RAND_MAX (0 x7FFFU) 的值是 : setw(7) RAND_MAX endl; TestDice(); return 0; ,17/47,/- 定義函數(shù) TestDice() - void TestDice() int Freq

8、6, Face, i; for (i=0; i6; i+) Freqi=0; / (1) 初始化 srand(int(time(0); / (2) 連擲 20 次 cout 連擲 20 次的結(jié)果: endl; for (i=1; i=20; i+) cout setw(5) RandI(6); if (i%5 = 0) cout endl; cout endl;,18/47,/ (3) 統(tǒng)計連擲 TestNum 次的結(jié)果 for (int Roll=0; Roll TestNum; Roll+) Face = RandI(6); FreqFace-1+; cout 點數(shù) 次數(shù) endl; co

9、ut - endl; for (i=0; i6; i+) cout setw(5) (i+1) setw(10) Freqi endl; cout - endl; ,19/47,程式執(zhí)行結(jié)果,20/47,隨機獲得一個介於0到1之間的浮點數(shù),inline double Rand() return double(rand()/RAND_MAX;,21/47,範例程式檔案 TestRand.cpp,藉由程式模擬連續(xù)隨機產(chǎn)生20個浮點數(shù)的過程。接著，統(tǒng)計連連續(xù)產(chǎn)生6000次的結(jié)果，以查看各個範圍內(nèi)出現(xiàn)的次數(shù)是否均勻(每個範圍間隔0.1)。最後，將6000次的結(jié)果平均 (理想值為中間值0.5)，以驗證準

10、亂數(shù)產(chǎn)生器的性能。,22/47,#include #include #include using namespace std; / 定義 inline 函數(shù) Rand() 產(chǎn)生 0 1 之間的亂數(shù) inline double Rand()return double(rand()/RAND_MAX; /- 宣告函數(shù) TestRand() - void TestRand(); const int TestNum = 6000; /- 主程式 - int main() cout right fixed showpoint setprecision(4); TestRand(); return 0;

11、,23/47,/- 定義函數(shù) TestRand() - void TestRand() int Freq10; double Sum, Temp; / (1) 初始化 srand(int(time(0); / 也可寫成 randomize(); for (int i=0; i10; i+) Freqi=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) 統(tǒng)計連試 TestN

12、um 次的結(jié)果 Sum = 0.0;,24/47,for (int Roll=0; Roll(i-1)*0.1) Freqi-1+; Sum += Temp; cout 範圍 次數(shù) endl; cout - endl; for (int i=1; i=10; i+) cout (i-1)*0.1) Rand() = (i*0.1) setw(6) Freqi-1 endl; cout - endl; cout 平均: Sum/double(TestNum) endl; return; ,25/47,程式執(zhí)行結(jié)果,26/47,遞迴函數(shù): 階乘(factorial),n的階乘，寫成 n !，的定義

13、式為,27/47,範例程式 Factorial.cpp: 遞迴函數(shù)Factorial(),/ Factorial.cpp #include using namespace std; / - 宣告遞迴函數(shù) Factorial() - int Factorial(int); / - 主程式 - int main() int N; cout N; if ( N 0 ) cout 錯誤! 您輸入了負數(shù). endl; else cout N ! = Factorial( N ) endl; return 0; ,28/47,/ - 定義遞迴函數(shù) Factorial() - int Factorial(i

14、nt N) if ( N = 1 ) return 1; else return N * Factorial(N-1); / 呼叫自己! 程式執(zhí)行結(jié)果,29/47,最大公約數(shù) (Greatest Common Divider，簡寫為GCD),正整數(shù)M和N的最大公約數(shù)，寫成GCD(M,N)，的定義式為 可以使用C+寫成遞迴函數(shù)GCD()，列於檔案GCD.cpp中。,30/47,範例程式 GCD.cpp,/ GCD.cpp #include using namespace std; / - 宣告函數(shù) GCD() - int GCD(int, int); / - 主程式 - int main() i

15、nt Num1, Num2; cout Num1; cout Num2; cout Num1 和 Num2 的最大公約數(shù)是 GCD(Num1, Num2); return 0; ,31/47,/ - 定義函數(shù) GCD() - int GCD(int M, int N ) if ( (M%N) = 0 ) return N; else return GCD(N, M%N); ,32/47,泡沫排序法,假設(shè)資料的名稱叫做Data，而且資料的數(shù)量是Size，則泡沫排序法 的虛擬程式碼 (pseudocode)： for (int i = 0; i i; j-) if (Dataj Dataj-1)

16、交換 Vj 和Vj-1 的值,33/47,範例程式 Bubble.cpp,34/47,35/47,36/47,程式執(zhí)行結(jié)果,37/47,線性搜尋法,假設(shè)資料的名稱叫做 Data，而且資料的數(shù)量是 Size，比對的標準為 key，則線性搜尋法的虛擬程式碼為： for (int i = 0; i Size; i+) if (Datai = Key) 傳回 i; 傳回 -1;,38/47,範例程式檔案 LinearSearch.cpp,/ LinearSearch.cpp #include #include #include using namespace std; / - 定義樣版函數(shù) LinSe

17、arch() - template int LinSearch(T *V, int N , T Key) for (int i=0; iN; i+) if (Vi = Key) return i; return -1; ,39/47,/ - 定義 inline 函數(shù) RandI() 產(chǎn)生 1N 之間的亂數(shù) - inline int RandI(int N) return rand()%N+1;,40/47,/ - 主程式 - int main() int Index; int Key = 32; srand(int(time(0); const int Size = 20; int DataS

18、ize; for (int i=0; i20; i+) Datai= RandI(85); / 隨機產(chǎn)生 Datai cout nData 的值是: endl;,41/47,for (int i=0; i -1) cout Key 在第 Index+1 個元素的地方. endl; else cout 找不到 Key endl; return 0; ,42/47,程式執(zhí)行結(jié)果,43/47,二分搜尋法 (binary search),如果資料本身已經(jīng)按照大小排序，就可以用二分搜尋法 以提高搜尋的效率。 假設(shè)資料的名稱叫做Data，而且資料的數(shù)量是Size，比對的標準為key，中間元素的下標叫做Mid，元素值較小的那一邊的下標範圍從Left到Mid-1，元素值較丈的那一邊的下標範圍從Mid+1到Right，則二分搜尋法的虛