第6章函數(shù)和遞歸(C版)

1、第六章 函數(shù)和遞歸算法第一節(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ù)例6.1 求：1!+2!+3!+10！#include using namespa

3、ce 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函數(shù)的形式 函數(shù)的形式從結(jié)構(gòu)上說(shuō)可以分為三種：無(wú)參函數(shù)、有參函數(shù)和空函數(shù)。它們的定義形式都相同。（1）無(wú)參函數(shù)無(wú)參函數(shù)顧名思義即為沒(méi)有參數(shù)傳遞的函數(shù)，無(wú)參函數(shù)一般不需要帶回函數(shù)值，所以函數(shù)類型說(shuō)明為void。（2）有參函數(shù)有參函數(shù)即有參數(shù)傳遞的函數(shù)，一般需要帶回函數(shù)值。例如int max(int x,int

4、y)函數(shù)。（3）空函數(shù)空函數(shù)即函數(shù)體只有一對(duì)花括號(hào)，花括號(hào)內(nèi)沒(méi)有任何語(yǔ)句的函數(shù)。例如，函數(shù)名（） 空函數(shù)不完成什么工作，只占據(jù)一個(gè)位置。在大型程序設(shè)計(jì)中，空函數(shù)用于擴(kuò)充函數(shù)功能。編寫(xiě)一個(gè)階乘的函數(shù)，我們給此函數(shù)取一個(gè)名字js。int js(int n) /函數(shù)名js，形參int n int s=1; / 中是函數(shù)的函數(shù)體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

5、()函數(shù)執(zhí)行結(jié)束，在主函數(shù)中js()值就是s的值。 在這里，函數(shù)的參數(shù)n是一個(gè)接口參數(shù)，說(shuō)得更明確點(diǎn)是入口參數(shù)。如果我們調(diào)用函數(shù)：js(3)，那么在程序里所有有n的地方，n被替代成3來(lái)計(jì)算。在這里，3就被稱為實(shí)參。又如：sqrt(4)，ln(5)，這里4，5叫實(shí)參。而ln(x)，sqrt(x)中的x，y叫形參。完整的程序如下：#includeusing namespace std;int js(int); /函數(shù)的聲明int main() int sum=0; for (int i=1; i=10; +i) sum+=js(i); /函數(shù)的調(diào)用 coutsum=sumendl;return 0

6、;int js(int n) /定義的函數(shù)體 int s=1; for (int i=1; i=n; +i) s*=i; return s; /函數(shù)的返回值二、函數(shù)的聲明和調(diào)用-【函數(shù)】1函數(shù)的聲明 調(diào)用函數(shù)之前先要聲明函數(shù)原型。在主調(diào)函數(shù)中，或所有函數(shù)定義之前，按如下形式聲明：類型說(shuō)明符 被調(diào)函數(shù)名（含類型說(shuō)明的形參表）； 如果是在所有函數(shù)定義之前聲明了函數(shù)原型，那么該函數(shù)原型在本程序文件中任何地方都有效，也就是說(shuō)在本程序文件中任何地方都可以依照該原型調(diào)用相應(yīng)的函數(shù)。如果是在某個(gè)主調(diào)函數(shù)內(nèi)部聲明了被調(diào)用函數(shù)原型，那么該原型就只能在這個(gè)函數(shù)內(nèi)部有效。 下面對(duì)js()函數(shù)原型聲明是合法的。 in

7、t js(int n); 也可以： int js(int);可以看到函數(shù)原型聲明與函數(shù)定義時(shí)的第一行類似，只多了一個(gè)分號(hào)，成為了一個(gè)聲明語(yǔ)句而已。2函數(shù)的調(diào)用聲明了函數(shù)原型之后，便可以按如下形式調(diào)用函數(shù)：函數(shù)名（實(shí)參列表） /例題中語(yǔ)句sum+=js(i);實(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函數(shù)的返回值 在組成函數(shù)體的各類語(yǔ)句中，值得注意的是返回語(yǔ)

8、句return。它的一般形式是：return（表達(dá)式）；/ 例題中語(yǔ)句return s; 其功能是把程序流程從被調(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ǔ)句，直接利用函數(shù)體的右花括號(hào)“”，作為沒(méi)有返回值的函數(shù)的返回。也可以有return語(yǔ)句，但return后沒(méi)有表達(dá)式。返回語(yǔ)句的另一種形式是：return；這時(shí)函數(shù)沒(méi)有返回值，而只把流程轉(zhuǎn)向主調(diào)函數(shù)。三、函數(shù)的傳值調(diào)用 函數(shù)傳值調(diào)用的特點(diǎn)是將調(diào)用函數(shù)的實(shí)參表中的實(shí)參值依次對(duì)應(yīng)地傳遞給被

9、調(diào)用函數(shù)的形參表中的形參。要求函數(shù)的實(shí)參與形參個(gè)數(shù)相等，并且類型相同。函數(shù)的調(diào)用過(guò)程實(shí)際上是對(duì)?？盏牟僮鬟^(guò)程，因?yàn)檎{(diào)用函數(shù)是使用?？臻g來(lái)保存信息的。函數(shù)在返回時(shí)，如果有返回值，則將它保存在臨時(shí)變量中。然后恢復(fù)主調(diào)函數(shù)的運(yùn)行狀態(tài)，釋放被調(diào)用函數(shù)的棧空間，按其返回地址返回到調(diào)用函數(shù)。 在C+語(yǔ)言中，函數(shù)調(diào)用方式分傳值調(diào)用和傳址調(diào)用。三、函數(shù)的傳值調(diào)用1、傳值調(diào)用這種調(diào)用方式是將實(shí)參的數(shù)據(jù)值傳遞給形參，即將實(shí)參值拷貝一個(gè)副本存放在被調(diào)用函數(shù)的棧區(qū)中。在被調(diào)用函數(shù)中，形參值可以改變，但不影響主調(diào)函數(shù)的實(shí)參值。參數(shù)傳遞方向只是從實(shí)參到形參，簡(jiǎn)稱單向值傳遞。舉個(gè)例子： #include using nam

10、espace 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中卻沒(méi)有交換。因?yàn)閟wap函數(shù)只是交換c,d兩變量副本的值，實(shí)參值沒(méi)有改變，并沒(méi)有達(dá)到交換的目的。三、函數(shù)的傳值調(diào)用2、傳址調(diào)用 這種調(diào)用方式是將實(shí)參變量的地址值傳遞給形參，這時(shí)形參實(shí)是指針，即讓形參的指針指向?qū)崊⒌刂?，這里不再是將實(shí)參拷貝一個(gè)副本給形參，而是讓形參直接指向?qū)崊?，這就

11、提供了一種可以改變實(shí)參變量的值的方法?，F(xiàn)在用傳址調(diào)用來(lái)實(shí)現(xiàn)swap： #include using namespace std; void swap(int &a,int &b) /定義swap()函數(shù)，形參是傳址調(diào)用 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ù)為傳址調(diào)用，&a是指實(shí)參變量的地址值傳遞給形參，所以，在函數(shù)swap中修改a,b的值相當(dāng)于在主函數(shù)main中修改c,d的值。四、函數(shù)的應(yīng)用舉例-【函數(shù)】例6

12、.2 計(jì)算組合數(shù)C(m,n)的值(n=m=10)。 【分析】組合數(shù)C(m,n)可以理解為從m個(gè)數(shù)中任意取出n個(gè)數(shù)的所有情況數(shù)。求這個(gè)數(shù)值，有一個(gè)經(jīng)典的計(jì)算方法：C(m,n)=m!/(m-n)!n!)。程序如下：#includeusing namespace std;int fac(int x); /階乘函數(shù)的聲明int main()int m,n;scanf(%d%d,&m,&n);printf(%d,fac(m)/(fac(m-n)*fac(n); /階乘函數(shù)的調(diào)用int fac(int x) /定義階乘函數(shù)int s=1;for (int i=1; i=x; i+) s*=i;return

13、 s; /階乘函數(shù)的值返回例6.3 計(jì)算如圖多邊形的面積。從圖中可以看出，五邊形的面積是三個(gè)三角形面積之和。程序如下：#include#include /使用printf和scanf語(yǔ)句，調(diào)用cstdio庫(kù)#include using namespace std;double area(double,double,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(b

14、3,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.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,

15、int);int main() int a,b; coutinput n,dab; if (check(a,b)=true) 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 用冒泡法對(duì)數(shù)組元素按由小到大排序（數(shù)組作為函數(shù)參數(shù)）#includeusing namespace std;void bubble(int,int); /相當(dāng)于void bubble

16、(int a,int n);int main() /大數(shù)組應(yīng)開(kāi)為全局變量 int array10=11,4,55,6,77,8,9,0,7,1; cout排序前 ; for (int i=0; i10; +i) coutarrayi,; coutendl;bubble(array,10); cout排序后 ;for (int i=0; i10; +i) coutarrayi,; coutendl; return 0; void bubble(int a,int n) for (int i=1; in; +i) for (int j=0; jaj+1) /判斷并交換變量 int temp=aj;

17、 aj=aj+1; aj+1=temp; 在前面我們已經(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ì)改變。五、全程變量、局部變量及它們的作用域 在函數(shù)外部定義的變量稱為外部變量或全局變量，在函數(shù)內(nèi)部定義的變量稱為內(nèi)部變量或局部變量。1全局變量 定義在函數(shù)外部沒(méi)有被花括號(hào)括起來(lái)的變量稱為全局變量，全局變量的作用域是從變量定義的位置開(kāi)始到文件結(jié)束。由于全局變量是在函數(shù)外部定義的，因此對(duì)所有函數(shù)而言都是外部的，可以在文件中位于全局變量定義后面的任何函

18、數(shù)中使用。例6.6 輸入兩個(gè)正整數(shù)，編程計(jì)算兩個(gè)數(shù)的最小公倍數(shù)。程序如下：#includeusing namespace std;int x,y; /定義全局變量x,yint gcd(int x,int y) /求最大公約數(shù)，形參x,y是局部變量int r=x%y; /r是局部變量，局部變量x,y屏蔽全局變量while(r!=0)x=y;y=r;r=x%y;return y;int lcm() /求最小公倍數(shù)return x*y/gcd(x,y); /這里x,y是全局變量int main() /gcd和lcm在main()前，函數(shù)不必聲明cinxy; /這里x,y是全局變量coutlcm()e

19、ndl;return 0;運(yùn)行結(jié)果： 輸入: 12 18 輸出: 36使用全局變量的說(shuō)明：在一個(gè)函數(shù)內(nèi)部，既可以使用本函數(shù)定義的局部變量，也可以使用在此函數(shù)前定義的全局變量。全局變量的作用是使得函數(shù)間多了一種傳遞信息的方式。如果在一個(gè)程序中多個(gè)函數(shù)都要對(duì)同一個(gè)變量進(jìn)行處理，即共享，就可以將這個(gè)變量定義成全局變量，使用非常方便，但副作用也不可低估。過(guò)多地使用全局變量，會(huì)增加調(diào)試難度。因?yàn)槎鄠€(gè)函數(shù)都能改變?nèi)肿兞康闹?，不易判斷某個(gè)時(shí)刻全局變量的值。過(guò)多地使用全局變量，會(huì)降低程序的通用性。如果將一個(gè)函數(shù)移植到另一個(gè)程序中，需要將全局變量一起移植過(guò)去，同時(shí)還有可能出現(xiàn)重名問(wèn)題。全局變量在程序執(zhí)行的全過(guò)

20、程中一直占用內(nèi)存單元。全局變量在定義時(shí)若沒(méi)有賦初值，其默認(rèn)值為0。2局部變量局部變量的作用域是在定義該變量的函數(shù)內(nèi)部，換句話說(shuō)，局部變量只在定義它的函數(shù)內(nèi)有效。函數(shù)的形參也是局部變量。局部變量的存儲(chǔ)空間是臨時(shí)分配的，當(dāng)函數(shù)執(zhí)行完畢，局部變量的空間就被釋放，其中的值無(wú)法保留到下次使用。 由于局部變量的作用域僅局限于本函數(shù)內(nèi)部，所以，在不同的函數(shù)中變量名可以相同，它們分別代表不同的對(duì)象，在內(nèi)存中占據(jù)不同的內(nèi)存單元，互不干擾。一個(gè)局部變量和一個(gè)全局變量是可以重名的，在相同的作用域內(nèi)局部變量有效時(shí)全局變量無(wú)效。即局部變量可以屏蔽全局變量(4)在代碼塊中定義的變量的存在時(shí)間和作用域?qū)⒈幌拗圃谠摯a塊中。

21、如for(int i;i=n;i+) sum+=i中的i是在該for循環(huán)語(yǔ)句中定義的，存在時(shí)間和作用域只能被限制在該for循環(huán)語(yǔ)句中。 (5)這里需要強(qiáng)調(diào)的是，主函數(shù)main中定義的變量也是局部變量，這一點(diǎn)與其他程序設(shè)計(jì)語(yǔ)言不同。(6) 全局變量數(shù)組初始全部為0，局部變量值是隨機(jī)的，要初始化初值，局部變量受?？臻g大小限制，大數(shù)組需要注意。通俗說(shuō)，局部變量的數(shù)組不能開(kāi)很大，全局變量隨便。六、函數(shù)的綜合應(yīng)用-【函數(shù)】 例6.7 寫(xiě)一個(gè)判斷素?cái)?shù)的函數(shù)，輸入一個(gè)數(shù)，判斷它是否是素?cái)?shù)，是輸出yes，不是輸出no?！痉治觥繉?duì)于任意整數(shù)i，根據(jù)素?cái)?shù)定義，我們從2開(kāi)始，到sqrt(i)，找i的第一個(gè)約數(shù)，若找

22、到第一個(gè)約數(shù)，則i必然不是素?cái)?shù)。程序如下：#include#includeint prime(int x); /對(duì)于函數(shù)的聲明int main()int n;scanf(%d,&n);if (prime(n) printf(%sn,yes);else printf(%sn,no);return 0;int prime(int x) /判斷x是否素?cái)?shù)的函數(shù)int j;if (x=2) return 1;j=2; while(j=sqrt(x) & x%j!=0) j+;if (x%j = 0) return 0;else return 1;例6.8 編程輸入十進(jìn)制整數(shù)N（N：-327673276

23、7），請(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);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ù) T

24、urnData(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è)為形參即可。例6.9 編寫(xiě)一個(gè)給一個(gè)分?jǐn)?shù)約分的程序。 程序如下：#include#includeusing namespace std;void common(int x,int y);int

25、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í)】1.求正整數(shù)2和100之間的完全數(shù)。完全數(shù)：因子之和等于它本身的自然數(shù)，如6=1+2+32.編程求2n(n為大于2的正整數(shù))中有多少個(gè)素?cái)?shù)。3已知 m=，輸入a,b,c，求m。

26、把求三個(gè)數(shù)的最大數(shù)max(x,y,z)分別定義成函數(shù)和過(guò)程來(lái)做。4.如果一個(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ì)“親和數(shù)” 。求最小的一對(duì)親和數(shù)(ab)。6.如果一個(gè)數(shù)從左邊讀和從右邊讀都是同一個(gè)數(shù)，就稱為回文數(shù)。例如6886就是一個(gè)回文數(shù)，丘出所有的既是回文數(shù)又是素?cái)?shù)的三位數(shù)。7根據(jù)公式arctanx(x)=x-x3/3+x5/5-x7/7+和=6 arctanx()

27、，定義函數(shù)arctanx(x)，求當(dāng)最后一項(xiàng)小于10-6時(shí)的值。8.哥德巴赫猜想的命題之一是:大于6 的偶數(shù)等于兩個(gè)素?cái)?shù)之和。編程將6100所有偶數(shù)表示成兩個(gè)素?cái)?shù)之和?！旧蠙C(jī)練習(xí)】1.簡(jiǎn)單算術(shù)表達(dá)式求值【1.12編程基礎(chǔ)之函數(shù)與過(guò)程抽象01】 兩位正整數(shù)的簡(jiǎn)單算術(shù)運(yùn)算（只考慮整數(shù)運(yùn)算），算術(shù)運(yùn)算為： +，加法運(yùn)算； -，減法運(yùn)算； *，乘法運(yùn)算； /，整除運(yùn)算； %，取余運(yùn)算。 算術(shù)表達(dá)式的格式為（運(yùn)算符前后可能有空格）： 運(yùn)算數(shù) 運(yùn)算符 運(yùn)算數(shù) 請(qǐng)輸出相應(yīng)的結(jié)果。輸入:一行算術(shù)表達(dá)式。輸出:整型算數(shù)運(yùn)算的結(jié)果（結(jié)果值不一定為2位數(shù)，可能多于2位或少于2位）。樣例輸入： 32+64樣例輸出：

28、96【上機(jī)練習(xí)】2.短信計(jì)費(fèi)【1.12編程基礎(chǔ)之函數(shù)與過(guò)程抽象02】 用手機(jī)發(fā)短信，一條短信資費(fèi)為0.1元，但限定一條短信的內(nèi)容在70個(gè)字以內(nèi)(包括70個(gè)字）。如果你一次所發(fā)送的短信超過(guò)了70個(gè)字，則會(huì)按照每70個(gè)字一條短信的限制把它分割成多條短信發(fā)送。假設(shè)已經(jīng)知道你當(dāng)月所發(fā)送的短信的字?jǐn)?shù)，試統(tǒng)計(jì)一下你當(dāng)月短信的總資費(fèi)。輸入:第一行是整數(shù)n，表示當(dāng)月發(fā)送短信的總次數(shù)，接著n行每行一個(gè)整數(shù)，表示每次短信的字?jǐn)?shù)。輸出:輸出一行，當(dāng)月短信總資費(fèi)，單位為元，精確到小數(shù)點(diǎn)后1位。樣例輸入: 樣例輸出: 10 1.3 39 49 42 61 44 147 42 72 35 46 【上機(jī)練習(xí)】3.甲流病人初

29、篩【1.12編程基礎(chǔ)之函數(shù)與過(guò)程抽象03】 目前正是甲流盛行時(shí)期，為了更好地進(jìn)行分流治療，醫(yī)院在掛號(hào)時(shí)要求對(duì)病人的體溫和咳嗽情況進(jìn)行檢查，對(duì)于體溫超過(guò)37.5度（含等于37.5度）并且咳嗽的病人初步判定為甲流病人（初篩）?，F(xiàn)需要統(tǒng)計(jì)某天前來(lái)掛號(hào)就診的病人中有多少人被初篩為甲流病人。輸入: 第一行是某天前來(lái)掛號(hào)就診的病人數(shù)n。(n200) 其后有n行，每行是病人的信息，包括三個(gè)信息：姓名（字符串，不含空格，最多8個(gè)字符）、體溫（float）、是否咳嗽（整數(shù)，1表示咳嗽，0表示不咳嗽）。每行三個(gè)信息之間以一個(gè)空格分開(kāi)。輸出: 按輸入順序依次輸出所有被篩選為甲流的病人的姓名，每個(gè)名字占一行。之后在輸

30、出一行，表示被篩選為甲流的病人數(shù)量。樣例輸入: 5 Zhang 38.3 0 Li 37.5 1 Wang 37.1 1 Zhao 39.0 1 Liu 38.2 1樣例輸出: Li Zhao Liu 3【上機(jī)練習(xí)】4.統(tǒng)計(jì)單詞數(shù)【1.12編程基礎(chǔ)之函數(shù)與過(guò)程抽象05】Noip2011普及組第2題 一般的文本編輯器都有查找單詞的功能，該功能可以快速定位特定單詞在文章中的位置，有的還能統(tǒng)計(jì)出特定單詞在文章中出現(xiàn)的次數(shù)。 現(xiàn)在，請(qǐng)你編程實(shí)現(xiàn)這一功能，具體要求是：給定一個(gè)單詞，請(qǐng)你輸出它在給定的文章中出現(xiàn)的次數(shù)和第一次出現(xiàn)的位置。注意：匹配單詞時(shí)，不區(qū)分大小寫(xiě)，但要求完全匹配，即給定單詞必須與文章中

31、的某一獨(dú)立單詞在不區(qū)分大小寫(xiě)的情況下完全相同（參見(jiàn)樣例1），如果給定單詞僅是文章中某一單詞的一部分則不算匹配（參見(jiàn)樣例2）。輸入: 第 1 行為一個(gè)字符串，其中只含字母，表示給定單詞； 第 2 行為一個(gè)字符串，其中只可能包含字母和空格，表示給定的文章。輸出: 只有一行，如果在文章中找到給定單詞則輸出兩個(gè)整數(shù)，兩個(gè)整數(shù)之間用一個(gè)空格隔開(kāi)，分別是單詞在文章中出現(xiàn)的次數(shù)和第一次出現(xiàn)的位置（即在文章中第一次出現(xiàn)時(shí)，單詞首字母在文章中的位置，位置從0開(kāi)始）；如果單詞在文章中沒(méi)有出現(xiàn)，則直接輸出一個(gè)整數(shù)-1。樣例輸入:樣例 #1：Toto be or not to be is a question樣例 #

32、2：toDid the Ottoman Empire lose its power at that time樣例輸出:樣例 #1：2 0樣例 #2：-1【上機(jī)練習(xí)】5.機(jī)器翻譯【1.12編程基礎(chǔ)之函數(shù)與過(guò)程抽象07】Noip2010提高組第1題 小晨的電腦上安裝了一個(gè)機(jī)器翻譯軟件，他經(jīng)常用這個(gè)軟件來(lái)翻譯英語(yǔ)文章。 這個(gè)翻譯軟件的原理很簡(jiǎn)單，它只是從頭到尾，依次將每個(gè)英文單詞用對(duì)應(yīng)的中文含義來(lái)替換。對(duì)于每個(gè)英文單詞，軟件會(huì)先在內(nèi)存中查找這個(gè)單詞的中文含義，如果內(nèi)存中有，軟件就會(huì)用它進(jìn)行翻譯；如果內(nèi)存中沒(méi)有，軟件就會(huì)在外存中的詞典內(nèi)查找，查出單詞的中文含義然后翻譯，并將這個(gè)單詞和譯義放入內(nèi)存，以備

33、后續(xù)的查找和翻譯。 假設(shè)內(nèi)存中有M個(gè)單元，每單元能存放一個(gè)單詞和譯義。每當(dāng)軟件將一個(gè)新單詞存入內(nèi)存前，如果當(dāng)前內(nèi)存中已存入的單詞數(shù)不超過(guò)M1，軟件會(huì)將新單詞存入一個(gè)未使用的內(nèi)存單元；若內(nèi)存中已存入M 個(gè)單詞，軟件會(huì)清空最早進(jìn)入內(nèi)存的那個(gè)單詞，騰出單元來(lái)，存放新單詞。 假設(shè)一篇英語(yǔ)文章的長(zhǎng)度為N個(gè)單詞。給定這篇待譯文章，翻譯軟件需要去外存查找多少次詞典？假設(shè)在翻譯開(kāi)始前，內(nèi)存中沒(méi)有任何單詞。輸入: 輸入文件共2行。每行中兩個(gè)數(shù)之間用一個(gè)空格隔開(kāi)。 第一行為兩個(gè)正整數(shù)M和N，代表內(nèi)存容量和文章的長(zhǎng)度。 第二行為N個(gè)非負(fù)整數(shù)，按照文章的順序，每個(gè)數(shù)（大小不超過(guò)1000）代表一個(gè)英文單詞。文章中兩個(gè)單

34、詞是同一個(gè)單詞，當(dāng)且僅當(dāng)它們對(duì)應(yīng)的非負(fù)整數(shù)相同。 【上機(jī)練習(xí)】輸出: 共1行，包含一個(gè)整數(shù)，為軟件需要查詞典的次數(shù)。樣例輸入:樣例 #1：3 71 2 1 5 4 4 1樣例 #2：2 108 824 11 78 11 78 11 78 8 264樣例輸出:樣例 #1：5樣例 #2：6提示: 輸入輸出樣例 1 說(shuō)明： 整個(gè)查字典過(guò)程如下：每行表示一個(gè)單詞的翻譯，冒號(hào)前為本次翻譯后的內(nèi)存狀況： 空：內(nèi)存初始狀態(tài)為空。 1 1：查找單詞1并調(diào)入內(nèi)存。 2 1 2：查找單詞2并調(diào)入內(nèi)存。 3 1 2：在內(nèi)存中找到單詞1。 4 1 2 5：查找單詞5并調(diào)入內(nèi)存。 5 2 5 4：查找單詞4并調(diào)入內(nèi)存替

35、代單詞1。 6 2 5 4：在內(nèi)存中找到單詞4。 7 5 4 1：查找單詞1并調(diào)入內(nèi)存替代單詞2。 共計(jì)查了5 次詞典。【上機(jī)練習(xí)】6.Vigenre密碼【1.12編程基礎(chǔ)之函數(shù)與過(guò)程抽象08】Noip2012提高組第1題 16世紀(jì)法國(guó)外交家Blaise de Vigenre設(shè)計(jì)了一種多表密碼加密算法Vigenre密碼。Vigenre密碼的加密解密算法簡(jiǎn)單易用，且破譯難度比較高，曾在美國(guó)南北戰(zhàn)爭(zhēng)中為南軍所廣泛使用。 在密碼學(xué)中，我們稱需要加密的信息為明文，用M表示；稱加密后的信息為密文，用C表示；而密鑰是一種參數(shù)，是將明文轉(zhuǎn)換為密文或?qū)⒚芪霓D(zhuǎn)換為明文的算法中輸入的數(shù)據(jù)，記為k。 在Vigenr

36、e密碼中，密鑰k是一個(gè)字母串，k=k1k2kn。當(dāng)明文M=m1m2mn時(shí)，得到的密文C=c1c2cn，其中ci=miki，運(yùn)算的規(guī)則如下表所示： Vigenre加密在操作時(shí)需要注意： 1.運(yùn)算忽略參與運(yùn)算的字母的大小寫(xiě)，并保持字母在明文M中的大小寫(xiě)形式； 2.當(dāng)明文M的長(zhǎng)度大于密鑰k的長(zhǎng)度時(shí)，將密鑰k重復(fù)使用。 例如，明文M=Helloworld，密鑰k=abc時(shí)，密文C=Hfnlpyosnd。 明文 H e l l o w o r l d 密鑰 a b c a b c a b c a 密文 H f n l p y o s n d 【上機(jī)練習(xí)】輸入: 第一行為一個(gè)字符串，表示密鑰k，長(zhǎng)度不超過(guò)

37、100，其中僅包含大小寫(xiě)字母。第二行 為一個(gè)字符串，表示經(jīng)加密后的密文，長(zhǎng)度不超過(guò)1000，其中僅包含大小寫(xiě)字母。 對(duì)于100%的數(shù)據(jù)，輸入的密鑰的長(zhǎng)度不超過(guò)100，輸入的密文的長(zhǎng)度不超過(guò)1000，且都僅包含英文字母。輸出: 輸出共1行，一個(gè)字符串，表示輸入密鑰和密文所對(duì)應(yīng)的明文。樣例輸入: CompleteVictory Yvqgpxaimmklongnzfwpvxmniytm樣例輸出: Wherethereisawillthereisaway【上機(jī)練習(xí)】7.素?cái)?shù)對(duì)【1.12編程基礎(chǔ)之函數(shù)與過(guò)程抽象10】 兩個(gè)相差為2的素?cái)?shù)稱為素?cái)?shù)對(duì)，如5和7，17和19等，本題目要求找出所有兩個(gè)數(shù)均不大于

38、n的素?cái)?shù)對(duì)。輸入: 一個(gè)正整數(shù)n。1=n=10000。輸出: 所有小于等于n的素?cái)?shù)對(duì)。每對(duì)素?cái)?shù)對(duì)輸出一行，中間用單個(gè)空格隔開(kāi)。若沒(méi)有找到任何素?cái)?shù)對(duì)，輸出empty。樣例輸入: 100樣例輸出: 3 5 5 7 11 13 17 19 29 31 41 43 59 61 71 73【上機(jī)練習(xí)】8我家的門(mén)牌號(hào)【小學(xué)奧數(shù)7649】 我家住在一條短胡同里，這條胡同的門(mén)牌號(hào)從1開(kāi)始順序編號(hào)。 若其余各家的門(mén)牌號(hào)之和減去我家門(mén)牌號(hào)的兩倍，恰好等于n，求我家的門(mén)牌號(hào)及總共有多少家。數(shù)據(jù)保證有唯一解。輸入: 一個(gè)正整數(shù)n。n100000。輸出: 一行，包含兩個(gè)正整數(shù)，分別是我家的門(mén)牌號(hào)及總共有多少家，中間用單

39、個(gè)空格隔開(kāi)。樣例輸入: 100樣例輸出: 10 15【上機(jī)練習(xí)】9質(zhì)數(shù)的和與積【小學(xué)奧數(shù)7827】 兩個(gè)質(zhì)數(shù)的和是S，它們的積最大是多少？輸入: 一個(gè)不大于10000的正整數(shù)S，為兩個(gè)質(zhì)數(shù)的和。輸出: 一個(gè)整數(shù)，為兩個(gè)質(zhì)數(shù)的最大乘積。數(shù)據(jù)保證有解。樣例輸入: 50樣例輸出: 589【上機(jī)練習(xí)】10.單詞替換【1.7編程基礎(chǔ)之字符串17】 輸入一個(gè)字符串，以回車結(jié)束（字符串長(zhǎng)度=100）。該字符串由若干個(gè)單詞組成，單詞之間用一個(gè)空格隔開(kāi)，所有單詞區(qū)分大小寫(xiě)?，F(xiàn)需要將其中的某個(gè)單詞替換成另一個(gè)單詞，并輸出替換之后的字符串。輸入: 第1行是包含多個(gè)單詞的字符串 s； 第2行是待替換的單詞a(長(zhǎng)度 =

40、 100)； 第3行是a將被替換的單詞b(長(zhǎng)度 = 100)。 s,a,b最前面和最后面都沒(méi)有空格。輸出: 輸出只有 1 行，將s中所有單詞a替換成b之后的字符串。樣例輸入: You want someone to help you You I樣例輸出: I want someone to help you【上機(jī)練習(xí)】11.笨小猴【1.9編程基礎(chǔ)之順序查找06】Noip2008提高組第1題 笨小猴的詞匯量很小，所以每次做英語(yǔ)選擇題的時(shí)候都很頭疼。但是他找到了一種方法，經(jīng)試驗(yàn)證明，用這種方法去選擇選項(xiàng)的時(shí)候選對(duì)的幾率非常大！ 這種方法的具體描述如下：假設(shè)maxn是單詞中出現(xiàn)次數(shù)最多的字母的出現(xiàn)次

41、數(shù)，minn是單詞中出現(xiàn)次數(shù)最少的字母的出現(xiàn)次數(shù)，如果maxn-minn是一個(gè)質(zhì)數(shù)，那么笨小猴就認(rèn)為這是個(gè)Lucky Word，這樣的單詞很可能就是正確的答案。 輸入: 只有一行，是一個(gè)單詞，其中只可能出現(xiàn)小寫(xiě)字母，并且長(zhǎng)度小于100。輸出: 共兩行，第一行是一個(gè)字符串，假設(shè)輸入的的單詞是Lucky Word，那么輸出“Lucky Word”，否則輸出“No Answer”； 第二行是一個(gè)整數(shù)，如果輸入單詞是Lucky Word，輸出maxn-minn的值，否則輸出0。樣例輸入: 樣例輸出:樣例 #1： 樣例 #1： 樣例 #2： error Lucky Word No Answer樣例 #2

42、： 2 0olympic【上機(jī)練習(xí)】12.素?cái)?shù)回文數(shù)的個(gè)數(shù)【1.13編程基礎(chǔ)之綜合應(yīng)用05】 求11到n之間（包括n），既是素?cái)?shù)又是回文數(shù)的整數(shù)有多少個(gè)。輸入: 一個(gè)大于11小于1000的整數(shù)n。輸出: 11到n之間的素?cái)?shù)回文數(shù)個(gè)數(shù)。樣例輸入: 23樣例輸出: 1提示: 回文數(shù)指左右對(duì)稱的數(shù)，如：292，333?！旧蠙C(jī)練習(xí)】13.判決素?cái)?shù)個(gè)數(shù)【1.13編程基礎(chǔ)之綜合應(yīng)用10】 輸入兩個(gè)整數(shù)X和Y，輸出兩者之間的素?cái)?shù)個(gè)數(shù)（包括X和Y）。輸入: 兩個(gè)整數(shù)X和Y（1 = X,Y = 105）。輸出: 輸出一個(gè)整數(shù)，表示X，Y之間的素?cái)?shù)個(gè)數(shù)（包括X和Y）。樣例輸入: 1 100樣例輸出: 25【上機(jī)練

43、習(xí)】14.最大質(zhì)因子序列【1.13編程基礎(chǔ)之綜合應(yīng)用21】 任意輸入兩個(gè)正整數(shù)m,n(1mn=5000)，依次輸出m到n之間每個(gè)數(shù)的最大質(zhì)因子(包括m和n；如果某個(gè)數(shù)本身是質(zhì)數(shù)，則輸出這個(gè)數(shù)自身)。輸入: 一行，包含兩個(gè)正整數(shù)m和n，其間以單個(gè)空格間隔。輸出: 一行，每個(gè)整數(shù)的最大質(zhì)因子，以逗號(hào)間隔。樣例輸入: 5 10樣例輸出: 5,3,7,2,3,5【上機(jī)練習(xí)】15.區(qū)間內(nèi)的真素?cái)?shù)【1.13編程基礎(chǔ)之綜合應(yīng)用23】 找出正整數(shù)M和N之間（N不小于M）的所有真素?cái)?shù)。 真素?cái)?shù)的定義：如果一個(gè)正整數(shù)P為素?cái)?shù)，且其反序也為素?cái)?shù)，那么P就為真素?cái)?shù)。 例如，11，13均為真素?cái)?shù)，因?yàn)?1的反序還是為1

44、1，13的反序?yàn)?1也為素?cái)?shù)。輸入: 輸入兩個(gè)數(shù)M和N，空格間隔，1=M=N=100000。輸出: 按從小到大輸出M和N之間（包括M和N）的真素?cái)?shù)，逗號(hào)間隔。如果之間沒(méi)有真素?cái)?shù)，則輸出No。樣例輸入: 10 35樣例輸出: 11,13,17,31【上機(jī)練習(xí)】16. 二進(jìn)制分類【1.13編程基礎(chǔ)之綜合應(yīng)用36】 若將一個(gè)正整數(shù)化為二進(jìn)制數(shù)，在此二進(jìn)制數(shù)中，我們將數(shù)字1的個(gè)數(shù)多于數(shù)字0的個(gè)數(shù)的這類二進(jìn)制數(shù)稱為A類數(shù)，否則就稱其為B類數(shù)。例如： (13)10=(1101)2，其中1的個(gè)數(shù)為3，0的個(gè)數(shù)為1，則稱此數(shù)為A類數(shù)； (10)10=(1010)2，其中1的個(gè)數(shù)為2，0的個(gè)數(shù)也為2，稱此數(shù)為B

45、類數(shù)； (24)10=(11000)2，其中1的個(gè)數(shù)為2，0的個(gè)數(shù)為3，則稱此數(shù)為B類數(shù)； 程序要求：求出11000之中（包括1與1000），全部A、B兩類數(shù)的個(gè)數(shù)。輸入: 無(wú)。輸出: 一行，包含兩個(gè)整數(shù)，分別是A類數(shù)和B類數(shù)的個(gè)數(shù)，中間用單個(gè)空格隔開(kāi)?！旧蠙C(jī)練習(xí)】17.確定進(jìn)制【1.13編程基礎(chǔ)之綜合應(yīng)用34】 6*9=42對(duì)于十進(jìn)制來(lái)說(shuō)是錯(cuò)誤的，但是對(duì)于13進(jìn)制來(lái)說(shuō)是正確的。即, 6(13)* 9(13)= 42(13)， 而 42(13)=4*131+2*130=54(10)。 你的任務(wù)是寫(xiě)一段程序，讀入三個(gè)整數(shù)p、q和 r，然后確定一個(gè)進(jìn)制 B(2=B=16) 使得 p * q = r

46、。 如果 B 有很多選擇, 輸出最小的一個(gè)。 例如：p=11, q=11, r=121.則有11(3)* 11(3)= 121(3)因?yàn)?11(3)= 1 * 31+ 1 * 30= 4(10)和121(3)=1*32+2*31+1*30=16(10)。對(duì)于進(jìn)制 10，同樣有11(10)* 11(10)= 121(10)。這種情況下，應(yīng)該輸出 3。如果沒(méi)有合適的進(jìn)制，則輸出 0。輸入: 一行，包含三個(gè)整數(shù)p、q、r。 p、q、r的所有位都是數(shù)字，并且1 = p、q、r 1 ) x3 = x * x2 ( n 1 ) ( n 1 )因此將xn 轉(zhuǎn)化為：x*xn-1，其中求xn-1 又用求xn 的

47、方法進(jìn)行求解。定義子程序xn(int n)求Xn ;如果n=1則遞歸調(diào)用xn(n-1) 求xn1 ;當(dāng)遞歸調(diào)用到達(dá)n=0時(shí)終止調(diào)用, 然后執(zhí)行本“層”的后繼語(yǔ)句;遇到子程序運(yùn)行完，就結(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; /遞歸邊界

48、 else return x*xn(n-1); /遞歸式 采用全程變量編寫(xiě)程序如下：#includeusing namespace std;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=

49、n*fac(n-1);返回主程序，打印fac(x)的結(jié)果。它的執(zhí)行流程如下圖所示：采用有參函數(shù)編寫(xiě)程序如下：#includeusing 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。

50、所以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) 【方法1】求兩個(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)用子程序; 如果余數(shù)為0，則終止調(diào)用子程序; 輸出此時(shí)的n值。 #includeusin

51、g namespace std;int gcd(int,int);int main() int m,n; cinmn; cout gcd=gcd(m,n)endl; return 0;int gcd(int m,int n) return m%n=0?n:gcd(n,m%n); 【方法2】二進(jìn)制最大公約數(shù)算法(1)遞歸終止條件：gcd(m,m)=m。(2)遞歸關(guān)系式： mn時(shí)：gcd(m,n)=gcd(n,m) m為偶數(shù)，n為偶數(shù)：gcd(m,n)=2*gcd(m/2,n/2) m為偶數(shù)，n為奇數(shù)：gcd(m,n)=gcd(m/2,n) m為奇數(shù)，n為偶數(shù)：gcd(m,n)=gcd(m,n/2) m為奇數(shù)，n為奇數(shù)：gcd(m,n)=gcd(n,m-n) 該方法和方法1相比更適合求高精度