C函數(shù)遞推遞歸課件

1、第六章 函數(shù)和遞推遞歸算法第六章 函數(shù)和遞推遞歸算法第一節(jié) 函數(shù)第二節(jié) 遞推算法第三節(jié) 遞歸算法第一節(jié) 函數(shù)第二節(jié) 遞推算法第三節(jié) 遞歸算法第一節(jié) 函數(shù) 前面我們曾經(jīng)學習了程序設計中的三種基本控制結構（順序、分支、循環(huán)）。用它們可以組成任何程序。但在應用中，還經(jīng)常用到子程序結構。 通常，在程序設計中，我們會發(fā)現(xiàn)一些程序段在程序的不同地方反復出現(xiàn)，此時可以將這些程序段作為相對獨立的整體，用一個標識符給它起一個名字，凡是程序中出現(xiàn)該程序段的地方，只要簡單地寫上其標識符即可。這樣的程序段，我們稱之為子程序。 子程序的使用不僅縮短了程序，節(jié)省了內存空間及減少了程序的編譯時間，而且有利于結構化程序設計。

2、因為一個復雜的問題總可將其分解成若干個子問題來解決，如果子問題依然很復雜，還可以將它繼續(xù)分解，直到每個子問題都是一個具有獨立任務的模塊。這樣編制的程序結構清晰，邏輯關系明確，無論是編寫、閱讀、調試還是修改，都會帶來極大的好處。 在一個程序中可以只有主程序而沒有子程序(本章以前都是如此)，但不能沒有主程序，也就是說不能單獨執(zhí)行子程序。 在此之前，我們曾經(jīng)介紹并使用了C+提供的各種標準函數(shù)，如abs(),sqrt()等等，這些系統(tǒng)提供的函數(shù)為我們編寫程序提供了很大的方便。比如：求sin(1)+ sin(2)+sin(100)的值。但這些函數(shù)只是常用的基本函數(shù)，編程時經(jīng)常需要自定義一些函數(shù)。第一節(jié)

3、函數(shù) 前面我們曾經(jīng)學習了程序設計中的三種基本例6.1 求：1!+2!+3!+10！#include using namespace std; int main() int sum=0; for (int i=1; i=10; i+) sum+=js(i); coutsum=sumy?x:y; 該函數(shù)返回值是整型，有兩個整型的形參，用來接受實參傳遞的兩個數(shù)據(jù)，函數(shù)體內的語句是求兩個數(shù)中的較大者并將其返回主調函數(shù)。2函數(shù)定義的例子3函數(shù)的形式 函數(shù)的形式從結構上說可以分為三種：無參函數(shù)、有參函數(shù)和空函數(shù)。它們的定義形式都相同。（1）無參函數(shù)無參函數(shù)顧名思義即為沒有參數(shù)傳遞的函數(shù)，無參函數(shù)一般不需要

4、帶回函數(shù)值，所以函數(shù)類型說明為void。（2）有參函數(shù)有參函數(shù)即有參數(shù)傳遞的函數(shù)，一般需要帶回函數(shù)值。例如int max(int x,int y)函數(shù)。（3）空函數(shù)空函數(shù)即函數(shù)體只有一對花括號，花括號內沒有任何語句的函數(shù)。例如，函數(shù)名（） 空函數(shù)不完成什么工作，只占據(jù)一個位置。在大型程序設計中，空函數(shù)用于擴充函數(shù)功能。3函數(shù)的形式編寫一個階乘的函數(shù)，我們給此函數(shù)取一個名字js。int js(int n)int s=1;for (int i=1; i=n; +i)s*=i;return s; 在本例中，函數(shù)名叫js，只有一個int型的自變量n，函數(shù)js屬int型。在本函數(shù)中，要用到兩個變量i，s

5、。在函數(shù)體中，是一個求階乘的語句，n的階乘的值在s中，最后由return語句將計算結果s值帶回，js()函數(shù)執(zhí)行結束，在主函數(shù)中js()值就是s的值。 在這里，函數(shù)的參數(shù)n是一個接口參數(shù)，說得更明確點是入口參數(shù)。如果我們調用函數(shù)：js(3)，那么在程序里所有有n的地方，n被替代成3來計算。在這里，3就被稱為實參。又如：sqrt(4)，ln(5)，這里4，5叫實參。而ln(x)，sqrt(x)中的x，y叫形參。編寫一個階乘的函數(shù)，我們給此函數(shù)取一個名字js。二、參數(shù)傳遞-【函數(shù)】1.非引用參數(shù) 普通的非引用類型的參數(shù)是通過復制對應的實參實現(xiàn)初始化。當用參數(shù)副本初始化形參時，函數(shù)并沒有訪問調用所傳

6、遞的實參本身，因此不會修改實參的值。舉個例子：#includeusing namespace std;void swap(int a,int b)int tmp=a;a=b;b=tmp;int main()int c=1,d=2;swap(c,d);coutc dendl;return 0; /程序輸出為：1 2 在此例中，雖然在swap函數(shù)中交換了a,b兩數(shù)的值，但是在main中卻沒有交換。因為swap函數(shù)只是交換c,d兩變量副本的值。二、參數(shù)傳遞-【函數(shù)】1.非引用參數(shù)2.引用參數(shù) 引用參數(shù)直接關聯(lián)到其所綁定的對象，而并非這些對象的副本。定義引用時，必須用與該引用綁定對象初始化該引用。引用

7、形參完全以相同的方式工作。每次調用函數(shù)，引用形參被創(chuàng)建并與相應實參關聯(lián)。現(xiàn)在用引用參數(shù)來實現(xiàn)swap：#includeusing namespace std;void swap(int &a,int &b)int tmp=a;a=b;b=tmp;int main()int c=1,d=2;swap(c,d); /交換變量coutc dendl;return 0; /程序輸出為：2 1 在此例中,因為swap函數(shù)的參數(shù)為引用參數(shù)，所以，在函數(shù)swap中修改a,b的值相當于在主函數(shù)main中修改c,d的值。2.引用參數(shù)3.const形參使用const修飾參數(shù)可避免在函數(shù)執(zhí)行中修改參數(shù)。舉個例子：

8、void solve(const int &a) a=1; /該函數(shù)是錯誤的，因為a是 const形參，所以在函數(shù)體中不能被修改。使用const修飾參數(shù)也可使函數(shù)接受常量作為引用參數(shù)。舉個例子： void fa(const int &a) void fb(int &a) int main() fa(2); /正確，因為fa()使用了常量引用形參。fb(2); /錯誤，因為fb()使用了非常量引用形參，不可以接受常量2。3.const形參三、函數(shù)的聲明和調用-【函數(shù)】1函數(shù)的聲明 調用函數(shù)之前先要聲明函數(shù)原型。在主調函數(shù)中，或所有函數(shù)定義之前，按如下形式聲明：類型說明符 被調函數(shù)名（含類型說明的

9、形參表）； 如果是在所有函數(shù)定義之前聲明了函數(shù)原型，那么該函數(shù)原型在本程序文件中任何地方都有效，也就是說在本程序文件中任何地方都可以依照該原型調用相應的函數(shù)。如果是在某個主調函數(shù)內部聲明了被調用函數(shù)原型，那么該原型就只能在這個函數(shù)內部有效。 函數(shù)原型和函數(shù)定義在返回值類型、函數(shù)名和參數(shù)個數(shù)與類型必須完全一致，否則，就會發(fā)生編譯錯誤。下面對max()函數(shù)原型聲明是合法的。int max（int x, int y）;也可以：int max（int , int ）; 可以看到函數(shù)原型聲明與函數(shù)定義時的第一行類似，只多了一個分號，成為了一個聲明語句而已。三、函數(shù)的聲明和調用-【函數(shù)】1函數(shù)的聲明2函數(shù)

10、的調用聲明了函數(shù)原型之后，便可以按如下形式調用函數(shù)：函數(shù)名（實參列表）實參列表中應給出與函數(shù)原型形參個數(shù)相同、類型相符的實參。在主調函數(shù)中的參數(shù)稱為實參，實參一般應具有確定的值。實參可以是常量、表達式，也可以是已有確定值的變量，數(shù)組或指針名。函數(shù)調用可以作為一條語句，這時函數(shù)可以沒有返回值。函數(shù)調用也可以出現(xiàn)在表達式中，這時就必須有一個明確的返回值。2函數(shù)的調用3函數(shù)的返回值 在組成函數(shù)體的各類語句中，值得注意的是返回語句return。它的一般形式是：return（表達式）； 其功能是把程序流程從被調函數(shù)轉向主調函數(shù)并把表達式的值帶回主調函數(shù)，實現(xiàn)函數(shù)的返回。所以，在圓括號表達式的值實際上就是

11、該函數(shù)的返回值。其返回值的類型即為它所在函數(shù)的函數(shù)類型。當一個函數(shù)沒有返回值時，函數(shù)中可以沒有return語句（在TC+和VC+，函數(shù)類型定義為void，可以沒有return語句；函數(shù)類型定義為int，必須有返回值），直接利用函數(shù)體的右花括號“”，作為沒有返回值的函數(shù)的返回。也可以有return語句，但return后沒有表達式。返回語句的另一種形式是：return；這時函數(shù)沒有返回值，而只把流程轉向主調函數(shù)。3函數(shù)的返回值四、函數(shù)的應用舉例-【函數(shù)】例6.2 求1!+2!+10!的值。程序如下：#includeusing namespace std;nt js(int);int main()i

12、nt sum=0;for (int i=1; i=10; +i) sum+=js(i);coutsum=sumendl;return 0;int js(int n)int s=1;for (int i=1; i=n; +i)s*=i;return s;四、函數(shù)的應用舉例-【函數(shù)】例6.2 求1!+2!+例6.3 任意輸入10組三角形的三邊，求其面積。我們可以定義一個已知三角形三邊求其面積的函數(shù)，設為area(a,b,c)。程序如下：#include#include using namespace std;double area(double,double,double);int main()

13、for (int i=1; i=10; +i) double a,b,c; coutinput a,b,cabc; if (a+b=c)|(a+c=b)|(b+c=a) coutdata error!endl; /判斷三角形是否合法 else couts=area(a,b,c)endl; return 0;double area(double a,double b,double c) /此函數(shù)為 海倫秦九韶公式 double p=(a+b+c)/2; return sqrt(p*(p-a)*(p-b)*(p-c);在函數(shù)說明中，如果形參的個數(shù)不止一個，那么在程序中調用函數(shù)的實參個數(shù)一定要與形參

14、的個數(shù)一致，第一個實參對應第一個形參，第二個實參對應第二個形參次序不能對調。例6.3 任意輸入10組三角形的三邊，求其面積。doubl例6.4 定義一個函數(shù)check(n,d)，讓它返回一個布爾值。如果數(shù)字d在正整數(shù)n的某位中出現(xiàn)則送回true，否則送回false。例如：check(325719,3)=true；check(77829,1)=false；#includeusing namespace std;bool check(int,int);int main() int a,b; coutinput n,dab; if (check(a,b)=true) couttrueendl; el

15、se coutfalseendl; return 0;bool check(int n,int d) while (n) /C+中 非0為真 int e=n%10; n/=10; if (e=d) return true; return false;例6.4 定義一個函數(shù)check(n,d)，讓它返回一個布爾例6.5 計算如圖多邊形的面積。從圖中可以看出，五邊形的面積是三個三角形面積之和。程序如下：#include#include /使用printf和scanf語句，調用cstdio庫#include using namespace std;double area(double,double,

16、double);int main() double b1,b2,b3,b4,b5,b6,b7,s; coutplease input b1,b2,b3,b4,b5,b6,b7:b1b2b3b4b5b6b7; s=area(b1,b5,b6)+area(b2,b6,b7)+area(b3,b4,b7); /調用三次函數(shù)area printf(s=%10.3lfn,s); return 0; double area(double a,double b,double c) double p=(a+b+c)/2; return sqrt(p*(p-a)*(p-b)*(p-c);例6.5 計算如圖多邊形

17、的面積。例6.6 輸出以下一個圖形【分析】我們前面學習可用二重循環(huán)打印出上圖形, 現(xiàn)我們設置一個函數(shù)打印出n個連續(xù)的*號。程序如下：#includeusing namespace std;void draw_line(int);int main() for (int i=1;i=6;+i) draw_line(i); /調用函數(shù),第i行打印i個連續(xù)星號 return 0;void draw_line(int n) /該過程打印出連續(xù)n 個星號,并換行 for (int i=1; i=n; +i) cout*; coutendl;例6.6 輸出以下一個圖形例6.7 定義函數(shù)fa求n!。#incl

18、ude#includeusing namespace std;void fa(int);int t; /t定義為全程變量int main() int x; cinx; fa(x); coutsetw(5)x; cout.width(8); /設置域寬，表示域寬為8 couttendl; /以上兩行為格式化輸出，相當于printf(%8dn,t); return 0;void fa(int n) t=1; for (int i=2; i=n; +i) t*=i; 這里通過全程變量t，將過程中計算結果傳遞到t變量中。fa(x)僅僅作為程序中的一條命令被執(zhí)行。例6.7 定義函數(shù)fa求n!。例6.8 用冒泡法對數(shù)組元素按由小到大排序（數(shù)組作為函數(shù)參數(shù)）#includeusing namespace std;void bubble(int,int); /相當于void bubble(int a,int n);int main() int array10=11,4,55,6,77,8,9,0,7,1; /大數(shù)組應開為全局變量 cout排序前 ; for (int i=0; i10; +i) coutarrayi,; coutendl;bubble(array,10); return 0;v