第一篇：算法競(jìng)賽入門經(jīng)典授課教案第4章 函數(shù)和遞歸
第4章
函數(shù)和遞歸
第4章 函數(shù)和遞歸
【教學(xué)內(nèi)容相關(guān)章節(jié)】
4.1數(shù)學(xué)函數(shù) 4.2地址的指針 4.3遞歸 4.4本章小結(jié) 【教學(xué)目標(biāo)】
（1）掌握多參數(shù)、單返回值的數(shù)學(xué)函數(shù)的定義和使用方法；（2）學(xué)會(huì)用typedef定義結(jié)構(gòu)體；（3）學(xué)會(huì)用assert宏幫助調(diào)試；
（4）理解函數(shù)調(diào)用時(shí)用實(shí)參給形參賦值的過程；（5）學(xué)會(huì)定義局部變量和全局變量；
（6）理解調(diào)用棧和棧幀，學(xué)會(huì)用gdb查看調(diào)用棧并選擇棧楨；（7）理解地址和指針；
（8）理解遞歸定義和遞歸函數(shù)；
（9）理解可執(zhí)行文件中的正文段、數(shù)據(jù)段和BSS段；（10）熟悉堆棧段，了解棧溢出的常見原因?！窘虒W(xué)要求】
掌握帶參函數(shù)的調(diào)用、賦值過程及函數(shù)的返回值，理解地址和指針的概念，理解遞歸定義和遞歸函數(shù)，理解段的概念。【教學(xué)內(nèi)容提要】
運(yùn)用前3章的知識(shí)盡管在理論上已經(jīng)足以寫出多數(shù)算法程序了，但實(shí)際上稍微復(fù)雜一點(diǎn)的程序往往由多個(gè)函數(shù)組成。函數(shù)是“過程式程序設(shè)計(jì)”的產(chǎn)物，但也產(chǎn)生了局部變量、參數(shù)傳遞方式、遞歸等諸多新的知識(shí)點(diǎn)。本章淡化例題，重點(diǎn)在于理解最后的語法。同時(shí)，通過請(qǐng)出gdb這一王牌，從根本上幫助讀者理解，看清事物的本質(zhì)?！窘虒W(xué)重點(diǎn)、難點(diǎn)】
教學(xué)重點(diǎn)：
（1）掌握多參數(shù)、單返回值的數(shù)學(xué)函數(shù)的定義和使用方法；（2）理解函數(shù)調(diào)用時(shí)用實(shí)參給形參賦值的過程；（3）理解地址和指針；
（4）理解遞歸定義和遞歸函數(shù)；
（5）理解可執(zhí)行文件中的正文段、數(shù)據(jù)段和BSS段。教學(xué)難點(diǎn)：貪心算法的基本要素?！菊n時(shí)安排（共3學(xué)時(shí)）】
4.1數(shù)學(xué)函數(shù) 4.2地址的指針 4.3遞歸 4.4本章小結(jié)
（0.5學(xué)時(shí)）
第 91 頁
第4章
函數(shù)和遞歸
4.1 數(shù)學(xué)函數(shù)
4.1.1 簡(jiǎn)單函數(shù)的編寫
下面給出一個(gè)計(jì)算兩點(diǎn)歐幾里德距離的函數(shù)：
double dist(double x1, double y1, double x2, double y2){ return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));} 提示4-1：C語言中的數(shù)學(xué)函數(shù)可以定義成“返回類型 函數(shù)名(參數(shù)列表){ 函數(shù)體 }”，其中函數(shù)體的最后一條語句應(yīng)該是“return 表達(dá)式；”。
提示4-2：函數(shù)的參數(shù)和返回值最好是“一等公民”int或double（注意char是一種特殊的int）。其他“非一等公民”作為以參數(shù)和返回值要復(fù)雜一些。
提示4-3：如果函數(shù)在執(zhí)行的過程中碰到了return語句，將直接退出這個(gè)函數(shù)，不去執(zhí)行后面的語句。相反，如果在執(zhí)行過程中始終沒有return語句，則會(huì)返回一個(gè)不確定的值。幸好，-Wall可以捕捉到這一可疑情況并產(chǎn)生警告。
main函數(shù)是有返回值的，假設(shè)返回值為0。main函數(shù)是整個(gè)程序的入口，如果有一個(gè)“其他的程序”來調(diào)用這個(gè)main函數(shù)——如操作系統(tǒng)、IDE、調(diào)試器，甚至自動(dòng)評(píng)測(cè)系統(tǒng)，這個(gè)0代表“正常結(jié)束”，就是返回給這些調(diào)用者的。在算法競(jìng)賽中，除了有特殊規(guī)定之外，請(qǐng)總是讓它返回0，以免評(píng)測(cè)系統(tǒng)錯(cuò)誤地認(rèn)為你的程序是異常退出。
提示4-4：在算法競(jìng)賽中，請(qǐng)總是讓main函數(shù)返回0。下面給出上述函數(shù)的另一種方法：
double dist(double x1, double y1, double x2, double y2){ double dx=x1-x2;double dy=y1-y2;return hypot(dx,dy);} 說明：（1）hypot函數(shù)的功能是計(jì)算一直角三角形的斜邊長(zhǎng)度。
（2）函數(shù)hypot(x,y)表示根據(jù)直角三角形的兩直解邊長(zhǎng)度x和y計(jì)算其斜邊的長(zhǎng)度?；蛘呤菑臉?biāo)點(diǎn)(x,y)到原點(diǎn)的距離，該函數(shù)的算法等同于sqrt(x*x+y*y)。
4.1.2 使用結(jié)構(gòu)體的函數(shù)
由于平面的點(diǎn)坐標(biāo)(x,y)可以看用一個(gè)整體，所以可以定義一個(gè)結(jié)構(gòu)體,它的名稱是Point，讓它包含點(diǎn)的坐標(biāo)x和y。
struct Point{ double x, y;};double dist(struct Point a, struct Point b){ return hypot(a.x-b.x, a.y-b.y);} 提示4-5：在C語言中，定義結(jié)構(gòu)體的方法為：“struct 結(jié)構(gòu)體名稱{ 域定義 };”,注意花括號(hào)的后面還有一個(gè)分號(hào)。
由于上面的定義在所有用到Piont的地方都得寫一個(gè)“struct”，所以給出一個(gè)簡(jiǎn)潔的寫法如下：
typedef struct Point{ double x, y;}Point;double dist(Point a, Point b){ return hypot(a.x-b.x, a.y-b.y);} 提示4-6：為了方便，往往用“typedef struct{ 域定義 }類型名;”的方式定義一個(gè)新類型名。這樣，就可以像原生數(shù)據(jù)類型一樣使用這個(gè)自定義類型。
4.1.3 應(yīng)用舉例 例4-1 組合數(shù)。
第 92 頁
第4章
函數(shù)和遞歸
輸入非負(fù)整數(shù)m和n，輸出組合數(shù)Cnm?n!m!(n?m)!，其中m≤n≤20。
【分析】
由組合數(shù)的公式可知，多次出現(xiàn)階乘，所以將求階乘作為一個(gè)函數(shù)：
程序4-1 組合數(shù)
#include
int main(){ int m, n;scanf(“%d%d”, &m, &n);printf(“%dn”, f(n)/(f(m)*f(n-m)));return 0;} 注意：編好程序后，一定要?jiǎng)e忘了測(cè)試程序。
提示4-7：即使最終答案在我們選擇的數(shù)據(jù)類型范圍之內(nèi)，計(jì)算的中間結(jié)果仍然可能溢出。
例4-2 孿生素?cái)?shù)。
如果n和n+2都是素?cái)?shù)，則稱它們是孿生素?cái)?shù)。輸入m，輸出兩個(gè)數(shù)均不超過m的最大孿生素?cái)?shù)。5≤m≤10000。例如m=20時(shí)答案是17、19，m=1000時(shí)答案是881、883。
【分析】
被1和它自身整除的、大于1的整數(shù)稱為素?cái)?shù)。由于要判斷n和n+2是否是素?cái)?shù)，所以把“判斷素?cái)?shù)”可以寫成一個(gè)函數(shù)，只需調(diào)用這個(gè)函數(shù)兩次就可以了。這樣的“判斷一個(gè)事物是否具有某一性質(zhì)”的函數(shù)還有一個(gè)學(xué)術(shù)名稱——謂詞（predicate）。
程序4-2 孿生素?cái)?shù)（1）
#include
int main(){ int i, m;scanf(“%d”, &m);for(i = m-2;i >= 3;i--)if(is_prime(i)&& is_prime(i+2)){ printf(“%d %dn”, i, i+2);break;}
第 93 頁
第4章
函數(shù)和遞歸
return 0;} 說明：（1）在is_prime函數(shù)的編寫中，用到了兩上小技巧。一是只判斷不超過sqrt(x)的整數(shù)i；二是及時(shí)退出：一旦發(fā)現(xiàn)x有一個(gè)大于1的因子，立刻返回0（假），只有最后才返回1（真）。
（2）函數(shù)的命名應(yīng)注意做到“見名知意”，即選有含義的英文單詞（或其縮寫）作為函數(shù)名。例如，“is_prime”取自英文“is is a prime?”（它是素?cái)?shù)嗎？）。
提示4-8：建議把謂詞（用來判斷某事物是否具有某種特性的函數(shù)）命名成“is_xxx”的形式。它返回int值，非0表示值，0表示假。
提示4-9：編寫函數(shù)時(shí)，應(yīng)盡量保證它能對(duì)任何合法參數(shù)都能得到正確的結(jié)果。如若不然，應(yīng)在顯著位置標(biāo)明函數(shù)的缺陷，以避免誤用。
下面改進(jìn)之后的版本：
程序4-3 孿生素?cái)?shù)（2）
#include
int main(){ int i, m;scanf(“%d”, &m);for(i = m-2;i >= 3;i--)if(is_prime(i)&& is_prime(i+2)){ printf(“%d %dn”, i, i+2);break;} return 0;} 除了特判n==1的情況外，程序中還使用了變量m，一方面避免了每次重復(fù)計(jì)算sqrt(x)，另一方面也通過四舍五入避免了浮點(diǎn)誤差。
最后，程序使用了assert.h的assert宏來限制非法的函數(shù)調(diào)用：當(dāng)x>=0不成立時(shí)，程序?qū)惓＝K止，并給出了提示信息。
說明：（1）斷言（assert）的語義如下：如果表達(dá)式的值為0（假），則輸出錯(cuò)誤消息并終止程序的執(zhí)行（一般還會(huì)出對(duì)話框，說明在什么地方引發(fā)了assert）；如果表達(dá)式為真，則不進(jìn)行任何操作。因此，斷言失敗就表明程序存在一個(gè)bug。
（2）C/C++的宏（assert）就是這樣的斷言，當(dāng)表達(dá)式為假時(shí)，調(diào)用庫函數(shù)abort()終止程序。
（3）程序中可以把a(bǔ)ssert看成一個(gè)在任何系統(tǒng)狀態(tài)下都可以安全使用的無害測(cè)試手段，所以不要把程序中的assert語句刪除掉。
（4）如果程序在assert處終止了，并不是說含有該assert的函數(shù)有錯(cuò)誤，而是調(diào)用函數(shù)出了差錯(cuò)，assert可以幫助我們追蹤到錯(cuò)誤發(fā)生的原因。
（5）在函數(shù)的入口處，建議使用斷言來檢查參數(shù)的有效性（合法性）。請(qǐng)給assert語句加注釋，告訴人們assert語句究竟要干什么。
第 94 頁
第4章
函數(shù)和遞歸
提示4-10：編程時(shí)合理利用assert宏，將給調(diào)試帶來很大的方便?？偠灾趯?shí)際的系統(tǒng)中，“一個(gè)地方的參數(shù)錯(cuò)誤就引起整個(gè)程序異常退出”是不可取的，在編寫和調(diào)試算法程序中，assert會(huì)“迫使”編寫出更高質(zhì)量的程序。
4.2 地址和指針
有時(shí)候，我們編程時(shí)為了完成某些操作——如交換兩個(gè)變量，或者需要返回兩個(gè)甚至更多的值——如解一個(gè)二元一次方程組。
4.2.1 變量交換
程序4-4 用函數(shù)交換變量（錯(cuò)誤）
#include
int main(){ int a = 3, b = 4;swap(3, 4);printf(“%d %dn”, a, b);return 0;} 說明：（1）下面來說一下函數(shù)調(diào)用的過程： ①計(jì)算參數(shù)的值（若是數(shù)學(xué)表達(dá)式，需要計(jì)算）。程序4-4中函數(shù)調(diào)用語句swap(a, b);中的a和b就是實(shí)際參數(shù)（簡(jiǎn)稱實(shí)參），它們的值分別為3和4。實(shí)參可以是常量、變量或表達(dá)式。
②把實(shí)參賦值給函數(shù)聲明中的a和b。函數(shù)聲明中的a和b稱為形式參數(shù)（簡(jiǎn)稱形參）。然后在函數(shù)內(nèi)部完成計(jì)算或操作。注意實(shí)參向形參的數(shù)據(jù)傳遞是“值傳遞”，即單向傳遞，只由實(shí)參傳給形參，而不能由形參傳回來給實(shí)參。
（2）下面來說一下幾個(gè)概念： ①局部變量（local variable）
函數(shù)（包括main函數(shù)）的形參和在該函數(shù)里定義的變量都被稱為該函數(shù)的局部變量。不同的局部變量相互獨(dú)立，無法訪問其他函數(shù)的局部變量，也就是說，局部變量只能在定義它的函數(shù)內(nèi)部使用，超出了局部變量的作用域范圍，局部變量是無效的。
局部變量的存儲(chǔ)空間是臨時(shí)分配的，函數(shù)執(zhí)行完畢時(shí)，局部變量的空間將被釋放，其中的值無法保留到下次使用。
②靜態(tài)局部變量（static local variable）
有時(shí)希望函數(shù)中的局部變量的值在函數(shù)調(diào)用結(jié)束后不消失而保留原值，這時(shí)就應(yīng)該指定局部變量為“靜態(tài)局部變量”，用關(guān)鍵字static進(jìn)行聲明。
靜態(tài)局部變量在程序整個(gè)運(yùn)行期間都不釋放，而局部變量在函數(shù)調(diào)用結(jié)束后即釋放。靜態(tài)局部變量在編譯時(shí)賦初值，即只賦初值一次；而對(duì)自動(dòng)變量賦初值是在函數(shù)調(diào)用時(shí)進(jìn)行，每調(diào)用一次函數(shù)重新給一次初值，相當(dāng)于執(zhí)行一次賦值語句。
如果在定義局部變量時(shí)不賦初值的話，則對(duì)靜態(tài)局部變量來說，編譯時(shí)自動(dòng)賦初值0（對(duì)數(shù)值型變量）或空字符（對(duì)字符變量）。而對(duì)自動(dòng)變量來說，如果不賦初值則它的值是一個(gè)不確定的值。
靜態(tài)局部變量在函數(shù)調(diào)用結(jié)束后仍然存在，其它函數(shù)是不能引用它們的。③全局變量（global variable）
將變量寫在所有函數(shù)的外面，這樣的變量是全局變量。全局變量可以在任何時(shí)候，由任何函數(shù)訪問。如果某局部變量和某個(gè)全局變量的名字一樣，那么在該局部變量的作用域中，起作用的是局部變量，全局變量被同名的局部變量屏蔽掉了，不起作用。
需要注意的是，全局變量是非常危險(xiǎn)的，應(yīng)該謹(jǐn)慎使用。
第 95 頁
第4章
函數(shù)和遞歸
提示4-11：函數(shù)的形參和在函數(shù)內(nèi)聲明的變量都是該函數(shù)的局部變量。無法訪問其他函數(shù)的局部變量。局部變量的存儲(chǔ)空間是臨時(shí)分配的，函數(shù)執(zhí)行完畢時(shí)，局部變量的空間將 釋放，其中的值無法保留到下次使用。在函數(shù)外聲明的變量是全局變量，它們可以被任何函數(shù)使用。操作全局變量有風(fēng)險(xiǎn)，應(yīng)謹(jǐn)慎使用。
下面就變量的生存期和可見性給出一個(gè)例子。
例4-3 寫出下面程序的運(yùn)行結(jié)果。#include
void other(){ static int a=2;static int b;/*a,b為靜態(tài)局部變量，具有全局壽命，局部可見，只第一次進(jìn)入函數(shù)進(jìn)入 函數(shù)時(shí)初始化*/ int c=10;/*c為局部變量，具有動(dòng)態(tài)生存期，每次進(jìn)入函數(shù)時(shí)都初始化*/ a=a+2;i=i+32;c=c+5;printf(“-----OTHER------n”);printf(“i:%d a:%d b:%d c:%dn”,i,a,b,c);b=a;} 解答：
運(yùn)行結(jié)果為如下：-------Main--------i:1 a:0 b:-10 c:0------Other--------i:33 a:4 b:0 c:15-------Main--------i:33 a:0 b:-10 c:8-------Other-------i:75 a:6 b:4 c:15 4.2.2 調(diào)用棧
調(diào)用棧描述的是函數(shù)之間的調(diào)用關(guān)系。它由多個(gè)棧幀（Stack Frame）組成，每個(gè)棧幀對(duì)應(yīng)著一個(gè)未運(yùn)行完的函數(shù)。棧幀中保存了該函數(shù)的返回地址和局部變量，因而不僅能在執(zhí)行完畢后找到正確的返回地址，還很自然地保證了不同函數(shù)的局部變量互不相干——因?yàn)椴煌瘮?shù)對(duì)應(yīng)著不同的棧幀。
第 96 頁
第4章
函數(shù)和遞歸
提示4-12：C語言調(diào)用棧（Call Stack）來描述函數(shù)之間的調(diào)用關(guān)系。調(diào)用棧由棧幀（Stack Frame）組成，每個(gè)棧幀對(duì)應(yīng)著一個(gè)未運(yùn)行完的函數(shù)。在gdb中可以用backtrace（簡(jiǎn)稱bt）命令打印所有棧幀信息。若要用p命令打印一個(gè)當(dāng)前棧幀的局部變量，可以用frame命令選擇另一個(gè)棧幀。
下面給出用gdb完成上述操作的命令和結(jié)果。（1）第一步：編譯程序。gcc 4-4.c-g（2）第二步：運(yùn)行g(shù)db。gdb a.exe 這樣，gdb在運(yùn)行時(shí)會(huì)自動(dòng)裝入剛才生成的可執(zhí)行程序。（3）第三步：查看源碼。(gdb)l 這里(gdb)是gdb的提示符，字母l是輸入的命令，它是list（列出程序清單）的縮寫。（4）第四步：加斷點(diǎn)并運(yùn)行。(gdb)b 4(gdb)r 其中b命令把斷點(diǎn)設(shè)在了第4行，r命令運(yùn)行程序，之后碰到了斷點(diǎn)并停止。接下來，查看調(diào)用棧。
（5）第四步：查看調(diào)用棧。(gdb)bt(gdb)p a(gdb)p b(gdb)up(gdb)p a(gdb)p b 這一步是關(guān)鍵。根據(jù)bt命令，調(diào)用棧中包含兩個(gè)棧幀：0#和1#，其中0號(hào)是當(dāng)前棧幀——swap函數(shù)，1號(hào)是它的“上一個(gè)”棧幀——main函數(shù)。
使用p命令可以打印變量值。p a和p b表示查看當(dāng)前棧幀中變量a和b的值。up命令表示選擇上一個(gè)棧幀。然后用p a和p b查看當(dāng)前棧幀中變量a和b的值。最后用q命令退出gdb。
說明：gdb是GNU開源組織發(fā)布的一個(gè)強(qiáng)大的UNIX下的程序調(diào)試工具。或許，大家比較喜歡那種圖形界面方式的，像VC、BCB等IDE的調(diào)試，但如果是在 UNIX平臺(tái)下做軟件，會(huì)發(fā)現(xiàn)gdb這個(gè)調(diào)試工具有比VC、BCB的圖形化調(diào)試器更強(qiáng)大的功能。
4.2.3 用指針實(shí)現(xiàn)變量交換
程序4-4不能實(shí)現(xiàn)兩個(gè)變量的值交換，用指針可以實(shí)現(xiàn)兩個(gè)變量的值交換。
程序4-5 用函數(shù)交換變量（正確）
#include
int main(){ int a = 3, b = 4;swap(&a, &b);printf(“%d %dn”, a, b);return 0;} 語句swap(&a, &b);中變量名前面加&得到的是該變量的地址。
提示4-13：C語言的變量都是放在內(nèi)存中的，而內(nèi)存中的每個(gè)字節(jié)都有一個(gè)稱為地址（address）的編號(hào)。每個(gè)變量都占有一定數(shù)目的字節(jié)（可用sizeof運(yùn)算符獲得），其中第一個(gè)字節(jié)的地址稱為變量的地址。
第 97 頁
第4章
函數(shù)和遞歸
提示4-14：用int* a聲明的變量a是指向int型變量的指針。賦值a=&b的含義是把變量b的地址存放在指針a中，表達(dá)式*a代表a指向的變量，它既可以放在賦值符號(hào)的左邊（左值），也可以放在右邊（右值）。
提示4-15：千萬不要濫用指針，這不僅會(huì)把自己搞糊涂，還會(huì)讓程序產(chǎn)生各種奇怪的錯(cuò)誤。事實(shí)上，本書的程序會(huì)很少用指針。
4.2.4 初學(xué)者易犯的錯(cuò)誤 一種典型的錯(cuò)誤寫法是：
void swap(int* a, int* b){ int *t = a;a = b;b = t;} 它交換了swap函數(shù)的局部變量a和b（輔助變量t必須是指針。int a是錯(cuò)誤的），但卻始終沒有修改它們指向的內(nèi)容，因此main函數(shù)中的a和b不會(huì)改變。
另一種錯(cuò)誤寫法是：
void swap(int* a, int* b){ int *t;*t = *a;*a = *b;*b = *t;} 這個(gè)程序去替換程序4-5，可能得到的結(jié)果是“4 3”。但是它還是錯(cuò)誤的，因?yàn)閠是一個(gè)變量（指針也是一個(gè)變量，只不過類型是“指針”而已），所以根據(jù)規(guī)則，它在賦值之前是不確定的。如果這個(gè)“不確定的值”所代表的內(nèi)存單元恰好是能寫入的，那么這個(gè)程序?qū)⒄９ぷ?；但如果它是只讀的，程序可能會(huì)崩潰。
4.3 遞 歸
4.3.1 遞歸的定義和遞歸函數(shù) 1．基本概念
一個(gè)函數(shù)在它的函數(shù)體內(nèi)調(diào)用它自身稱為遞歸調(diào)用。這種函數(shù)稱為遞歸函數(shù)。Ｃ語言允許函數(shù)的遞歸調(diào)用。在遞歸調(diào)用中，主調(diào)函數(shù)又是被調(diào)函數(shù)。執(zhí)行遞歸函數(shù)將反復(fù)調(diào)用其自身，每調(diào)用一次就進(jìn)入新的一層。例如： int f(int x){ int y;z=f(y);return z;} 本函數(shù)是一個(gè)遞歸函數(shù)。但是運(yùn)行該函數(shù)將無休止地調(diào)用其自身，這當(dāng)然是不正確的。這個(gè)遞歸函數(shù)是一個(gè)死遞歸（無限遞歸，Infinite Recursion）函數(shù)。為了防止遞歸調(diào)用無終止地進(jìn)行，必須在函數(shù)內(nèi)有終止遞歸調(diào)用的手段。常用的辦法是加條件判斷，滿足某種條件后就不再作遞歸調(diào)用，然后逐層返回。
2．遞歸函數(shù)的構(gòu)成要素
遞歸函數(shù)必須滿足兩個(gè)條件：
（1）必須有一個(gè)終止準(zhǔn)則（遞歸的邊界條件、遞歸的結(jié)束條件）；
（2）在每一次調(diào)用自己時(shí)，必須是（在某種意義上）更接近于解（遞推公式或遞歸方程）；
邊界條件與遞歸方程是遞歸函數(shù)的二個(gè)要素。若沒有條件（1），則遞歸無從終止；若沒有條件（2），則不是遞歸。
3．遞歸調(diào)用過程（兩個(gè)階段）（1）遞推階段
將原問題不斷地分解為新的子問題，逐漸從未知的向已知的方向推進(jìn)，最終達(dá)到已知的條件，即遞歸結(jié)束條件，這時(shí)遞推階段結(jié)束。
（2）回歸階段
第 98 頁
第4章
函數(shù)和遞歸
從已知條件出發(fā)，按照“遞推”的逆過程，逐一求值回歸，最終到達(dá)“遞推”的開始處，結(jié)束回歸階段，完成遞歸調(diào)用。
例4-4 用遞歸法計(jì)算n!。
用遞歸法計(jì)算n!，階乘函數(shù)f(n)=n!可定義為：
?ff(0)=1(n)?f(n?1)?n(n?1)【分析】
本題是一個(gè)遞歸問題。下面給出求f(5)的遞歸過程如下：（1）遞推過程
f(5)=5×f(4)→f(4)=4×f(3)→f(3)=3×f(2)→f(2)=2×f(1)→f(1)=1×f(0)→f(0)=1 未知----→已知（2）回歸過程
f(5)=5×f(4)←f(4)=4×f(3)←f(3)=3×f(2)←f(2)=2×f(1)←f(1)=1×f(0)← f(0)=1 =120 =24 =6 =2 =1 未知←---已知 對(duì)應(yīng)的程序如下：
程序4-6 用遞歸計(jì)算階乘
#include
int main(){ printf(“%dn”, f(3));return 0;} 提示4-16：C語言支持遞歸——函數(shù)可以直接或間接調(diào)用自己。但要注意為遞歸函數(shù)編寫終止條件，否則將產(chǎn)生無限遞歸。
4.3.2 C語言對(duì)遞歸的支持
可以借助于gdb來調(diào)試程序4-6。首先用bf命令設(shè)置斷點(diǎn)——除了可以按行號(hào)設(shè)置外，也可以直接給出函數(shù)名，斷點(diǎn)將設(shè)置在函數(shù)的開頭?？梢杂胷命令運(yùn)行程序，并在斷點(diǎn)處停下來，接下來用s命令單步執(zhí)行。
每次執(zhí)行完s指令，都會(huì)有一層遞歸調(diào)用終止，直到返回main函數(shù)。事實(shí)上，如果在遞歸調(diào)用初期查看調(diào)用棧，會(huì)發(fā)現(xiàn)每次遞歸調(diào)用都會(huì)多一個(gè)棧幀——和普通的函數(shù)調(diào)用并沒有什么不同。確實(shí)如此，由于使用了調(diào)用棧，C語言自然支持了遞歸。在C語言的函數(shù)中，調(diào)用自己和調(diào)用其他函數(shù)并沒有任何本質(zhì)區(qū)別，都是建立新棧幀，傳遞參數(shù)并修改“當(dāng)前代碼行”，在函數(shù)體執(zhí)行完畢后刪除棧幀，處理返回值并修改“當(dāng)前代碼行”。
提示4-17：由于使用了調(diào)用棧，C語言支持遞歸。在C語言中，調(diào)用自己和調(diào)用其他函數(shù)并沒有本質(zhì)不同。
4.3.3 段錯(cuò)誤與棧溢出 “段”（segmentation）是指二進(jìn)制文件內(nèi)的區(qū)域，所有某種特定類型信息被保存在里面?？梢杂胹ize程序得到可執(zhí)行文件中各個(gè)段的大小。
提示4-18：在可執(zhí)行文件中，正文段（Text Segment）儲(chǔ)存指令，數(shù)據(jù)段（Data Segment）儲(chǔ)存已初始化的全局變量，BSS段（BSS Segment）儲(chǔ)存未賦值的全局變量所需的空間。
調(diào)用棧所在的段為堆棧段（Stack Segment）。和其他段一樣，它也有自己的大小，不能被越界訪問，否則就會(huì)出現(xiàn)段錯(cuò)誤（Segment Fault）。
每次遞歸調(diào)用都需要往調(diào)用棧里增加一個(gè)棧幀，久而久之就越界了。用術(shù)語把它叫做棧溢出（Stack Overflow）。
提示4-19：在運(yùn)行時(shí)，程序會(huì)動(dòng)態(tài)創(chuàng)建一個(gè)堆棧段，里面存放著調(diào)用棧，因此保存著函數(shù)的調(diào)用關(guān)系和局部變量。
第 99 頁
第4章
函數(shù)和遞歸
?？臻g與操作系統(tǒng)有關(guān)。在Linux中，棧大小是由系統(tǒng)命令ulimit指定的，例如ulimit –a顯示當(dāng)前棧大小，而ulimit-s 32768將把棧大小指定為32MB。但在Windows中，棧大小是儲(chǔ)存在可執(zhí)行文件的。使用gcc可以這樣指定可執(zhí)行文件的棧大?。篻cc –Wl,--stack =16777216，這樣棧大小就變?yōu)?6MB。
提示4-20：在Linux中，棧大小并沒有儲(chǔ)存在可執(zhí)行程序中，只能用ulimit命令修改；在Windows中，棧大小儲(chǔ)存在可執(zhí)行程序中，用gcc編譯時(shí)可以通過-Wl,--stack=
說明：（1）在介紹數(shù)組時(shí)，“把較大的數(shù)組放在main函數(shù)外”是因?yàn)檫@樣定義的數(shù)組是全局?jǐn)?shù)組，放在數(shù)據(jù)段。
（2）局部變量放在堆棧段。棧溢出不見得是遞歸調(diào)用太多，也可能是局部變量太大。只要總大小超過了允許的范圍，就會(huì)產(chǎn)生棧溢出。
4.4 本 章 小 結(jié)
本章涉及了整個(gè)C語言中最難理解的兩個(gè)東西：指針和遞歸。4.4.1 小問題集錦 首先，來編寫一個(gè)函數(shù)solve，給定浮點(diǎn)數(shù)a,b,c,d,e,f，求解方程組ax+by=c,dx+ey=f?！痉治觥?/p>
下面利用線性代數(shù)知識(shí)來分析方程組的什么時(shí)候有唯一解、無解或無窮多解？方程組為如下：
?ax?by?c ??dx?ey?f設(shè)它的系數(shù)矩陣為A=?行變換如下：
?a b??a b c?，它的增廣矩陣為B=[A ]=b???，對(duì)B實(shí)施初等d ed e f?????a b c??a b c??B=????
d e f0 ea-bd fa-cd????（1）當(dāng)ea-bd≠0時(shí)，系數(shù)矩陣A的秩R(A)=2，增廣矩陣的秩R(B)=2,即R(A)=R(B)=2，此時(shí)線性方程組有唯一解。
ce?bf?x???ea?bd ?af?cd?y??ea?bd?（2）當(dāng)ea-bd=0時(shí)
①當(dāng)fa-cd=0時(shí)，R(A)=R(B)=1<2,此時(shí)線性方程組有無窮多組解。
②當(dāng)fa-cd≠0時(shí)，R(A)=1，R(B)=2,則R(A) 函數(shù)solve如下： void solve(float a, float b, float c, float d, float e, float f){ float x, y;assert(e * a – b * d== 0 && f * a – c * d== 0);//使用斷言，解不唯一退出 if(e * a – b * d!= 0){ //此方程的解是唯一的 printf(“The solution of equation is unique:n ”);printf(“x=%f”,(c * e – b * f)/(e * a – b * d));printf(“y=%f”,(a * f – c * d)/(e * a – b * d));return; 第 100 頁 第4章 函數(shù)和遞歸 } if(e * a – b * d == 0 && f * a – c * d!= 0){ //此方程無解 printf(“The equation is no solutio:n ”);return;} } 任務(wù)2：解不唯一時(shí)仍然正常返回，但調(diào)用者有辦法知道解的數(shù)量（無解、唯一解、無窮多組解）。 解答： 函數(shù)solve如下： int void solve(float a, float b, float c, float d, float e, float f){ float x, y;if(e * a – b * d== 0 && f * a – c * d== 0){ //此方程的解是不唯一 printf(“The solution of equation is not unique:n ”);return 2;} if(e * a – b * d!= 0){ //此方程的解是唯一的 printf(“The solution of equation is unique:n ”);printf(“x=%f”,(c * e – b * f)/(e * a – b * d));printf(“y=%f”,(a * f – c * d)/(e * a – b * d));return 1;} if(e * a – b * d == 0 && f * a – c * d!= 0){ //此方程無解 printf(“The equation is no solutio:n ”);return 0;} } 然后，請(qǐng)編寫一個(gè)程序，包含3個(gè)函數(shù)f()、g()和h()，3個(gè)函數(shù)均無參數(shù)，返回值均為int型。 任務(wù)1：定義int a,b，要求在依次執(zhí)行a=f()和b=f()后，a和b的值不同。解答： 程序如下： #include int g(){ c++;return c;} int h(){ c++;return c; 第 101 頁 第4章 函數(shù)和遞歸 } void main(){ int a,b;a=f();b=f();printf(“a=%,b=%d”,a,b);} 很顯然，依次執(zhí)行a=f()和b=f()后，a=2和b=3，a和b的值不同。任務(wù)2：定義int a,b，要求在依次執(zhí)行a=(f()+g())+h()和b=f()+(g()+h())后，a和b的值不同。 解答：將上面的程序a=f();和b=f();，換成a=(f()+g())+h()和b=f()+(g()+h())。很顯然，依次執(zhí)行a=(f()+g())+h()和b=f()+(g()+h())后，a=9和b=18，a和b的值不同。 接下來做兩個(gè)編程探索。 問題1：局部變量是否可以和全局變量重名？如果可以，實(shí)際上使用的是哪個(gè)？這可能會(huì)引起什么樣的難以察覺到的錯(cuò)誤？ 解答：局部變量可以和全局變量同名，但在局部變量的作用域內(nèi)，實(shí)際上使用是局部變量，全局變量失效。 問題2：如果在函數(shù)中聲明一個(gè)局部變量，然后返回它的地址，調(diào)用者獲取該地址時(shí)，該地址是否是有效的？為什么？ 解答：該局部變量的地址是無效的。因?yàn)榫植孔兞康拇鎯?chǔ)空間是臨時(shí)分配的，函數(shù)執(zhí)行完畢時(shí)，局部變量的空間將被釋放。 4.4.2 小結(jié) 本章介紹了數(shù)組和指針，盡管它們?cè)诤芏嗟胤娇梢曰煊茫羔樅蛿?shù)組不是一回事。要盡量回避指針。 遞歸要從從概念和語言兩個(gè)方面理解。從概念上，遞歸就是“自己使用自己”的意思。遞歸調(diào)用就是自己調(diào)用自己，遞歸定義就是自己定義自己。“使用自己”可以是直接的，也可以是間接的。由于重點(diǎn)是設(shè)計(jì)算法和編寫程序，理解遞歸函數(shù)的執(zhí)行過程是非常重要的。 布 置 作 業(yè) 習(xí)題1 請(qǐng)寫出下列程序的輸出結(jié)果。程序如下： #include void main(){ print(3);putchar(“n”); 第 102 頁 第4章 函數(shù)和遞歸 } 解答：輸出結(jié)果如下： 1 2 2 3 3 3習(xí)題2 用遞歸方法求解下面問題。 有5個(gè)人坐在一起，問第5個(gè)人多少歲？他說比第4個(gè)人大2歲。問第4個(gè)人歲數(shù)，他說比第3個(gè)人大2歲。問第3個(gè)人，又說比第2個(gè)人大2歲。問第2個(gè)人，說比第1個(gè)人大2歲。最后問第1個(gè)人，他說是10歲。請(qǐng)問第5個(gè)人多大。 【分析】 本題是一個(gè)遞歸問題。若第i個(gè)人的年齡用age(i)表示，根據(jù)題意可得如下遞推關(guān)系： age(5)=age(4)+2 age(4)=age(3)+2 age(3)=age(2)+2 age(2)=age(1)+2 age(1)=10 可以用數(shù)學(xué)公式表述如下： age(n)??10 n=1 age(n-1)+2 n>1求第5個(gè)人的年齡的遞歸過程如下：（1）遞推過程 age(5)=age(4)+2→age(4)=age(3)+2→age(3)=age(2)+2→age(2)=age(1)+2→age(1)=10 未知→已知（2）回歸過程 age(5)=age(4)+2←age(4)=age(3)+2←age(3)=age(2)+2←age(2)=age(1)+2←age(1)=10 =18 =16 =14 =12 未知←------------------------------已知 程序如下（其中函數(shù)age是遞歸函數(shù)）： #include void main(){ printf(“%dn”,age(5));} 第 103 頁 第3章 數(shù)組和字符串 第3章 數(shù)組和字符串 【教學(xué)內(nèi)容相關(guān)章節(jié)】 3.1數(shù)組 3.2字符數(shù)組 3.3最長(zhǎng)回文子串 3.4小結(jié)與習(xí)題 【教學(xué)目標(biāo)】 （1）掌握一維數(shù)組的聲明和使用方法；（2）掌握二維數(shù)組的聲明和使用方法； （3）掌握字符串的聲明、賦值、比較和連接方法；（4）熟悉字符的ASCII碼和ctype.h； （5）正確認(rèn)識(shí)++、+=等能修改變量的運(yùn)算符；（6）學(xué)會(huì)編譯選項(xiàng)-Wall獲得更多的警告信息；（7）掌握fgetc和getchar的使用方法； （8）了解不同操作系統(tǒng)中換行符的表示方法； （9）掌握fgets的使用方法并了解gets的“緩沖區(qū)溢出”的漏洞；（10）理解預(yù)處理和迭代開發(fā)的技巧?！窘虒W(xué)要求】 （1）掌握一維數(shù)組和二維數(shù)組的聲明和使用方法；（2）掌握字符串的聲明、相關(guān)的操作；（3）掌握fgetc和getchar的使用方法；（3）掌握fgets和gets的使用方法?！窘虒W(xué)內(nèi)容提要】 通過對(duì)第2章的學(xué)習(xí)，了解了計(jì)算機(jī)的計(jì)算優(yōu)勢(shì)，但沒有發(fā)揮出計(jì)算機(jī)的存儲(chǔ)優(yōu)勢(shì)——只用了屈指可數(shù)的變量。盡管有的程序也處理了大量的數(shù)據(jù)，但這些數(shù)據(jù)都只是“過客”，只參與了計(jì)算、并沒有被保存下來。 本章介紹數(shù)組和字符串，二者都能保存大量的數(shù)據(jù)。字符串是一種數(shù)組（字符數(shù)組），但由于其應(yīng)用的特殊性，適用一些特別的處理方式?！窘虒W(xué)重點(diǎn)、難點(diǎn)】 教學(xué)重點(diǎn)： （1）掌握一維數(shù)組和二維數(shù)組的聲明和使用方法；（2）掌握字符串的聲明、相關(guān)的操作；（3）掌握fgetc和getchar的使用方法；（3）掌握fgets和gets的使用方法。教學(xué)難點(diǎn)： （1）掌握一維數(shù)組和二維數(shù)組的聲明和使用方法； （2）掌握字符串的聲明、相關(guān)的操作及字符串處理函數(shù)的使用?！菊n時(shí)安排（共5學(xué)時(shí)）】 3.1數(shù)組 3.2字符數(shù)組 3.3最長(zhǎng)回文子串 3.4小結(jié)與習(xí)題（1學(xué)時(shí)） 第 52頁 第3章 數(shù)組和字符串 3.1 數(shù) 組 下面從一個(gè)問題出發(fā)，說明一下為何使用數(shù)組。 問題：讀入一些整數(shù)，逆序輸出到一行中，已知整數(shù)不超過100個(gè)?！痉治觥?/p> 首先通過循環(huán)來讀取100個(gè)整數(shù)的輸入，然后把每個(gè)數(shù)都存下來，存放在數(shù)組中，最后輸出。 程序3-1 逆序輸出 #include 提示3-1：語句int a[MAXN]聲明了一個(gè)包含MAXN個(gè)整型變量的數(shù)組，即a[0],a[1],a[2] ,?,a[MAXN-1]，但不包含a[MAXN]。MAXN必須是常數(shù)，不能是變量。 在本程序中，聲明MAXN為100+10而不是100，主要是為了保險(xiǎn)起見。 提示3-2：在算法競(jìng)賽中，常常難以精確計(jì)算出需要的數(shù)組大小，數(shù)組一般會(huì)聲明得稍大些。在空間夠用的前提下，浪費(fèi)一點(diǎn)不要緊。 語句a[n++]=x;的等價(jià)于兩條語句a[n]=x;n++;，循環(huán)結(jié)束后，數(shù)據(jù)被存在了a[0],a[1] ,?,a[n-1]，其中變量n個(gè)整數(shù)的個(gè)數(shù)。 在數(shù)組中存放整數(shù)后，依次輸出a[n-1],a[n],?,a[1]和a[0]。一般要求輸出的行首行尾均無空格，相鄰兩個(gè)數(shù)據(jù)間用單個(gè)空格隔開，一共需要輸出n個(gè)整數(shù)，但只有n-1個(gè)空格，所以只好分兩條語句輸出。 在上述程序中，數(shù)組a被聲明在main函數(shù)的外面。簡(jiǎn)單地說，只有在放外面時(shí)，數(shù)組a才可以開得很大；放在main函數(shù)內(nèi)時(shí)，數(shù)組稍大就會(huì)異常退出。 提示3-3：比較大的數(shù)組應(yīng)盡量聲明在main函數(shù)外。 C語言數(shù)組中使用過程中，有一些特殊的情況。例如，數(shù)組不能夠進(jìn)行賦值操作，即不能將一個(gè)整體賦值給另外一個(gè)數(shù)組。如果從數(shù)組a復(fù)制到k個(gè)元素到數(shù)組b，可以這個(gè)語句： memcpy(b,a,sizeof(int)*k)。如果數(shù)組a和b都是浮點(diǎn)型的，復(fù)制時(shí)要寫成memcpy(b,a, sizeof(double)*k)。另外需要注意的是，使用memcpy函數(shù)要包含頭文件string.h。如果需要把數(shù)組a全部復(fù)制到數(shù)組b中，可以寫成：memcpy(b,a,sizeof(a))。 說明：memcpy函數(shù)原型如下： void *memcpy(void *dest, void *src, unsigned int count);它的功能是由src所指內(nèi)存區(qū)域復(fù)制count個(gè)字節(jié)到dest所指內(nèi)存區(qū)域，src和dest所指內(nèi)存區(qū)域不能重疊，函數(shù)返回指向dest的指針。主要功能是對(duì)字符串進(jìn)行拷貝，也可以對(duì)數(shù)組進(jìn)行操作。在程序中需包含頭文件：#include 例3-1 開燈問題。 有n盞燈，編號(hào)為1～n，第1個(gè)人把所有燈打開，第2個(gè)人按下所有編號(hào)為2的倍數(shù)的開關(guān)（這些燈將被關(guān)掉），第3個(gè)人按下所有編號(hào)為3的倍數(shù)的開關(guān)（其中關(guān)掉的燈被打開，開著燈將被關(guān)閉），依此類推。一共有k個(gè)人，問最后有哪些燈開著？ 輸入：n和k，輸出開著的燈編號(hào)。k≤n≤1000。樣例輸入：7 3 樣例輸出：1 5 6 7 第 53頁 第3章 數(shù)組和字符串 【分析】 用a[1],a[2],?,a[n]表示編號(hào)為1,2,3,?,n的燈是否開著，模擬這些操作即可。代碼如下： 程序3-2 開燈問題逆序輸出 #include memset函數(shù)原型如下： void *memset(void *buffer, char c, int count);它的功能是把buffer所指內(nèi)存區(qū)域的前count個(gè)字節(jié)設(shè)置成字符c，第三個(gè)參數(shù)指的是字節(jié)的個(gè)數(shù)，返回指向buffer的指針，在程序中需包含頭文件：#include （2）有一個(gè)技巧是在輸出：為了避免輸出多余空格，設(shè)置了一個(gè)標(biāo)志變量first，可以表示當(dāng)前要輸出的變量是否為第一個(gè)。第一個(gè)變量前不應(yīng)有空格，但其他都有。 例3-2 蛇形填數(shù)。 在n*n方陣?yán)锾钊?,2,?,n*n，要求填成蛇形。例如n=4時(shí)方陣為 10 11 12 1 9 16 13 2 8 15 14 3 7 6 5 4 上面的方陣中，多余的空格只是為了便于觀察規(guī)律，不必嚴(yán)格輸出。n≤8?！痉治觥?/p> 與數(shù)學(xué)的矩相比，可以用一個(gè)所謂的二維數(shù)組來存儲(chǔ)題目中的方陣。只需聲明一個(gè)int a[MAXN][MAXN]，就可以獲得一個(gè)大小為MAXN×MAXN的方陣。在聲明時(shí)，兩維的大小不必相同。 提示3-4：用int a[MAXN][MAXN]生成一個(gè)整型的二維數(shù)組，其中MAXN和MAXN不必相等。這個(gè)數(shù)組共有MAXN×MAXN個(gè)元素，分別為a[0][0],a[0][1],?,a[0][MAXN-1],a[1][0] ,a[1][1],?,a[1][MAXN-1],?,a[MAXN-1][0],a[MAXN-1][1],?, a[MAXN-1][MAXN-1]。 第 54頁 第3章 數(shù)組和字符串 假設(shè)從1開始依次填這寫。設(shè)“筆”的坐標(biāo)為(x,y)，則一開始x=0，y=n-1，即第0行第n-1列（注意行列的范圍是0～n-1，沒有第n列）?！肮P”的移動(dòng)軌跡是：下、下、下、左、左、左、上、上、上、右、右、下、下、左、上?？傊?，先是下，到不能填了為止，然后是左，接著是上，最后是右。“不能填”是指再走就出界（例如4→5）或者再走就要走到以前填過的格子（例如12→13）。如果把所有格式初始化為0，就能很方便地加以判斷。 程序3-3 蛇形填數(shù) #include 提示3-5：可以利用C語言簡(jiǎn)潔的語法，但前提是保持代碼的可讀性。 提示3-6：在很多情況下，最好是在做一件事之前檢查是不是可以做，而不要做完再后悔。因?yàn)椤盎谄濉蓖脖容^麻煩。 說明：本程序?qū)τ谂cx+1 3.2 字 符 數(shù) 組 文本處理在計(jì)算機(jī)應(yīng)用中占有重要地位。在C語言中，字符串其實(shí)就是字符數(shù)組——可以像處理普通數(shù)組一樣處理字符串，只需要注意輸入輸出和字符串函數(shù)的使用。 例3-3 豎式問題。 找出所有形如abc*de（三位數(shù)乘以兩位數(shù)）的算式，使得在完整的豎式中，所有數(shù)字都屬于一個(gè)特定的數(shù)字集合。輸入數(shù)字集合（相鄰數(shù)字之間沒有空格），輸出所有豎式。每個(gè)豎式前應(yīng)有編號(hào)，之后應(yīng)有一個(gè)空行。最后輸出解的總數(shù)。具體格式見樣例輸出（為了便于觀察，豎式中的空格改用小數(shù)點(diǎn)顯示，但你的程序應(yīng)該輸出空格，而非小數(shù)點(diǎn)）。 樣例輸入：2357 樣例輸出： <1>..775 x..33----- 第 55頁 第3章 數(shù)組和字符串 .2325 2325.-----25575 The number of solutions=1 【分析】 本題的解題策略是嘗試所有的abc和de，判斷是否滿足條件。寫出如下的偽代碼： char s[20];int count = 0;scanf(“%s”, s);for(abc = 111;abc <= 999;abc++)for(de = 11;de <= 99;de++)if(“abc*de”是個(gè)合法的豎式){ printf(“<%d>n”, ++count);打印abc*de的豎式和其后的空行 count++;} printf(“The number of solutions = %dn”, count);說明：（1）char s[20]是一個(gè)定義字符數(shù)組的語句，scanf(“%s”,s)表示從鍵盤輸入一個(gè)字符串給字符數(shù)組s。 （2）char是“字符型”的意思，而字符是一種特殊的整數(shù)。每一個(gè)字符都有一個(gè)整數(shù)編碼，稱為ASCII碼。C語言中允許用直接的方法表示字符，還有以反斜線開頭的字符（轉(zhuǎn)義序列，Escape Sequence）。 （3）在stdlib.h中有一個(gè)函數(shù)atoi，它的函數(shù)原型如下： int atoi(char *s)它表示將字符串s中的內(nèi)容轉(zhuǎn)換成一個(gè)整型數(shù)返回，如字符串“1234”,則函數(shù)返回值是1234。 （4）在stdlib.h中有一個(gè)函數(shù)itoa，它的函數(shù)原型如下： char *itoa(int value,char *string,int radix)它表示將整數(shù)value轉(zhuǎn)換成字符串存入string, radix為轉(zhuǎn)換時(shí)所用基數(shù)(保存到字符串中的數(shù)據(jù)的進(jìn)制基數(shù) 2 8 10 16)，返回指向轉(zhuǎn)換后的字符串的指針。 例如，itoa(32,string,10)是將32變成十進(jìn)制數(shù)一個(gè)字符串“32”，并返回指向這個(gè)字符串的指針；itoa(32,string,16)是將32變成十進(jìn)制數(shù)一個(gè)字符串“20”，并返回指向這個(gè)字符串的指針。 提示3-7：C語言中的字符型用char表示，它實(shí)際存儲(chǔ)的是字符的ASCII碼。字符常量可以用單引號(hào)法表示。在語法上可以把字符當(dāng)作int型使用。 語句scanf(“%s”, s);表示讀入一個(gè)不含空格、TAB和回車符的字符串，存入字符數(shù)組s中，s前面沒有&符號(hào)。 提示3-8：在scanf(“%s”,s)中，不要在s前面加上&符號(hào)。如果是字符數(shù)組char s[MAXN] [MAXL],可以用scanf(“%s”,s[i])讀取第i個(gè)字符串。 接下來有兩個(gè)問題：判斷和輸出。先考慮輸出。首先計(jì)算第一行乘積x=abc*e，然后是第二行y=abc*d，最后是總乘積z=abc*de，然后一次性打印出來： printf(“%5dnX%4dn-----n%5dn%4dn-----n%5dnn”,abc,de,x,y,z);完整程序如下： 程序3-4 豎式問題 #include 第 56頁 第3章 數(shù)組和字符串 for(de = 11;de <= 99;de++){ x = abc*(de%10);y = abc*(de/10);z = abc*de;sprintf(buf, “%d%d%d%d%d”, abc, de, x, y, z);ok = 1;for(i = 0;i < strlen(buf);i++)if(strchr(s, buf[i])== NULL)ok = 0;if(ok){ printf(“<%d>n”, ++count);printf(“%5dnX%4dn-----n%5dn%4dn-----n%5dnn”,abc,de,x,y,z);} } printf(“The number of solutions = %dn”, count);return 0;} 說明：（1）sprintf函數(shù) sprintf是個(gè)變參函數(shù)，定義如下： int sprintf(char *buffer, const char *format [, argument]...);除了前兩個(gè)參數(shù)類型固定外，后面可以接任意多個(gè)參數(shù)。而它的精華，顯然就在第二個(gè)參數(shù)格式化字符串上。 此函數(shù)的功能是把格式化的數(shù)據(jù)寫入某個(gè)字符串，它的返回值是字符串長(zhǎng)度。包含此函數(shù)的頭文件是stdio.h。 例如，本程序中的sprintf(buf,“%d%d%d%d%d”,abc,de,x,y,z);語句的功能是將整數(shù)abcdexyx打印成字符串存儲(chǔ)在串buff中。 （2）strchr函數(shù) strchr函數(shù)定義如下： char *strchr(const char *s,char c);此函數(shù)的功能是查找字符串s中首次出現(xiàn)字符c的位置。它的返回值是返回首次出現(xiàn)c的位置的指針，如果s中不存在c則返回NULL。包含此函數(shù)的頭文件是string.h。 例如，本程序的if語句中strchr(s, buf[i])的功能是查找字符串s中首次出字符buf[i]的位置。如果strchr(s, buf[i])==NULL，則表明字符串s中沒有buf[i]的字符。 （3）sprintf函數(shù)、printf函數(shù)、fprintf函數(shù)的區(qū)別 printf輸出到屏幕，fprintf輸出到文件，而sprintf輸出到字符串。需要注意是應(yīng)該保證寫入的字符串有足夠的空間。 提示3-9：可以用sprintf把信息輸出到字符串，用法和printf、fprintf類似。但你應(yīng)當(dāng)保證字符串足夠大，可以容納輸出信息。 字符串的空間應(yīng)為字符個(gè)數(shù)加1，這是因?yàn)镃語言的字符串是以空字符'
第二篇：算法競(jìng)賽入門經(jīng)典授課教案第3章 數(shù)組和字符串