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

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

2、續(xù)分解，直到每個子問題都是一個具有獨立任務的模塊。這樣編制的程序結構清晰，邏輯關系明確，無論是編寫、閱讀、調試還是修改，都會帶來極大的好處。 在一個程序中可以只有主程序而沒有子程序(本章以前都是如此)，但不能沒有主程序，也就是說不能單獨執(zhí)行子程序。 在此之前，我們曾經介紹并使用了C+提供的各種標準函數，如abs(),sqrt()等等，這些系統(tǒng)提供的函數為我們編寫程序提供了很大的方便。比如：求sin(1)+ sin(2)+sin(100)的值。但這些函數只是常用的基本函數，編程時經常需要自定義一些函數。第一節(jié) 函數例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; 該函數返回值是整型，有兩個整型的形參，用來接受實參傳遞的兩個數據，函數體內的語句是求兩個數中的較大者并將其返回主調函數。3函數的形式 函數的形式從結構上說可以分為三種：無參函數、有參函數和空函數。它們的定義形式都相同。（1）無參函數無參函數顧名思義即為沒有參數傳遞的函數，無參函數一般不需要帶回函數值，所以函數類型說明為void。（2）有參函數有參函數即有參數傳遞的函數，一般需要帶回函數值。例如int max(int x,int

4、y)函數。（3）空函數空函數即函數體只有一對花括號，花括號內沒有任何語句的函數。例如，函數名（） 空函數不完成什么工作，只占據一個位置。在大型程序設計中，空函數用于擴充函數功能。編寫一個階乘的函數，我們給此函數取一個名字js。int js(int n) /函數名js，形參int n int s=1; / 中是函數的函數體for (int i=1; i=n; +i)s*=i;return s; 在本例中，函數名叫js，只有一個int型的自變量n，函數js屬int型。在本函數中，要用到兩個變量i，s。在函數體中，是一個求階乘的語句，n的階乘的值在s中，最后由return語句將計算結果s值帶回，js

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

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

7、t js(int n); 也可以： int js(int);可以看到函數原型聲明與函數定義時的第一行類似，只多了一個分號，成為了一個聲明語句而已。2函數的調用聲明了函數原型之后，便可以按如下形式調用函數：函數名（實參列表） /例題中語句sum+=js(i);實參列表中應給出與函數原型形參個數相同、類型相符的實參。在主調函數中的參數稱為實參，實參一般應具有確定的值。實參可以是常量、表達式，也可以是已有確定值的變量，數組或指針名。函數調用可以作為一條語句，這時函數可以沒有返回值。函數調用也可以出現在表達式中，這時就必須有一個明確的返回值。3函數的返回值 在組成函數體的各類語句中，值得注意的是返回語

8、句return。它的一般形式是：return（表達式）；/ 例題中語句return s; 其功能是把程序流程從被調函數轉向主調函數并把表達式的值帶回主調函數，實現函數的返回。所以，在圓括號表達式的值實際上就是該函數的返回值。其返回值的類型即為它所在函數的函數類型。當一個函數沒有返回值時，函數中可以沒有return語句，直接利用函數體的右花括號“”，作為沒有返回值的函數的返回。也可以有return語句，但return后沒有表達式。返回語句的另一種形式是：return；這時函數沒有返回值，而只把流程轉向主調函數。三、函數的傳值調用 函數傳值調用的特點是將調用函數的實參表中的實參值依次對應地傳遞給被

9、調用函數的形參表中的形參。要求函數的實參與形參個數相等，并且類型相同。函數的調用過程實際上是對?？盏牟僮鬟^程，因為調用函數是使用?？臻g來保存信息的。函數在返回時，如果有返回值，則將它保存在臨時變量中。然后恢復主調函數的運行狀態(tài)，釋放被調用函數的?？臻g，按其返回地址返回到調用函數。 在C+語言中，函數調用方式分傳值調用和傳址調用。三、函數的傳值調用1、傳值調用這種調用方式是將實參的數據值傳遞給形參，即將實參值拷貝一個副本存放在被調用函數的棧區(qū)中。在被調用函數中，形參值可以改變，但不影響主調函數的實參值。參數傳遞方向只是從實參到形參，簡稱單向值傳遞。舉個例子： #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函數中交換了a,b兩數的值，但是在main中卻沒有交換。因為swap函數只是交換c,d兩變量副本的值，實參值沒有改變，并沒有達到交換的目的。三、函數的傳值調用2、傳址調用 這種調用方式是將實參變量的地址值傳遞給形參，這時形參實是指針，即讓形參的指針指向實參地址，這里不再是將實參拷貝一個副本給形參，而是讓形參直接指向實參，這就

11、提供了一種可以改變實參變量的值的方法。現在用傳址調用來實現swap： #include using namespace std; void swap(int &a,int &b) /定義swap()函數，形參是傳址調用 int tmp=a;a=b;b=tmp; int main() int c=1,d=2; swap(c,d); /交換變量 coutc dendl; return 0; /程序輸出為：2 1 在此例中,因為swap函數的參數為傳址調用，&a是指實參變量的地址值傳遞給形參，所以，在函數swap中修改a,b的值相當于在主函數main中修改c,d的值。四、函數的應用舉例-【函數】例6

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

13、 s; /階乘函數的值返回例6.3 計算如圖多邊形的面積。從圖中可以看出，五邊形的面積是三個三角形面積之和。程序如下：#include#include /使用printf和scanf語句，調用cstdio庫#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); /調用三次函數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 定義一個函數check(n,d)，讓它返回一個布爾值。如果數字d在正整數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 用冒泡法對數組元素按由小到大排序（數組作為函數參數）#includeusing namespace std;void bubble(int,int); /相當于void bubble

16、(int a,int n);int main() /大數組應開為全局變量 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; 在前面我們已經知道數組名是該數組在內存的首地址。將數組名作為參數傳給函數，實際上是把數組的地址傳給函數。形參數組和實參數組的首地址重合，因此在被調用函數中對數組元素值進行改變，主調函數中實參數組的相應元素值也會改變。五、全程變量、局部變量及它們的作用域 在函數外部定義的變量稱為外部變量或全局變量，在函數內部定義的變量稱為內部變量或局部變量。1全局變量 定義在函數外部沒有被花括號括起來的變量稱為全局變量，全局變量的作用域是從變量定義的位置開始到文件結束。由于全局變量是在函數外部定義的，因此對所有函數而言都是外部的，可以在文件中位于全局變量定義后面的任何函

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

19、ndl;return 0;運行結果： 輸入: 12 18 輸出: 36使用全局變量的說明：在一個函數內部，既可以使用本函數定義的局部變量，也可以使用在此函數前定義的全局變量。全局變量的作用是使得函數間多了一種傳遞信息的方式。如果在一個程序中多個函數都要對同一個變量進行處理，即共享，就可以將這個變量定義成全局變量，使用非常方便，但副作用也不可低估。過多地使用全局變量，會增加調試難度。因為多個函數都能改變全局變量的值，不易判斷某個時刻全局變量的值。過多地使用全局變量，會降低程序的通用性。如果將一個函數移植到另一個程序中，需要將全局變量一起移植過去，同時還有可能出現重名問題。全局變量在程序執(zhí)行的全過

20、程中一直占用內存單元。全局變量在定義時若沒有賦初值，其默認值為0。2局部變量局部變量的作用域是在定義該變量的函數內部，換句話說，局部變量只在定義它的函數內有效。函數的形參也是局部變量。局部變量的存儲空間是臨時分配的，當函數執(zhí)行完畢，局部變量的空間就被釋放，其中的值無法保留到下次使用。 由于局部變量的作用域僅局限于本函數內部，所以，在不同的函數中變量名可以相同，它們分別代表不同的對象，在內存中占據不同的內存單元，互不干擾。一個局部變量和一個全局變量是可以重名的，在相同的作用域內局部變量有效時全局變量無效。即局部變量可以屏蔽全局變量(4)在代碼塊中定義的變量的存在時間和作用域將被限制在該代碼塊中。

21、如for(int i;i=n;i+) sum+=i中的i是在該for循環(huán)語句中定義的，存在時間和作用域只能被限制在該for循環(huán)語句中。 (5)這里需要強調的是，主函數main中定義的變量也是局部變量，這一點與其他程序設計語言不同。(6) 全局變量數組初始全部為0，局部變量值是隨機的，要初始化初值，局部變量受棧空間大小限制，大數組需要注意。通俗說，局部變量的數組不能開很大，全局變量隨便。六、函數的綜合應用-【函數】 例6.7 寫一個判斷素數的函數，輸入一個數，判斷它是否是素數，是輸出yes，不是輸出no。【分析】對于任意整數i，根據素數定義，我們從2開始，到sqrt(i)，找i的第一個約數，若找

22、到第一個約數，則i必然不是素數。程序如下：#include#includeint prime(int x); /對于函數的聲明int main()int n;scanf(%d,&n);if (prime(n) printf(%sn,yes);else printf(%sn,no);return 0;int prime(int x) /判斷x是否素數的函數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 編程輸入十進制整數N（N：-327673276

23、7），請輸出它對應的二進制、八進制、十六進制數?！痉治觥窟@是一道進行數制轉換的問題，將十進制整數轉換成R進制的數，算法是：除以R取余，再將余數倒過來寫出即是R進制的數。本例是要求把一個十進制數同時轉換成二進制、八進制、十六進制數。因此可以設計一個過程同時處理這三種的進制轉換。程序如下：#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轉成2進制數 TurnData(n,8); /n轉成8進制數 T

24、urnData(n,16); /n轉成16進制數 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;這里的過程TurnData中的參數不需要把什么值返回給主程序，因此設為形參即可。例6.9 編寫一個給一個分數約分的程序。 程序如下：#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; /用輾轉相除法求x,y的最大公約數 do r=m%n; m=n; n=r; while (r!=0); x/=m; /用兩者的最大公約數i對x,y進行約分 y/=m; coutsetw(5)xsetw(5)yendl;運行結果：輸入 : 12 8輸出 : 3 2【課堂練習】1.求正整數2和100之間的完全數。完全數：因子之和等于它本身的自然數，如6=1+2+32.編程求2n(n為大于2的正整數)中有多少個素數。3已知 m=，輸入a,b,c，求m。

26、把求三個數的最大數max(x,y,z)分別定義成函數和過程來做。4.如果一個自然數是素數,且它的數字位置經過對換后仍為素數,則稱為絕對素數,例如13。試求出所有二位絕對素數。5.自然數a的因子是指能被a整除的所有自然數，但不含a本身。例如12的因子為：1,2,3,4,6。若自然數a的因子之和為b，而且b的因子之和又等于a，則稱a,b為一對“親和數” 。求最小的一對親和數(ab)。6.如果一個數從左邊讀和從右邊讀都是同一個數，就稱為回文數。例如6886就是一個回文數，丘出所有的既是回文數又是素數的三位數。7根據公式arctanx(x)=x-x3/3+x5/5-x7/7+和=6 arctanx()

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

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

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

30、出一行，表示被篩選為甲流的病人數量。樣例輸入: 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【上機練習】4.統(tǒng)計單詞數【1.12編程基礎之函數與過程抽象05】Noip2011普及組第2題 一般的文本編輯器都有查找單詞的功能，該功能可以快速定位特定單詞在文章中的位置，有的還能統(tǒng)計出特定單詞在文章中出現的次數。 現在，請你編程實現這一功能，具體要求是：給定一個單詞，請你輸出它在給定的文章中出現的次數和第一次出現的位置。注意：匹配單詞時，不區(qū)分大小寫，但要求完全匹配，即給定單詞必須與文章中

31、的某一獨立單詞在不區(qū)分大小寫的情況下完全相同（參見樣例1），如果給定單詞僅是文章中某一單詞的一部分則不算匹配（參見樣例2）。輸入: 第 1 行為一個字符串，其中只含字母，表示給定單詞； 第 2 行為一個字符串，其中只可能包含字母和空格，表示給定的文章。輸出: 只有一行，如果在文章中找到給定單詞則輸出兩個整數，兩個整數之間用一個空格隔開，分別是單詞在文章中出現的次數和第一次出現的位置（即在文章中第一次出現時，單詞首字母在文章中的位置，位置從0開始）；如果單詞在文章中沒有出現，則直接輸出一個整數-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【上機練習】5.機器翻譯【1.12編程基礎之函數與過程抽象07】Noip2010提高組第1題 小晨的電腦上安裝了一個機器翻譯軟件，他經常用這個軟件來翻譯英語文章。 這個翻譯軟件的原理很簡單，它只是從頭到尾，依次將每個英文單詞用對應的中文含義來替換。對于每個英文單詞，軟件會先在內存中查找這個單詞的中文含義，如果內存中有，軟件就會用它進行翻譯；如果內存中沒有，軟件就會在外存中的詞典內查找，查出單詞的中文含義然后翻譯，并將這個單詞和譯義放入內存，以備

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

34、詞是同一個單詞，當且僅當它們對應的非負整數相同。 【上機練習】輸出: 共1行，包含一個整數，為軟件需要查詞典的次數。樣例輸入:樣例 #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 說明： 整個查字典過程如下：每行表示一個單詞的翻譯，冒號前為本次翻譯后的內存狀況： 空：內存初始狀態(tài)為空。 1 1：查找單詞1并調入內存。 2 1 2：查找單詞2并調入內存。 3 1 2：在內存中找到單詞1。 4 1 2 5：查找單詞5并調入內存。 5 2 5 4：查找單詞4并調入內存替

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

36、e密碼中，密鑰k是一個字母串，k=k1k2kn。當明文M=m1m2mn時，得到的密文C=c1c2cn，其中ci=miki，運算的規(guī)則如下表所示： Vigenre加密在操作時需要注意： 1.運算忽略參與運算的字母的大小寫，并保持字母在明文M中的大小寫形式； 2.當明文M的長度大于密鑰k的長度時，將密鑰k重復使用。 例如，明文M=Helloworld，密鑰k=abc時，密文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 【上機練習】輸入: 第一行為一個字符串，表示密鑰k，長度不超過

37、100，其中僅包含大小寫字母。第二行 為一個字符串，表示經加密后的密文，長度不超過1000，其中僅包含大小寫字母。 對于100%的數據，輸入的密鑰的長度不超過100，輸入的密文的長度不超過1000，且都僅包含英文字母。輸出: 輸出共1行，一個字符串，表示輸入密鑰和密文所對應的明文。樣例輸入: CompleteVictory Yvqgpxaimmklongnzfwpvxmniytm樣例輸出: Wherethereisawillthereisaway【上機練習】7.素數對【1.12編程基礎之函數與過程抽象10】 兩個相差為2的素數稱為素數對，如5和7，17和19等，本題目要求找出所有兩個數均不大于

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

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

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

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

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

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

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

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

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

47、方法進行求解。定義子程序xn(int n)求Xn ;如果n=1則遞歸調用xn(n-1) 求xn1 ;當遞歸調用到達n=0時終止調用, 然后執(zhí)行本“層”的后繼語句;遇到子程序運行完，就結束本次的調用，返回到上一“層”調用語句的地方，并執(zhí)行其后繼語句;繼續(xù)執(zhí)行步驟，從調用中逐“層”返回，最后返回到主程序。 采用函數編寫程序如下：#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); /遞歸式 采用全程變量編寫程序如下：#includeusing namespace std;int tt,x; /利用全局變量tt傳遞結果int xn(int);int main()int n; cinxn; xn(n); coutxn=tt0時，x!=x*(x-1)！。 假設用函數Fac(x)表示x的階乘，當x=3時，Fac(3)的求解方法可表示為：Fac(3)=3*fac(2)=3*2*Fac(1)=3*2*1*Fac(0)=3*2*1*1=6定義函數：int fac(int n) 如果n=0，則fac=1; 如果n0，則繼續(xù)調用函數fac=

49、n*fac(n-1);返回主程序，打印fac(x)的結果。它的執(zhí)行流程如下圖所示：采用有參函數編寫程序如下：#includeusing namespace std;int fac(int );int main()int x;cinx;coutx!=fac(x)endl; /主程序調用fac(x) 求x !return 0;int fac(int n) /函數fac(n) 求n !return n=0 ? 1 : n*fac(n-1); /調用函數fac(n-1)遞歸求(n-1) !【說明】： 這里出現了一個小東西，三元運算符“?:”。a?b:c的含義是：如果a為真，則表達式的值是b，否則是c。

50、所以n=0? 1 : n*fac(n-1)很好地表達了剛才的遞歸定義。 采用全程變量編寫程序如下： #includeusing namespace std;int t;int fac(int);int main()int x;cinx;fac(x);coutt0，n0) 【方法1】求兩個數的最大公約數，可以用枚舉因子的方法，從兩者中較小的數枚舉到能被兩個數同時整除且是最大的約數的方法；也可以用輾轉相除法，這里采用遞歸實現輾轉相除算法： 求m除以n的余數; 如果余數不為0，則讓m=n，n=余數，重復步驟，即調用子程序; 如果余數為0，則終止調用子程序; 輸出此時的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】二進制最大公約數算法(1)遞歸終止條件：gcd(m,m)=m。(2)遞歸關系式： mn時：gcd(m,n)=gcd(n,m) m為偶數，n為偶數：gcd(m,n)=2*gcd(m/2,n/2) m為偶數，n為奇數：gcd(m,n)=gcd(m/2,n) m為奇數，n為偶數：gcd(m,n)=gcd(m,n/2) m為奇數，n為奇數：gcd(m,n)=gcd(n,m-n) 該方法和方法1相比更適合求高精度