第6章講義函數(shù)遞推遞歸(C++版)

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

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

3、e std; int main三 int sum=0; for (int i=1; i=10; i+) sum+=js(i); coutsum=sumy?x:y; 該函數(shù)返回值是整型，有兩個(gè)整型的形參，用來(lái)接受實(shí)參傳遞的兩個(gè)數(shù)據(jù)，函數(shù)體內(nèi)的語(yǔ)句是求兩個(gè)數(shù)中的較大者并將其返回主調(diào)函數(shù)。3 3函數(shù)的形式函數(shù)的形式 函數(shù)的形式從結(jié)構(gòu)上說(shuō)可以分為三種：無(wú)參函數(shù)、有參函數(shù)和空函函數(shù)的形式從結(jié)構(gòu)上說(shuō)可以分為三種：無(wú)參函數(shù)、有參函數(shù)和空函數(shù)。它們的定義形式都相同。數(shù)。它們的定義形式都相同。（1 1）無(wú)參函數(shù)）無(wú)參函數(shù)無(wú)參函數(shù)顧名思義即為沒(méi)有參數(shù)傳遞的函數(shù)，無(wú)參函數(shù)一般不需要帶回函數(shù)無(wú)參函數(shù)顧名思義即為沒(méi)有參

4、數(shù)傳遞的函數(shù)，無(wú)參函數(shù)一般不需要帶回函數(shù)值，所以函數(shù)類型說(shuō)明為值，所以函數(shù)類型說(shuō)明為voidvoid。（2 2）有參函數(shù)）有參函數(shù)有參函數(shù)即有參數(shù)傳遞的函數(shù)，一般需要帶回函數(shù)值。例如有參函數(shù)即有參數(shù)傳遞的函數(shù)，一般需要帶回函數(shù)值。例如int max(int x,int y)int max(int x,int y)函數(shù)。函數(shù)。（3 3）空函數(shù)）空函數(shù)空函數(shù)即函數(shù)體只有一對(duì)花括號(hào)，花括號(hào)內(nèi)沒(méi)有任何語(yǔ)句的函數(shù)?？蘸瘮?shù)即函數(shù)體只有一對(duì)花括號(hào)，花括號(hào)內(nèi)沒(méi)有任何語(yǔ)句的函數(shù)。例如，例如，函數(shù)名講義函數(shù)名講義 空函數(shù)不完成什么工作，只占據(jù)一個(gè)位置。在大型程序設(shè)計(jì)中，空函數(shù)空函數(shù)不完成什么工作，只占據(jù)一個(gè)位置。

5、在大型程序設(shè)計(jì)中，空函數(shù)用于擴(kuò)充函數(shù)功能。用于擴(kuò)充函數(shù)功能。編寫(xiě)一個(gè)階乘的函數(shù)，我們給此函數(shù)取一個(gè)名字js。int js(int n)int s=1;for (int i=1; i=n; +i)s*=i;return s; 在本例中，函數(shù)名叫js，只有一個(gè)int型的自變量n，函數(shù)js屬int型。在本函數(shù)中，要用到兩個(gè)變量i，s。在函數(shù)體中，是一個(gè)求階乘的語(yǔ)句，n的階乘的值在s中，最后由return語(yǔ)句將計(jì)算結(jié)果s值帶回，js三函數(shù)執(zhí)行結(jié)束，在主函數(shù)中js三值就是s的值。 在這里，函數(shù)的參數(shù)n是一個(gè)接口參數(shù)，說(shuō)得更明確點(diǎn)是入口參數(shù)。如果我們調(diào)用函數(shù)：js(3)，那么在程序里所有有n的地方，n被替

6、代成3來(lái)計(jì)算。在這里，3就被稱為實(shí)參。又如：sqrt(4)，ln(5)，這里4，5叫實(shí)參。而ln(x)，sqrt(x)中的x，y叫形參。二、參數(shù)傳遞-【函數(shù)】 普通的非引用類型的參數(shù)是通過(guò)復(fù)制對(duì)應(yīng)的實(shí)參實(shí)現(xiàn)初始化。普通的非引用類型的參數(shù)是通過(guò)復(fù)制對(duì)應(yīng)的實(shí)參實(shí)現(xiàn)初始化。當(dāng)用參數(shù)副本初始化形參時(shí)，函數(shù)并沒(méi)有訪問(wèn)調(diào)用所傳遞的實(shí)參本身，當(dāng)用參數(shù)副本初始化形參時(shí)，函數(shù)并沒(méi)有訪問(wèn)調(diào)用所傳遞的實(shí)參本身，因此不會(huì)修改實(shí)參的值。舉個(gè)例子：因此不會(huì)修改實(shí)參的值。舉個(gè)例子：#include#includeusing namespace std;using namespace std;void swap(int a,

7、int b)void swap(int a,int b) int tmp=a;a=b;b=tmp;int tmp=a;a=b;b=tmp; int mainint main三三 int c=1,d=2;int c=1,d=2;swap(c,d);swap(c,d);coutc dendl;coutc dendl;return 0;return 0; / /程序輸出為：程序輸出為：1 21 2 在此例中，雖然在在此例中，雖然在swapswap函數(shù)中交換了函數(shù)中交換了a,ba,b兩數(shù)的值，但是在兩數(shù)的值，但是在mainmain中卻沒(méi)中卻沒(méi)有交換。因?yàn)橛薪粨Q。因?yàn)閟wapswap函數(shù)只是交換函數(shù)只是

8、交換c,dc,d兩變量副本的值。兩變量副本的值。 引用參數(shù)直接關(guān)聯(lián)到其所綁定的對(duì)象，而并非這些對(duì)象的副本。定引用參數(shù)直接關(guān)聯(lián)到其所綁定的對(duì)象，而并非這些對(duì)象的副本。定義引用時(shí)，必須用與該引用綁定對(duì)象初始化該引用。引用形參完全以相同的義引用時(shí)，必須用與該引用綁定對(duì)象初始化該引用。引用形參完全以相同的方式工作。每次調(diào)用函數(shù)，引用形參被創(chuàng)建并與相應(yīng)實(shí)參關(guān)聯(lián)?，F(xiàn)在用引用方式工作。每次調(diào)用函數(shù)，引用形參被創(chuàng)建并與相應(yīng)實(shí)參關(guān)聯(lián)?，F(xiàn)在用引用參數(shù)來(lái)實(shí)現(xiàn)參數(shù)來(lái)實(shí)現(xiàn)swapswap：#include#includeusing namespace std;using namespace std;void swap(

9、int &a,int &b)void swap(int &a,int &b) int tmp=a;a=b;b=tmp;int tmp=a;a=b;b=tmp; int mainint main三三 int c=1,d=2;int c=1,d=2;swap(c,d); /swap(c,d); /交換變量交換變量coutc dendl;coutc dendl;return 0;return 0; / /程序輸出為：程序輸出為：2 12 1 在此例中在此例中, ,因?yàn)橐驗(yàn)閟wapswap函數(shù)的參數(shù)為引用參數(shù)，所以，在函數(shù)函數(shù)的參數(shù)為引用參數(shù)，所以，在函數(shù)swapswa

10、p中中修改修改a,ba,b的值相當(dāng)于在主函數(shù)的值相當(dāng)于在主函數(shù)mainmain中修改中修改c,dc,d的值。的值。使用使用constconst修飾參數(shù)可避免在函數(shù)執(zhí)行中修改參數(shù)。修飾參數(shù)可避免在函數(shù)執(zhí)行中修改參數(shù)。舉個(gè)例子：舉個(gè)例子： void solve(const int &a)void solve(const int &a) a=1;a=1; / /該函數(shù)是錯(cuò)誤的，因?yàn)樵摵瘮?shù)是錯(cuò)誤的，因?yàn)閍 a是是 const const形參，所以在函數(shù)體中不能形參，所以在函數(shù)體中不能被修改。被修改。使用使用constconst修飾參數(shù)也可使函數(shù)接受常量作為引用參數(shù)。修飾參數(shù)也可使函數(shù)接

11、受常量作為引用參數(shù)。舉個(gè)例子：舉個(gè)例子： void fa(const int &a) void fa(const int &a) void fb(int &a) void fb(int &a) int mainint main三三 fa(2); /fa(2); /正確，因?yàn)檎_，因?yàn)閒afa三使用了常量引用形參。三使用了常量引用形參。fb(2); /fb(2); /錯(cuò)誤，因?yàn)殄e(cuò)誤，因?yàn)閒bfb三使用了非常量引用三使用了非常量引用形參，不可以接受常量形參，不可以接受常量2 2。 三、函數(shù)的聲明和調(diào)用-【函數(shù)】1 1函數(shù)的聲明函數(shù)的聲明 調(diào)用函數(shù)之前先要聲明函數(shù)原型

12、。在主調(diào)函數(shù)中，或所有函數(shù)定義之前調(diào)用函數(shù)之前先要聲明函數(shù)原型。在主調(diào)函數(shù)中，或所有函數(shù)定義之前，按如下形式聲明：，按如下形式聲明：類型說(shuō)明符類型說(shuō)明符 被調(diào)函數(shù)名（含類型說(shuō)明的形參表）；被調(diào)函數(shù)名（含類型說(shuō)明的形參表）； 如果是在所有函數(shù)定義之前聲明了函數(shù)原型，那么該函數(shù)原型在本程序文件如果是在所有函數(shù)定義之前聲明了函數(shù)原型，那么該函數(shù)原型在本程序文件中任何地方都有效，也就是說(shuō)在本程序文件中任何地方都可以依照該原型調(diào)用相應(yīng)的中任何地方都有效，也就是說(shuō)在本程序文件中任何地方都可以依照該原型調(diào)用相應(yīng)的函數(shù)。如果是在某個(gè)主調(diào)函數(shù)內(nèi)部聲明了被調(diào)用函數(shù)原型，那么該原型就只能在這個(gè)函數(shù)。如果是在某個(gè)主調(diào)

13、函數(shù)內(nèi)部聲明了被調(diào)用函數(shù)原型，那么該原型就只能在這個(gè)函數(shù)內(nèi)部有效。函數(shù)內(nèi)部有效。 函數(shù)原型和函數(shù)定義在返回值類型、函數(shù)名和參數(shù)個(gè)數(shù)與類型必須完全一致函數(shù)原型和函數(shù)定義在返回值類型、函數(shù)名和參數(shù)個(gè)數(shù)與類型必須完全一致，否則，就會(huì)發(fā)生編譯錯(cuò)誤。下面對(duì)，否則，就會(huì)發(fā)生編譯錯(cuò)誤。下面對(duì)maxmax三函數(shù)原型聲明是合法的。三函數(shù)原型聲明是合法的。int maxint max（int x, int yint x, int y）; ;也可以：也可以：int maxint max（int , int int , int ）; ; 可以看到函數(shù)原型聲明與函數(shù)定義時(shí)的第一行類似，只多了一可以看到函數(shù)原型聲明與函數(shù)

14、定義時(shí)的第一行類似，只多了一個(gè)分號(hào)，成為了一個(gè)聲明語(yǔ)句而已。個(gè)分號(hào)，成為了一個(gè)聲明語(yǔ)句而已。l2 2函數(shù)的調(diào)用函數(shù)的調(diào)用聲明了函數(shù)原型之后，便可以按如下形式調(diào)用函數(shù)：函數(shù)名（實(shí)參列表）函數(shù)名（實(shí)參列表）實(shí)參列表中應(yīng)給出與函數(shù)原型形參個(gè)數(shù)相同、類型相符的實(shí)參。在主調(diào)函數(shù)中的參數(shù)稱為實(shí)參，實(shí)參一般應(yīng)具有確定的值。實(shí)參可以是常量、表達(dá)式，也可以是已有確定值的變量，數(shù)組或指針名。函數(shù)調(diào)用可以作為一條語(yǔ)句，這時(shí)函數(shù)可以沒(méi)有返回值。函數(shù)調(diào)用也可以出現(xiàn)在表達(dá)式中，這時(shí)就必須有一個(gè)明確的返回值。3 3函數(shù)的返回值函數(shù)的返回值 在組成函數(shù)體的各類語(yǔ)句中，值得注意的是返回語(yǔ)句return。它的一般形式是： ret

15、urnreturn（表達(dá)式）；（表達(dá)式）； 其功能是把程序流程從被調(diào)函數(shù)轉(zhuǎn)向主調(diào)函數(shù)并把表達(dá)式的值帶回主調(diào)函數(shù)，實(shí)現(xiàn)函數(shù)的返回。所以，在圓括號(hào)表達(dá)式的值實(shí)際上就是該函數(shù)的返回值。其返回值的類型即為它所在函數(shù)的函數(shù)類型。當(dāng)一個(gè)函數(shù)沒(méi)有返回值時(shí)，函數(shù)中可以沒(méi)有return語(yǔ)句（在TC+和VC+，函數(shù)類型定義為void，可以沒(méi)有return語(yǔ)句；函數(shù)類型定義為int，必須有返回值），直接利用函數(shù)體的右花括號(hào)“”，作為沒(méi)有返回值的函數(shù)的返回。也可以有return語(yǔ)句，但return后沒(méi)有表達(dá)式。返回語(yǔ)句的另一種形式是：return；這時(shí)函數(shù)沒(méi)有返回值，而只把流程轉(zhuǎn)向主調(diào)函數(shù)。四、函數(shù)的應(yīng)用舉例-【函數(shù)

16、】例6.2 求1!+2!+10!的值。程序如下：#includeusing namespace std;nt js(int);int main三int 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;例6.3 任意輸入10組三角形的三邊，求其面積。我們可以定義一個(gè)已知三角形三邊求其面積的函數(shù)，設(shè)為area(a,b,c)。程序如下：#include#include using namespace st

17、d;double area(double,double,double);int main三 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)*

18、(p-c);在函數(shù)說(shuō)明中，如果形參的個(gè)數(shù)不止一個(gè)，那么在程序中調(diào)用函數(shù)的實(shí)參個(gè)數(shù)一定要與形參的個(gè)數(shù)一致，第一個(gè)實(shí)參對(duì)應(yīng)第一個(gè)形參，第二個(gè)實(shí)參對(duì)應(yīng)第二個(gè)形參次序不能對(duì)調(diào)。例6.4 定義一個(gè)函數(shù)check(n,d)，讓它返回一個(gè)布爾值。如果數(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)

19、couttrueendl; else 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.5 計(jì)算如圖多邊形的面積。從圖中可以看出，五邊形的面積是三個(gè)三角形面積之和。程序如下：#include#include /使用printf和scanf語(yǔ)句，調(diào)用cstdio庫(kù)#include using namespace std;double area(double,double,double);int ma

20、in三 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.6 輸出以下一個(gè)圖形【分析】我們前面學(xué)習(xí)可用二重

21、循環(huán)打印出上圖形, 現(xiàn)我們?cè)O(shè)置一個(gè)函數(shù)打印出n個(gè)連續(xù)的*號(hào)。程序如下：#includeusing namespace std;void draw_line(int);int main三 for (int i=1;i=6;+i) draw_line(i); /調(diào)用函數(shù),第i行打印i個(gè)連續(xù)星號(hào) return 0;void draw_line(int n) /該過(guò)程打印出連續(xù)n 個(gè)星號(hào),并換行 for (int i=1; i=n; +i) cout*; coutendl;例6.7 定義函數(shù)fa求n!。#include#includeusing namespace std;void fa(int);i

22、nt 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; 這里通過(guò)全程變量t，將過(guò)程中計(jì)算結(jié)果傳遞到t變量中。fa(x)僅僅作為程序中的一條命令被執(zhí)行。例6.8 用冒泡法對(duì)數(shù)組元素按由小到大排序（數(shù)組作為函數(shù)參數(shù)）#includeusing namespace std;void bu

23、bble(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)開(kāi)為全局變量 cout排序前 ; for (int i=0; i10; +i) coutarrayi,; coutendl;bubble(array,10); return 0;void bubble(int a,int n) for (int i=1; in; +i) for (int j=0; jaj+1) /判斷并交換變量 int temp=aj; aj=aj+1; aj+1=temp; cout排序

24、后 ;for (int i=0; i10; +i) coutai,; coutendl; 在前面我們已經(jīng)知道數(shù)組名是該數(shù)組在內(nèi)存的首地址。將數(shù)組名作為參數(shù)傳給函數(shù)，實(shí)際上是把數(shù)組的地址傳給函數(shù)。形參數(shù)組和實(shí)參數(shù)組的首地址重合，因此在被調(diào)用函數(shù)中對(duì)數(shù)組元素值進(jìn)行改變，主調(diào)函數(shù)中實(shí)參數(shù)組的相應(yīng)元素值也會(huì)改變。例6.9 分析下列函數(shù)嵌套調(diào)用的結(jié)果。（函數(shù)的嵌套調(diào)用）#includeusing namespace std;void fun1三,fun2三,fun3三;int main三 coutIts in main三.endl; fun2三; coutIts back in main三.n; / 這

25、句語(yǔ)句等于 coutIt is back in main三.endl; return 0;void fun1三 coutIts in fun1三.n; fun3三; coutits back in fun1三.n;void fun2三 coutIts in fun2三.n; fun1三; coutIts back in fun2三.n;void fun3三 coutIts in fun3三.n;程序的執(zhí)行結(jié)果是：Its in main三.Its in fun2三.Its in fun1三.Its in fun3三.Its back in fun1三.Its back in fun2三.Its

26、back in main三.函數(shù)的嵌套調(diào)用指的是一個(gè)函數(shù)調(diào)用另一個(gè)函數(shù)，而被調(diào)用函數(shù)又可調(diào)用其它函數(shù)。例如，在調(diào)用A函數(shù)的過(guò)程中，可以調(diào)用B函數(shù)，在調(diào)用B函數(shù)的過(guò)程中，還可以調(diào)用C函數(shù)當(dāng)C函數(shù)調(diào)用結(jié)束后，返回到B函數(shù)，當(dāng)B函數(shù)調(diào)用結(jié)束后，再返回到A函數(shù)。這就是函數(shù)的嵌套調(diào)用過(guò)程。五、全程變量、局部變量及它們的作用域-【函數(shù)】 在函數(shù)外部定義的變量稱為外部變量或全局變量，在函數(shù)內(nèi)部定義的變量稱為內(nèi)部變量或局部變量。1 1全局變量全局變量 全局變量的作用域是從變量定義的位置起直至本源文件結(jié)束止，即從定義位置之后的所有函數(shù)都可以訪問(wèn)該全局變量。下面通過(guò)例子來(lái)說(shuō)明這一點(diǎn)。0 全局變量的應(yīng)用。#incl

27、ude#includeusing namespace std;int x,y; /定義全局變量x，yint fun1(int s) /訪問(wèn)全局變量x，y x=10; y=x*s; return x+y;float a,b; /定義全局變量a，bvoid fun2(int c) coutx=x y=ymn; coutfun1(m)endl; fun2(n);couta=a b=bendl; /訪問(wèn)全局變量a，breturn 0; 當(dāng)在鍵盤上輸入6 9后程序的執(zhí)行結(jié)果是：70 x=10 y=60a=0 b=0 程序中主函數(shù)先調(diào)用fun1三，實(shí)參是6，將實(shí)參值傳給形參s(即s=6)，函數(shù)fun1中x

28、值為10，y值為60，return語(yǔ)句將xy的和返回，fun1三結(jié)束。主函數(shù)輸出返回值之后，調(diào)用fun2三，在fun2三中輸出全局變量x和y 的值，之后返回主函數(shù)。在主函數(shù)中輸出全局變量a和b值。由于a、b在聲明時(shí)未賦初值，系統(tǒng)的默認(rèn)值為0。使用全局變量的說(shuō)明：使用全局變量的說(shuō)明： 在一個(gè)函數(shù)內(nèi)部，既可以使用本函數(shù)定義的局部變量，也可以使用在此函數(shù)前定義的全局變量。全局變量的作用是使得函數(shù)間多了一種傳遞信息的方式。如果在一個(gè)程序中多個(gè)函數(shù)都要對(duì)同一個(gè)變量進(jìn)行處理，即共享，就可以將這個(gè)變量定義成全局變量，使用非常方便，但副作用也不可低估。 過(guò)多地使用全局變量，會(huì)增加調(diào)試難度。因?yàn)槎鄠€(gè)函數(shù)都能改變

29、全局變量的值，不易判斷某個(gè)時(shí)刻全局變量的值。 過(guò)多地使用全局變量，會(huì)降低程序的通用性。如果將一個(gè)函數(shù)移植到另一個(gè)程序中，需要將全局變量一起移植過(guò)去，同時(shí)還有可能出現(xiàn)重名問(wèn)題。 全局變量在程序執(zhí)行的全過(guò)程中一直占用內(nèi)存單元。 全局變量在定義時(shí)若沒(méi)有賦初值，其默認(rèn)值為0。2 2局部變量局部變量 局部變量的作用域是在定義該變量的函數(shù)內(nèi)部。換句話說(shuō)，局部變量只在定義它的函數(shù)內(nèi)有效。在一個(gè)子程序內(nèi)定義的變量也是局部變量，其作用域是該子程序。函數(shù)的形參也是局部變量。 由于局部變量的作用域僅局限于本函數(shù)內(nèi)部，所以，在不同的函數(shù)中變量名可以相同，它們分別代表不同的對(duì)象，在內(nèi)存中占據(jù)不同的內(nèi)存單元，互不干擾。一

30、個(gè)局部變量和一個(gè)全局變量是可以重名的，在相同的作用域內(nèi)局部變量有效時(shí)全局變量無(wú)效。即局部變量可以屏蔽全局變量。六、函數(shù)的綜合應(yīng)用-【函數(shù)】1 編程輸入十進(jìn)制整數(shù)N（N：-3276732767），請(qǐng)輸出它對(duì)應(yīng)的二進(jìn)制、八進(jìn)制、十六進(jìn)制數(shù)?！痉治觥窟@是一道進(jìn)行數(shù)制轉(zhuǎn)換的問(wèn)題，將十進(jìn)制整數(shù)轉(zhuǎn)換成R進(jìn)制的數(shù)，算法是：除以R取余，再將余數(shù)倒過(guò)來(lái)寫(xiě)出即是R進(jìn)制的數(shù)。本例是要求把一個(gè)十進(jìn)制數(shù)同時(shí)轉(zhuǎn)換成二進(jìn)制、八進(jìn)制、十六進(jìn)制數(shù)。因此可以設(shè)計(jì)一個(gè)過(guò)程同時(shí)處理這三種的進(jìn)制轉(zhuǎn)換。程序如下：#include#includeusing namespace std;void TurnData(int n,int a);

31、char ch6=A,B,C,D,E,F;int main三 int n; cinn; TurnData(n,2); /n轉(zhuǎn)成2進(jìn)制數(shù) TurnData(n,8); /n轉(zhuǎn)成8進(jìn)制數(shù) TurnData(n,16); /n轉(zhuǎn)成16進(jìn)制數(shù) return 0;void TurnData(int n,int a) int x17,i,j,k=0; coutn turn into a : endl; if (n0) cout=1; -h) if (xh10) coutxh; else coutchxh-10; coutendl;這里的過(guò)程TurnData中的參數(shù)不需要把什么值返回給主程序，因此設(shè)為形參即

32、可。2 編寫(xiě)一個(gè)給一個(gè)分?jǐn)?shù)約分的程序。 程序如下：#include#includeusing namespace std;void common(int x,int y);int main三 int a,b; cinab; common(a,b);void common(int x,int y) int m=x,n=y,r; /用輾轉(zhuǎn)相除法求x,y的最大公約數(shù) do r=m%n; m=n; n=r; while (r!=0); x/=m; /用兩者的最大公約數(shù)i對(duì)x,y進(jìn)行約分 y/=m; coutsetw(5)xsetw(5)yendl;運(yùn)行結(jié)果：輸入 : 12 8輸出 : 3 2課堂練習(xí)-

33、【函數(shù)】1.編程找出由鍵盤任意輸入二個(gè)整數(shù)中的較大數(shù)。2.編程找出由鍵盤任意輸入三個(gè)整數(shù)中的最大數(shù)。3.求從鍵盤任意輸入三個(gè)自然數(shù)的最大公約數(shù)。4.求從鍵盤任意輸入兩個(gè)自然數(shù)的最小公倍數(shù)。5.用函數(shù)求1+2+3+n的和（n R 0）3.求正整數(shù)2和100之間的完全數(shù)。完全數(shù)：因子之和等于它本身的自然數(shù)，如6=1+2+34.如果一個(gè)自然數(shù)是素?cái)?shù),且它的數(shù)字位置經(jīng)過(guò)對(duì)換后仍為素?cái)?shù),則稱為絕對(duì)素?cái)?shù),例如13。試求出所有二位絕對(duì)素?cái)?shù)。5.自然數(shù)a的因子是指能被a整除的所有自然數(shù)，但不含a本身。例如12的因子為：1,2,3,4,6。若自然數(shù)a的因子之和為b，而且b的因子之和又等于a，則稱a,b為一對(duì)“親

34、和數(shù)” 。求最小的一對(duì)親和數(shù)(ab)。6.如果一個(gè)數(shù)從左邊讀和從右邊讀都是同一個(gè)數(shù)，就稱為回文數(shù)。例如6886就是一個(gè)回文數(shù)，求出所有的既是回文數(shù)又是素?cái)?shù)的三位數(shù)。7.編寫(xiě)程序計(jì)算表達(dá)式：Y = x2 + SH(x)，SH(x)是雙曲正弦函數(shù)8.輸入自然數(shù)n，求前n個(gè)合數(shù)（非素?cái)?shù)），其素因子僅有2，3，或5。9.哥德巴赫猜想的命題之一是:大于6 的偶數(shù)等于兩個(gè)素?cái)?shù)之和。編程將6100所有偶數(shù)表示成兩個(gè)素?cái)?shù)之和。第二節(jié) 遞推算法 遞推和遞歸是編程中常用的基本算法。在前面的解題中已經(jīng)用到了遞推算法，下面對(duì)這兩種算法的基本應(yīng)用進(jìn)行詳細(xì)研究討論。遞推算法是一種用若干步可重復(fù)的簡(jiǎn)單運(yùn)算（規(guī)律）來(lái)描述復(fù)雜

35、問(wèn)題的方法。 遞推算法以初始起點(diǎn)值為基礎(chǔ)，用相同的運(yùn)算規(guī)律，逐次重復(fù)運(yùn)算，直至運(yùn)算結(jié)束。這種從“起點(diǎn)”重復(fù)相同的方法直至到達(dá)一定“邊界”，猶如單向運(yùn)動(dòng)，用循環(huán)可以實(shí)現(xiàn)。遞推的本質(zhì)是按規(guī)律逐次推出（計(jì)算）下一步的結(jié)果。3 植樹(shù)節(jié)那天，有五位參加了植樹(shù)活動(dòng)，他們完成植樹(shù)的棵數(shù)都不相同。問(wèn)第一位同學(xué)植了多少棵時(shí)，他指著旁邊的第二位同學(xué)說(shuō)比他多植了兩棵；追問(wèn)第二位同學(xué)，他又說(shuō)比第三位同學(xué)多植了兩棵；如此追問(wèn)，都說(shuō)比另一位同學(xué)多植兩棵。最后問(wèn)到第五位同學(xué)時(shí)，他說(shuō)自己植了10棵。到底第一位同學(xué)植了多少棵樹(shù)？【分析】設(shè)第一位同學(xué)植樹(shù)的棵數(shù)為a1，欲求a1，需從第五位同學(xué)植樹(shù)的棵數(shù)a5入手，根據(jù)“多兩棵”這個(gè)

36、規(guī)律，按照一定順序逐步進(jìn)行推算： a5=10; a4=a5+2=12; a3=a4+2=14; a2=a3+2=16; a1=a2+2=18;本程序的遞推運(yùn)算可用如下圖示描述： 程序如下：#includeusing namespace std;int main三 int a=10; /以第五位同學(xué)的棵數(shù)為遞推的起始值 for (int i=4; i=1; -i) /還有4人，遞推計(jì)算4次 a+=2; /遞推運(yùn)算規(guī)律 cout The Num is a=3）。即：F1=0 （N=1） F2=1 （N=2） Fn=Fn-1 + Fn-2 （N=3）程序如下：#include#include usi

37、ng namespace std;int main三 int f0=0,f1=1,f2; int n; cinn; for (int i=3; i=n; +i) f2=f0+f1; f0=f1; f1=f2; printf(%dn,f2);return 0; -【遞推算法】1、猴子吃棗問(wèn)題：猴子摘了一堆棗，第一天吃了一半，還嫌不過(guò)癮，又吃了一個(gè)；第二天，又吃了剩下的一半零一個(gè)；以后每天如此。到第十天，猴子一看只剩下一個(gè)了。問(wèn)最初有多少個(gè)棗子？2、任何一個(gè)自然數(shù)的立方都可以寫(xiě)成一串連續(xù)奇數(shù)之和。如： 13=1 23=3+5=8 33=7+9+11=27 43=13+15+17+19=64 .編程

38、輸入N，求N3是由哪些奇數(shù)之和。3、樓梯有N級(jí)臺(tái)階，上樓可以一步上一階，也可以一步上二階。編一遞推程序，計(jì)算共有多少種不同走法？4、兔子在出生兩個(gè)月以后，就具有生殖后代的能力。假設(shè)一對(duì)兔子，每月都能生一對(duì)兔子，生出來(lái)的每一對(duì)小兔子，在出生兩個(gè)月后，也每月生一對(duì)兔子。那么，由一對(duì)剛出生的小兔子開(kāi)始，連續(xù)不斷地繁殖下去，在某個(gè)指定的月份有多少對(duì)兔子？5、骨牌鋪法： 有1n的一個(gè)長(zhǎng)方形，用一個(gè)11、12和13的骨牌鋪滿方格。例如當(dāng)n=3時(shí)為13的方格。此時(shí)用11、12和13的骨牌鋪滿方格，共有四種鋪法。如下圖：第三節(jié) 遞歸算法一、遞歸概念一、遞歸概念 當(dāng)函數(shù)的定義中，其內(nèi)部操作又直接或間接地出現(xiàn)對(duì)自

39、身的調(diào)用，則稱這樣的程序嵌套定義為遞歸定義。 遞歸通常把一個(gè)大型復(fù)雜的問(wèn)題層層轉(zhuǎn)化為一個(gè)與原問(wèn)題相似的規(guī)模較小的問(wèn)題來(lái)求解，遞歸策略只需少量的程序就可描述出解題過(guò)程所需要的多次重復(fù)計(jì)算，大大地減少了程序的代碼量。遞歸的能力在于用有限的語(yǔ)句來(lái)定義對(duì)象的無(wú)限集合。用遞歸思想寫(xiě)出的程序往往十分簡(jiǎn)潔易懂。例如，在數(shù)學(xué)上，所有偶數(shù)的集合可遞歸地定義為：0是一個(gè)偶數(shù)；一個(gè)偶數(shù)與2的和是一個(gè)偶數(shù)。 可見(jiàn)，僅需兩句話就能定義一個(gè)由無(wú)窮多個(gè)元素組成的集合。在程序中，遞歸是通過(guò)函數(shù)的調(diào)用來(lái)實(shí)現(xiàn)的。函數(shù)直接調(diào)用其自身，稱為直接遞歸；函數(shù)間接調(diào)用其自身，稱為間接遞歸。二、遞歸應(yīng)用二、遞歸應(yīng)用5 植樹(shù)節(jié)那天，有五位同學(xué)

40、參加了植樹(shù)活動(dòng)，他們完成植樹(shù)的棵數(shù)都不相同。問(wèn)第一位同學(xué)植了多少棵時(shí)，他指著旁邊的第二位同學(xué)說(shuō)比他多植了兩棵；追問(wèn)第二位同學(xué)，他又說(shuō)比第三位同學(xué)多植了兩棵；如此追問(wèn)，都說(shuō)比另一位同學(xué)多植兩棵，最后問(wèn)到第五位同學(xué)時(shí)，他說(shuō)自己植了10棵。問(wèn)第一位同學(xué)到底植了多少棵樹(shù)？【分析】把原問(wèn)題求第一位同學(xué)的植樹(shù)棵數(shù)a1轉(zhuǎn)化為a1=a2+2，即求a2；而求a2又轉(zhuǎn)化為a2=a3+2; a3=a4+2; a4=a5+2逐層轉(zhuǎn)化為求a2,a3,a4,a5且都采用與求a1相同的方法，最后的a5為已知值，用a5=10返回到上一層并代入計(jì)算出a4；又用a4的值代入上一層去求a3; ,如此,直到求出a1。因此：其中求ax

41、+1 又采用求ax 的方法。所以:定義一個(gè)處理問(wèn)題的子程序Num(x)，如果x 5就遞歸調(diào)用子程序Num(x+1);當(dāng)遞歸調(diào)用到達(dá)一定條件(x=5)，就直接執(zhí)行num=10，再執(zhí)行后繼語(yǔ)句，遇End返回到調(diào)用子程序的地方。最后返回到開(kāi)頭的原問(wèn)題，此時(shí)所得到的運(yùn)算結(jié)果就是原問(wèn)題Num(1)的答案。程序如下：#includeusing namespace std;int num(int);int main三 cout The Num is num(1)endl; return 0;int num(int x) if (x=5) return 10; /遞歸邊界 else return num(x+

42、1)+2; /遞歸式 利用全局變量的形式，也可以傳遞數(shù)據(jù)，采用另一種方式編寫(xiě)。 程序如下：#includeusing namespace std;int num(int);int a;/定義一個(gè)全局變量a，通過(guò)全局變量傳遞數(shù)值int main三 num(1);/主程序調(diào)用Num(1)求第1個(gè)人的棵數(shù) cout The Num is a1 ) X3 = X * X2 ( n 1 ) ( n 1 )因此將Xn 轉(zhuǎn)化為：x*xn-1，其中求Xn -1 又用求Xn 的方法進(jìn)行求解。定義子程序xn(n: int)求Xn ;如果n=1則遞歸調(diào)用xn(n-1) 求Xn1 ;當(dāng)遞歸調(diào)用到達(dá)n=0時(shí)終止調(diào)用,

43、然后執(zhí)行本“層”的后繼語(yǔ)句;遇到子程序中的end就結(jié)束本次的調(diào)用，返回到上一“層”調(diào)用語(yǔ)句的地方，并執(zhí)行其后繼語(yǔ)句;繼續(xù)執(zhí)行步驟，從調(diào)用中逐“層”返回，最后返回到主程序。 采用函數(shù)編寫(xiě)程序如下：#includeusing namespace std;int xn(int); int x;int main三 int n; cinxn; coutxn=xn(n)endl; return 0;int xn(int n) if (n=0) return 1; /遞歸邊界 else return x*xn(n-1); /遞歸式 采用全程變量編寫(xiě)程序如下：#includeusing namespace s

44、td;int tt,x; /利用全局變量tt傳遞結(jié)果int xn(int);int main三int n; cinxn; xn(n); coutxn=tt0時(shí)，x!=x*(x-1)！。 假設(shè)用函數(shù)Fac(x)表示x的階乘，當(dāng)x=3時(shí)，F(xiàn)ac(3)的求解方法可表示為：Fac(3)=3*fac(2)=3*2*Fac(1)=3*2*1*Fac(0)=3*2*1*1=6定義函數(shù)：int fac(int n) 如果n=0，則fac=1; 如果n0，則繼續(xù)調(diào)用函數(shù)fac=n*fac(n-1);返回主程序，打印fac(x)的結(jié)果。它的執(zhí)行流程如下圖所示：采用有參函數(shù)編寫(xiě)程序如下：#includeusing

45、namespace std;int fac(int );int main三int x;cinx;coutx!=fac(x)endl; /主程序調(diào)用fac(x) 求x !return 0;int fac(int n) /函數(shù)fac(n) 求n !return n=0 ? 1 : n*fac(n-1); /調(diào)用函數(shù)fac(n-1)遞歸求(n-1) !【說(shuō)明】： 這里出現(xiàn)了一個(gè)小東西，三元運(yùn)算符“?:”。a?b:c的含義是：如果a為真，則表達(dá)式的值是b，否則是c。所以n=0 ? 1 : n*fac(n-1)很好地表達(dá)了剛才的遞歸定義。 采用全程變量編寫(xiě)程序如下： #includeusing namespace std;int t;int fac(int);int main三int x;cinx;fac(x);coutt0，n0)【分析】求兩個(gè)數(shù)的最大公約數(shù)，可以用枚舉因子的方法，從兩者中較小的數(shù)枚舉到能被兩個(gè)數(shù)同時(shí)整除且是最大的約數(shù)的方法；也可以用輾轉(zhuǎn)相除法，這里采用遞歸實(shí)現(xiàn)輾轉(zhuǎn)相除算法： 求m除以n的余數(shù);如果余數(shù)不為0，則讓m=n，n=余數(shù)，重復(fù)步驟，即調(diào)用子程序;如果