最新-C--課件9-PPT

1、第六章 函數(shù)、遞推與遞歸函數(shù)的概念、定義、調(diào)用和返回帶自定義函數(shù)的程序設(shè)計遞推算法遞歸思想及算法實現(xiàn)內(nèi) 容 要 點 為什么需要函數(shù)？ 滿足實際應(yīng)用需求6.1 函數(shù) 函數(shù)是組成 C/C+ 程序的基礎(chǔ) C/C+ 庫中已經(jīng)為用戶提供了許多標準庫函數(shù) 用戶可以根據(jù)自己的需要選用合適的庫函數(shù) 如果沒有所需函數(shù)，用戶可自己定義和編寫一些函數(shù)函數(shù)概述函數(shù)是模塊化的基本單位主調(diào)函數(shù)與被調(diào)函數(shù)程序、源文件與函數(shù)關(guān)系程序中各模塊關(guān)系file1.cppmain()fun1()fun2()file2.cppfun3()fun4()fun5()programint main() int a, b, sum; sum =

2、 Add( a, b ); / 函數(shù)調(diào)用 int Add( int x, int y ) ; / 函數(shù)聲明int Add( int x, int y ) / 函數(shù)定義 / 函數(shù)體取代函數(shù)聲明尾部的分號 要使用C+函數(shù)，必須完成如下工作： 提供函數(shù)定義 提供函數(shù)聲明（原型） 調(diào)用函數(shù)函數(shù)定義：有返回值的函數(shù) 沒有返回值的函數(shù)（void函數(shù)）void functionName (parameterList) /沒有返回值 return; / 可選typeName functionName (parameterList) /有返回值 return value;【任務(wù)6.1】素數(shù)判定思路：設(shè)計一個函數(shù)

3、 int checkprime(int a) ， 負責(zé)檢查 a 是否為素數(shù)： 如果是素數(shù)，該函數(shù)返回 1； 否則，該函數(shù)返回 0。#include #include using namespace std;int main( ) int a=0; cout a; if ( checkprime(a) ) / 函數(shù)調(diào)用cout a 是素數(shù) endl; elsecout a 不是素數(shù) endl; return 0;int checkprime( int n); / 函數(shù)聲明int checkprime(int n) / 函數(shù)定義，n為形式參數(shù) int k=0; for (k = 2; k = sq

4、rt(n); k = k+1) if (n % k = 0) / 如果 n 能被k整除則返回0 return 0; return 1; / n 不能被k整除則返回1有何問題？函數(shù)原型 int checkprime(int n);提高算法效率只要在 1 和 n 之間存在一個因子就可終止，并返回 n 不是素數(shù)若 n 可被 2 整除，不需檢驗其它數(shù)，程序終止并返回 n 不是素數(shù)；若否，則所有偶數(shù)都不是因子，程序只需檢驗奇數(shù)程序不必檢驗因子一直到 n，只需到sqrt(n)即可int checkprime( int n ) int i; if( n % 2 = 0 ) return 0; for( i

5、= 3; i = sqrt(n); i += 2 ) if( n % i = 0 ) return 0; return 1;問題1：本算法效率？每次迭代都需要計算平方根，很費時問題2：本算法正確性？n=1 n=2 時結(jié)果錯誤int checkprime( int n ) int limit, i; limit = sqrt(n); if( n % 2 = 0 ) return 0; for( i = 3; i = limit; i += 2 ) if( n % i = 0 ) return 0; return 1;問題：本算法正確性？ 浮點數(shù)的存儲有誤差，程序的正確性依賴于機器的表示精度int

6、 checkprime( int n ) int limit, i; limit = sqrt(n) + 1; if( n % 2 = 0 ) return 0; for( i = 3; i = limit; i += 2 ) if( n % i = 0 ) return 0; return 1;if( n y ) t = 1; else t = -1; return t;函數(shù)定義示例： Compare函數(shù); 多條 return 語句int Compare( int x, int y ) if( x = y ) return 0; else if( x y ) return 1; else r

7、eturn -1;編寫函數(shù) Swap，互換兩個整型數(shù)據(jù) x、y 的值void Swap( int x, int y ) int t; t = x; x = y; y = t; return; / 沒有返回值只需直接寫return語句函數(shù)定義示例：Swap 函數(shù)int IsDigit( char c ) if( c = 0 & c = 48 & c = a & c = z ) / az的ASCII值為61H7AH / AZ的ASCII值為41H5AH return c a + A; else return c;函數(shù)定義示例： TransformIntoUpperCase 函數(shù)編寫函數(shù) IsLea

8、pYear，判斷某個給定年份是否為閏年int IsLeapYear( int year ) return year % 4 = 0 & year % 100 != 0 | year % 400 = 0;函數(shù)定義示例： IsLeapYear 函數(shù)int mysqrt(int x) int i=1,sum=0,count=0; while (sum=x) sum+=i; count+; i+=2; return count-1;求整數(shù)的平方根，取其整數(shù)部分思考：參數(shù)的有效性、合法性判斷應(yīng) 放在函數(shù)里? 放在主程序里?int mysqrt(int x) int i=0; while (i*i=x)

9、i+; return i-1;函數(shù)定義示例： 我的平方根函數(shù)int main() int times; char ch; coutch; while (ch!=q) couttimes; n_chars(ch, times); coutThe value of times is timesendl; coutch; cout0) coutc; coutn; double cube(double x);int main() double p,q; p = 1.2; q = cube(p); coutp=pendl; cout實參p的地址是&pendl; coutq=qendl; return 0

10、;double cube(double x) coutx=xendl; cout形參x的地址是&xx; ciny; coutx“ “yendl; (1) Swap( x, y ); coutx“ “yendl; (4) return 0;例：互換兩個整數(shù)void Swap( int x, int y ) int temp; coutx“ “yendl; (2) temp = x; x = y; y = temp; coutx“ “ya; cinb; couta“ “bendl; Swap(); couta“ “bendl; return 0;void Swap() int temp; cout

11、a“ “bendl; temp = a; a = b; b = temp; couta“ “bendl; return;輸出：10 20 10 20 20 1020 10【任務(wù)6.2】給歌手打分 定義int Max( int a,int b)函數(shù)，返回a,b中的大者 定義int Min( int a,int b)函數(shù)，返回a,b中的小者 定義整型變量p，用以保存 N個數(shù)中的最大值 定義整型變量q，用以保存 N個數(shù)中的最小值 定義一個整型變量 sum 做累加用 最終得分： (sum-p-q) / (N-2) # include#includeusing namespace std;int Max

12、( int , int );int Min( int , int );int main( ) int p = 0; int q = 100; int sum = 0，x = 0; int i = 1; for ( i = 1; i=10; i = i+1 ) cout“請第” i “位裁判給分” x ; p = Max( x, p ) ; q = Min( x, q ) ; sum = sum + x ; cout“選手得分”b ) return a ; else return b ; int Min( int c , int d ) if ( c d ) return c ; else re

13、turn d ; #include#includeusing namespace std;void print(int,int); /void print(int*,int);int main() const int n=5; int an; coutEnter matrix a:n; for(int i=0;iai; coutYou have entered the matrix a:n; print(a,n); return 0;void print(int array,int size) /void print(int *array,int size) for(int k=0;k=siz

14、e-1;k+) coutsetw(10)arraykendl; 問題：一維數(shù)組作為參數(shù)void bubble(int,int);int main() int a10; bubble(a,10); return 0;void bubble(int array,int size) for (int j=1;jsize;j+) for (int i=0;isize-j;i+) if (arrayiarrayi+1) int p=arrayi; arrayi=arrayi+1; arrayi+1=p; 冒泡排序：#include#includeusing namespace std;void prin

15、t(int4,int);int main() const int n=5; int an4; coutEnter matrix a:n; for(int i=0;in;i+)for(int j=0;jaij; coutYou have entered the matrix a:n; print(a,n); return 0;void print(int array4,int xsize) for(int i=0;i=xsize-1;i+) for(int j=0;j4;j+) coutsetw(10)arrayij;cout=1; i-) if ( fishi+1%4 != 0 ) break

16、; / 跳出for循環(huán)else fishi=fishi+1*5/4+1; / 計算第i人看到的魚數(shù) while( i=1 ); for (i=1; i=5; i+) cout fishi endl; return 0;int main() int n=100, i=0; int q101; q0=1; for (i=1;i=n;i=i+1) qi=qi-1+i; cout“切100刀后最多可得” qn塊endl; return 0;【任務(wù)6.4】王小二切餅 1 2 4 7 11切0刀 切1刀 切2刀 切3刀 切4刀 遞推公式： q(0) = 1 q(n) = q(n-1) + n5051 遞歸

17、算法在可計算性理論中占有重要地位，它是算法設(shè)計的有力工具，對于拓展編程思路非常有用。6.3 遞歸及其實現(xiàn)遞歸的目的簡化復(fù)雜問題的手段： 將問題逐步化簡（遞簡），在化簡過程中保持原問題的性質(zhì)不變，直到問題最簡，可以輕易地獲得答案；然后將簡化問題的答案組裝成原始問題的解（回歸）遞歸示例n! = 1 2 3 n: n! = (n-1)! n; 1! = 1xn = x x x x: xn = xn-1 x; x0 = 1或結(jié)點和與結(jié)點：ABC條件 Z 條件 !ZABGZ1 Z2 ZnC條件為 Z1 , Z2 , , Zn A 取值為 B 或 C , 或 G或結(jié)點 A 為與結(jié)點，A 的最終取值為C 結(jié)

18、點的值，為了求得 C的值，先求出 B結(jié)點的值，C 是 B 的函數(shù)。ABCABDC與結(jié)點 A 結(jié)點的值最終為 D 的值，為了求 D 需要先求 B 和 C。先求左邊的點才能求最右邊的點。例如：求 n ! 的與或圖直接可解結(jié)點C = 1D = 2*C = 2B = D = 2E = 3*B = 3*2 = 6A = E = 6例如：求 3 ! 的與或圖求 3! 的遞歸調(diào)用與返回 求 3! 的程序框圖1求 3! 的程序框圖2unsigned long fact( unsigned int );int main()int n=0;coutn;coutn的階乘為fact(n)endl;return 0;u

19、nsigned long fact( unsigned int n ) unsigned long result; if( n = 1 )result = 1; elseresult = n * fact( n - 1 ) ; return result;【任務(wù)6.5】求n!3nmainmain 函數(shù)?？蚣芎瘮?shù)調(diào)用棧框架mainfact第一次以 3 為參數(shù)調(diào)用 fact，進入函數(shù)時3nresultmainfact第二次以 2 為參數(shù)調(diào)用 fact，進入函數(shù)時fact2nresultmainfact第三次以 1 為參數(shù)調(diào)用 fact，進入函數(shù)時factfact1nresultmainfact第三

20、次以 1 為參數(shù)調(diào)用 fact，退出函數(shù)前factfact11nresultmainfact第二次以 2 為參數(shù)調(diào)用 fact，退出函數(shù)前fact22nresultmainfact第一次以 3 為參數(shù)調(diào)用 fact，退出函數(shù)前36nresult3nmain遞歸調(diào)用結(jié)束后的 main 函數(shù)棧框架遞歸與遞推的比較（以求 n! 為例）遞推：從已知的初始條件出發(fā)，逐次去求所需要的 階乘值。 fact( 1 ) = 1fact( 2 ) = 2 * fact( 1 ) = 2fact( 3 ) = 3 * fact( 2 ) = 6 遞歸：出發(fā)點不在初始條件上，而在求解目標上。 從所求的未知項出發(fā)，逐次

21、調(diào)用自身，直到 遞歸的邊界（初始條件）。 遞歸算法比較符合人的思維方式，邏輯性強， 易于理解。遞歸與遞推的相似之處： 都基于控制結(jié)構(gòu)，均涉及循環(huán) 遞推：使用顯式循環(huán)結(jié)構(gòu) 遞歸：使用選擇結(jié)構(gòu)，通過重復(fù)性的函數(shù)調(diào)用實現(xiàn)循環(huán) 均涉及終止測試，都有可能發(fā)生無限循環(huán) 遞推：在循環(huán)條件不滿足時終止 遞歸：遇到初始條件時終止 理論上，能用遞歸解決的問題也能用遞推解決。計算 x nlong double CalPower( long double x, int n ) long double result; if( n = 0 ) result = 1; else result = x * CalPower(

22、 x, n 1 ) ; return result;算法舉例(1)求兩個正整數(shù)的最大公約數(shù)算法舉例(2)unsigned int gcd(unsigned int x, unsigned int y) unsigned int t; t = x y ? x : y; while( x % t != 0 | y % t != 0 ) t-; return t;窮舉法歐氏算法步驟 1：x 整除以 y，記余數(shù)為 r步驟 2：若 r 為 0，則最大公約數(shù)即為 y，算法結(jié)束步驟 3：否則將 y 作為新 x，將 r 作為新 y，重復(fù)上述步驟unsigned int gcd(unsigned int x,

23、unsigned int y) unsigned int r; while( 1 ) r = x % y; if( r = 0 ) return y; x = y; y = r; 求兩個正整數(shù)的最大公約數(shù) unsigned int gcd(unsigned int x, unsigned int y) while( y != 0 ) unsigned int r = x%y; x = y; y = r; return x; unsigned int gcd(unsigned int x, unsigned int y) if( x%y = 0 ) return y; return gcd(y,x%y);遞歸算法求兩個正整數(shù)的最大公約數(shù)1, 1, 2, 3, 5, 8, 13, 21, fibonacci (1) = 1 fibonacci (2) = 1 fibonacci (n) = fibonacci(n-1) + fibonacci(n-2)求Fibonacci數(shù)的遞歸程序具有指數(shù)復(fù)雜性。求Fibonacci數(shù)算法舉例(3)unsigned long GetFibonacci(