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

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

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

3、函數(shù) 前面我們曾經(jīng)學(xué)習(xí)了程序設(shè)計(jì)中的三種基本例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í)參傳遞的兩個數(shù)據(jù)，函數(shù)體內(nèi)的語句是求兩個數(shù)中的較大者并將其返回主調(diào)函數(shù)。2函數(shù)定義的例子3函數(shù)的形式 函數(shù)的形式從結(jié)構(gòu)上說可以分為三種：無參函數(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ù)體只有一對花括號，花括號內(nèi)沒有任何語句的函數(shù)。例如，函數(shù)名（） 空函數(shù)不完成什么工作，只占據(jù)一個位置。在大型程序設(shè)計(jì)中，空函數(shù)用于擴(kuò)充函數(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語句將計(jì)算結(jié)果s值帶回，js()函數(shù)執(zhí)行結(jié)束，在主函數(shù)中js()值就是s的值。 在這里，函數(shù)的參數(shù)n是一個接口參數(shù)，說得更明確點(diǎn)是入口參數(shù)。如果我們調(diào)用函數(shù)：js(3)，那么在程序里所有有n的地方，n被替代成3來計(jì)算。在這里，3就被稱為實(shí)參。又如：sqrt(4)，ln(5)，這里4，5叫實(shí)參。而ln(x)，sqrt(x)中的x，y叫形參。編寫一個階乘的函數(shù)，我們給此函數(shù)取一個名字js。二、參數(shù)傳遞-【函數(shù)】1.非引用參數(shù) 普通的非引用類型的參數(shù)是通過復(fù)制對應(yīng)的實(shí)參實(shí)現(xiàn)初始化。當(dāng)用參數(shù)副本初始化形參時，函數(shù)并沒有訪問調(diào)用所傳

6、遞的實(shí)參本身，因此不會修改實(shí)參的值。舉個例子：#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中卻沒有交換。因?yàn)閟wap函數(shù)只是交換c,d兩變量副本的值。二、參數(shù)傳遞-【函數(shù)】1.非引用參數(shù)2.引用參數(shù) 引用參數(shù)直接關(guān)聯(lián)到其所綁定的對象，而并非這些對象的副本。定義引用時，必須用與該引用綁定對象初始化該引用。引用

7、形參完全以相同的方式工作。每次調(diào)用函數(shù)，引用形參被創(chuàng)建并與相應(yīng)實(shí)參關(guān)聯(lián)?，F(xiàn)在用引用參數(shù)來實(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 在此例中,因?yàn)閟wap函數(shù)的參數(shù)為引用參數(shù)，所以，在函數(shù)swap中修改a,b的值相當(dāng)于在主函數(shù)main中修改c,d的值。2.引用參數(shù)3.const形參使用const修飾參數(shù)可避免在函數(shù)執(zhí)行中修改參數(shù)。舉個例子：

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

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

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

11、該函數(shù)的返回值。其返回值的類型即為它所在函數(shù)的函數(shù)類型。當(dāng)一個函數(shù)沒有返回值時，函數(shù)中可以沒有return語句（在TC+和VC+，函數(shù)類型定義為void，可以沒有return語句；函數(shù)類型定義為int，必須有返回值），直接利用函數(shù)體的右花括號“”，作為沒有返回值的函數(shù)的返回。也可以有return語句，但return后沒有表達(dá)式。返回語句的另一種形式是：return；這時函數(shù)沒有返回值，而只把流程轉(zhuǎn)向主調(diào)函數(shù)。3函數(shù)的返回值四、函數(shù)的應(yīng)用舉例-【函數(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ù)的應(yīng)用舉例-【函數(shù)】例6.2 求1!+2!+例6.3 任意輸入10組三角形的三邊，求其面積。我們可以定義一個已知三角形三邊求其面積的函數(shù)，設(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ù)不止一個，那么在程序中調(diào)用函數(shù)的實(shí)參個數(shù)一定要與形參

14、的個數(shù)一致，第一個實(shí)參對應(yīng)第一個形參，第二個實(shí)參對應(yīng)第二個形參次序不能對調(diào)。例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 計(jì)算如圖多邊形的面積。從圖中可以看出，五邊形的面積是三個三角形面積之和。程序如下：#include#include /使用printf和scanf語句，調(diào)用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); /調(diào)用三次函數(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 計(jì)算如圖多邊形

17、的面積。例6.6 輸出以下一個圖形【分析】我們前面學(xué)習(xí)可用二重循環(huán)打印出上圖形, 現(xiàn)我們設(shè)置一個函數(shù)打印出n個連續(xù)的*號。程序如下：#includeusing namespace std;void draw_line(int);int main() for (int i=1;i=6;+i) draw_line(i); /調(diào)用函數(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); /設(shè)置域?qū)?，表示域?qū)挒? couttendl; /以上兩行為格式化輸出，相當(dāng)于printf(%8dn,t); return 0;void fa(int n) t=1; for (int i=2; i=n; +i) t*=i; 這里通過全程變量t，將過程中計(jì)算結(jié)果傳遞到t變量中。fa(x)僅僅作為程序中的一條命令被執(zhí)行。例6.7 定義函數(shù)fa求n!。例6.8 用冒泡法對數(shù)組元素按由小到大排序（數(shù)組作為函數(shù)參數(shù)）#includeusing namespace std;void bubble(int,int); /相當(dāng)于void bubble(int a,int n);int main() int array10=11,4,55,6,77,8,9,0,7,1; /大數(shù)組應(yīng)開為全局變量 cout排序前 ; for (int i=0; i10; +i) coutarrayi,; coutendl;bubble(array,10); return 0;v