C語(yǔ)言程序設(shè)計(jì) 課件 第5章函數(shù)

《程序設(shè)計(jì)》1第5章函數(shù)《程序設(shè)計(jì)》2目錄5.1函數(shù)基礎(chǔ)知識(shí)5.2函數(shù)定義5.3函數(shù)調(diào)用5.4函數(shù)說(shuō)明5.5函數(shù)嵌套調(diào)用5.6遞歸函數(shù)基礎(chǔ)5.7命令行參數(shù)5.8局部變量和全局變量5.9函數(shù)程序設(shè)計(jì)實(shí)例5.10存儲(chǔ)類(lèi)5.11編譯預(yù)處理命令簡(jiǎn)介為什么要用函數(shù)（Function）?結(jié)構(gòu)化程序設(shè)計(jì)自頂向下逐步求精功能分解《程序設(shè)計(jì)》3為什么要用函數(shù)（Function）?用函數(shù)實(shí)現(xiàn)模塊化程序設(shè)計(jì)《程序設(shè)計(jì)》4函數(shù)swap：互換兩個(gè)變量值的C語(yǔ)言程序段voidswap(int*a,int*b)//互換兩個(gè)變量值{inttemp=*a;*a=*b;*b=temp;}在程序中需要互換兩個(gè)變量值時(shí)，就調(diào)用函數(shù)swap《程序設(shè)計(jì)》65.1函數(shù)基礎(chǔ)知識(shí)結(jié)構(gòu)化程序設(shè)計(jì)中，將復(fù)雜的功能分解成若干簡(jiǎn)單的子功能，并用函數(shù)實(shí)現(xiàn)子功能，用調(diào)用函數(shù)實(shí)現(xiàn)子功能要求函數(shù)是一個(gè)實(shí)現(xiàn)指定功能、邏輯上獨(dú)立的代碼段對(duì)函數(shù)使用者來(lái)說(shuō)，把它看作“黑盒”，只需知道要傳送給函數(shù)的數(shù)據(jù)（輸入），和函數(shù)執(zhí)行后能得到什么結(jié)果（輸出）函數(shù)還可以定義局部對(duì)象，使函數(shù)在邏輯上作為程序的一個(gè)相對(duì)獨(dú)立單位，不受主函數(shù)或其他函數(shù)對(duì)程序?qū)ο竺挠绊憽冻绦蛟O(shè)計(jì)》7從函數(shù)的形式看，函數(shù)分兩類(lèi)①無(wú)參函數(shù)在調(diào)用無(wú)參函數(shù)時(shí)，主調(diào)函數(shù)不向被調(diào)用函數(shù)傳遞數(shù)據(jù)。②有參函數(shù)在調(diào)用函數(shù)時(shí)，主調(diào)函數(shù)在調(diào)用被調(diào)用函數(shù)時(shí)，通過(guò)參數(shù)向被調(diào)用函數(shù)傳遞數(shù)據(jù)。函數(shù)間的關(guān)系一個(gè)C程序以main()函數(shù)作為程序的主函數(shù)。程序運(yùn)行時(shí)，從它開(kāi)始執(zhí)行；如果在main函數(shù)中調(diào)用其他函數(shù)，在調(diào)用后流程返回到main函數(shù)，在main函數(shù)中結(jié)束整個(gè)程序的運(yùn)行。所有函數(shù)都是平行的，即在定義函數(shù)時(shí)是分別進(jìn)行的，是互相獨(dú)立的。一個(gè)函數(shù)并不從屬于另一個(gè)函數(shù)，即函數(shù)不能嵌套定義。函數(shù)間可以互相調(diào)用，但不能調(diào)用main函數(shù)。main函數(shù)是被操作系統(tǒng)調(diào)用的?！冻绦蛟O(shè)計(jì)》8從用戶(hù)使用的角度看，函數(shù)有兩種①庫(kù)函數(shù)由系統(tǒng)提供的，用戶(hù)不必自己定義，可直接使用它們。不同的C語(yǔ)言編譯系統(tǒng)提供的庫(kù)函數(shù)的數(shù)量和功能會(huì)有一些不同，當(dāng)然許多基本的函數(shù)是共同的。②用戶(hù)自己定義的函數(shù)用以解決用戶(hù)專(zhuān)門(mén)需要的函數(shù)?！冻绦蛟O(shè)計(jì)》9《程序設(shè)計(jì)》10庫(kù)函數(shù)把一些公用的、基本的計(jì)算功能所對(duì)應(yīng)的函數(shù)集中起來(lái)，構(gòu)成一個(gè)庫(kù)，我們稱(chēng)之為函數(shù)庫(kù)，相應(yīng)的函數(shù)成為庫(kù)函數(shù)函數(shù)庫(kù)中的函數(shù)具有預(yù)先定義的、標(biāo)準(zhǔn)的輸入、輸入接口C語(yǔ)言中定義了一些基本的標(biāo)準(zhǔn)函數(shù)編程環(huán)境工具廠商（Microsoft、Borland等）往往提供更多的函數(shù)供編程者使用《程序設(shè)計(jì)》11庫(kù)函數(shù)（續(xù)）C語(yǔ)言使用頭文（headerfile，即*.h文件）對(duì)函數(shù)庫(kù)中的函數(shù)進(jìn)行定義和說(shuō)明函數(shù)庫(kù)中的函數(shù)經(jīng)編譯后，綁定在一起件，構(gòu)成一個(gè)庫(kù)文件（libraryfile，即*.lib文件）C程序調(diào)用C語(yǔ)言或者編程環(huán)境提供的函數(shù)時(shí)，要在程序中include相應(yīng)的頭文件；在產(chǎn)生執(zhí)行文件時(shí)，需要與庫(kù)文件中相應(yīng)的目標(biāo)函數(shù)代碼連接為了使用方便，C語(yǔ)言按功能分類(lèi)，提供了大量函數(shù)庫(kù)，每個(gè)函數(shù)庫(kù)都有自己的頭文件《程序設(shè)計(jì)》12庫(kù)函數(shù)的使用使用相應(yīng)庫(kù)函數(shù)的程序都要在使用之前寫(xiě)上包含其頭文件的預(yù)處理命令常用的頭文件stdio.h（輸入輸出庫(kù)函數(shù)）math.h、stdlib.h、float.h（數(shù)學(xué)庫(kù)函數(shù)）time.h（時(shí)間庫(kù)函數(shù)）ctype.h（字符分類(lèi)和轉(zhuǎn)換庫(kù)函數(shù)）string.h（內(nèi)存緩沖區(qū)和字符串處理庫(kù)函數(shù)）graphics.h（圖形處理庫(kù)函數(shù)）malloc.h、stdlib.h（內(nèi)存動(dòng)態(tài)分配庫(kù)函數(shù)）signal.h、process.h（進(jìn)程控制庫(kù)函數(shù)）《程序設(shè)計(jì)》135.2函數(shù)定義函數(shù)定義的一般形式為

類(lèi)型標(biāo)識(shí)符函數(shù)名(形式參數(shù)說(shuō)明表){

說(shuō)明和定義部分語(yǔ)句序列

}C語(yǔ)言要求，在程序中用到的所有函數(shù)，必須“先定義，后使用”。定義函數(shù)應(yīng)包括以下幾個(gè)內(nèi)容:(1)指定函數(shù)的名字，以便以后按名調(diào)用。(2)指定函數(shù)的類(lèi)型，即函數(shù)返回值的類(lèi)型。(3)指定函數(shù)的參數(shù)的名字和類(lèi)型，以便在調(diào)用函數(shù)時(shí)向它們傳遞數(shù)據(jù)。對(duì)無(wú)參函數(shù)不需要這項(xiàng)。(4)指定函數(shù)應(yīng)當(dāng)完成什么操作，也就是函數(shù)是做什么的，即函數(shù)的功能。這是最重要的，是在函數(shù)體中解決的?！冻绦蛟O(shè)計(jì)》14《程序設(shè)計(jì)》15函數(shù)定義（續(xù)）類(lèi)型標(biāo)識(shí)符用于標(biāo)識(shí)函數(shù)執(zhí)行結(jié)果返回值的類(lèi)型當(dāng)函數(shù)執(zhí)行不返回值時(shí)，習(xí)慣用void來(lái)標(biāo)記當(dāng)函數(shù)返回int型值時(shí)，類(lèi)型區(qū)分符int可以省略函數(shù)名是一個(gè)標(biāo)識(shí)符，一個(gè)C程序有且只有一個(gè)main()函數(shù)，其它的函數(shù)名可以隨意命名《程序設(shè)計(jì)》16函數(shù)定義（續(xù)）函數(shù)名之后括號(hào)內(nèi)的形式參數(shù)說(shuō)明表是按需要而定沒(méi)有形參的函數(shù)，也就沒(méi)有形參說(shuō)明表，常用void代之，但函數(shù)名之后的一對(duì)圓括號(hào)不可省略當(dāng)函數(shù)有多個(gè)形參時(shí)，形參說(shuō)明之間用逗號(hào)分隔，每個(gè)形參說(shuō)明指定形參的類(lèi)型和形參名《程序設(shè)計(jì)》17函數(shù)定義（續(xù)）最外層花括號(hào)“{”和“}”括住的部分是函數(shù)體在函數(shù)體的前面部分可有函數(shù)需要的程序?qū)ο蟮恼f(shuō)明和定義函數(shù)體內(nèi)定義的變量是局部變量，只能在函數(shù)體內(nèi)引用它們說(shuō)明和定義之后是由語(yǔ)句序列組成的執(zhí)行代碼《程序設(shè)計(jì)》18

【例5.2.1】求兩個(gè)實(shí)數(shù)中最小值的函數(shù)min()。求兩個(gè)數(shù)中最小值的函數(shù)min()doublemin(doublex,doubley)/*返回double型值，有兩個(gè)形參x，y，都為double型的*/{/*函數(shù)返回x和y中的小者的值*/returnx<y?x:y;}

return語(yǔ)句的執(zhí)行將結(jié)束函數(shù)的執(zhí)行

C語(yǔ)言的return語(yǔ)句有兩種形式：

return;用于不返回值的函數(shù)體中

return表達(dá)式；用于有返回值的函數(shù)體中《程序設(shè)計(jì)》19【例5.2.2】求兩個(gè)正整數(shù)最大公因子的函數(shù)gcd()。求兩個(gè)正整數(shù)最大公因子的函數(shù)gcd()兩個(gè)正整數(shù)a和b的最大公因子有性質(zhì)：gcd(a,b)=gcd(a-b,b),如a>b；gcd(a,b)=gcd(a,b-a),如a<b；gcd(a,b)=a，如a=b。《程序設(shè)計(jì)》20intgcd(inta,intb){while(a!=b)if(a>b)a-=b;elseb-=a;returna;}第1解法第2解法：輾轉(zhuǎn)相除法計(jì)算27和24的最大公因子27除以24，余數(shù)324除以3，整除最大公因子：3計(jì)算27和25的最大公因子27除以25，余數(shù)225除以2，余數(shù)12除以1，整除最大公因子：1《程序設(shè)計(jì)》22計(jì)算兩個(gè)正整數(shù)a和b（設(shè)a

b）的最大公因子的輾轉(zhuǎn)相除法算法:[求余數(shù)]求a除b的余數(shù)r[判結(jié)束]如r等于0，b為最大公約數(shù)[替換]用b置a，r置b，并回到步驟[求余數(shù)]第2解法：輾轉(zhuǎn)相除法《程序設(shè)計(jì)》23

intgcd(inta,intb){intr;while(1){if((r=a%b)==0)break;a=b;b=r;}returnb;}《程序設(shè)計(jì)》24

intgcd(inta,intb){intr=a;do{a=b;b=r;r=a%b;}while(r);returnb;}《程序設(shè)計(jì)》25函數(shù)定義（續(xù)）C語(yǔ)言也允許在函數(shù)名后的圓括號(hào)內(nèi)只給出各形參的名，隨后才指定各形參的類(lèi)型，但這種寫(xiě)法在C++中已不允許doublemin(x,y)doublex,y;{returnx<y?x:y;}C語(yǔ)言還允許函數(shù)體為空的函數(shù)dummy()/*或dummy(void)*/{}《程序設(shè)計(jì)》265.3函數(shù)調(diào)用函數(shù)被定義以后，凡要實(shí)現(xiàn)函數(shù)功能的地方，就可簡(jiǎn)單地通過(guò)函數(shù)調(diào)用來(lái)完成函數(shù)調(diào)用的一般形式為函數(shù)名（實(shí)際參數(shù)表）print_star(); //調(diào)用無(wú)參函數(shù)c=max(a,b); //調(diào)用有參函數(shù)函數(shù)調(diào)用（續(xù)）1.函數(shù)調(diào)用語(yǔ)句把函數(shù)調(diào)用單獨(dú)作為一個(gè)語(yǔ)句。如printf_star();這時(shí)不要求函數(shù)帶回值，只要求函數(shù)完成一定的操作。2.函數(shù)表達(dá)式函數(shù)調(diào)用出現(xiàn)在另一個(gè)表達(dá)式中，如c=max(a,b);

這時(shí)要求函數(shù)帶回一個(gè)確定的值以參加表達(dá)式的運(yùn)算。3.函數(shù)參數(shù)函數(shù)調(diào)用作為另一個(gè)函數(shù)調(diào)用時(shí)的實(shí)參。如m=max(a,max(b,c));，又如:printf(″%d″,max(a,b));《程序設(shè)計(jì)》27形式參數(shù)和實(shí)際參數(shù)在調(diào)用有參函數(shù)時(shí)，主調(diào)函數(shù)和被調(diào)用函數(shù)之間有數(shù)據(jù)傳遞關(guān)系。在定義函數(shù)時(shí)函數(shù)名后面括號(hào)中的變量名稱(chēng)為“形式參數(shù)”（簡(jiǎn)稱(chēng)“形參”）或“虛擬參數(shù)”。在主調(diào)函數(shù)中調(diào)用一個(gè)函數(shù)時(shí)，函數(shù)名后面括號(hào)中的參數(shù)稱(chēng)為“實(shí)際參數(shù)”（簡(jiǎn)稱(chēng)“實(shí)參”）。實(shí)際參數(shù)可以是常量、變量或表達(dá)式，但要求它們有確定的值。實(shí)參與形參的類(lèi)型應(yīng)相同或賦值兼容。賦值兼容是指實(shí)參與形參類(lèi)型不同時(shí)能按不同類(lèi)型數(shù)值的賦值規(guī)則進(jìn)行轉(zhuǎn)換。《程序設(shè)計(jì)》28《程序設(shè)計(jì)》29函數(shù)調(diào)用有兩種方式傳值調(diào)用（callbyvalue）把實(shí)參的值傳給被調(diào)用函數(shù)的參數(shù)（形參）。這時(shí)，被調(diào)用函數(shù)對(duì)參數(shù)的改變，不影響調(diào)用函數(shù)實(shí)參的原始值傳引用調(diào)用（callbyreference）把實(shí)參的地址傳給被調(diào)用函數(shù)的參數(shù)（形參）地址。這時(shí)，被調(diào)用函數(shù)對(duì)參數(shù)的改變，將影響到調(diào)用函數(shù)實(shí)參的原始值傳值調(diào)用實(shí)例把實(shí)參的值傳給被調(diào)用函數(shù)的參數(shù)（形參）。這時(shí)，被調(diào)用函數(shù)對(duì)參數(shù)的改變，不影響調(diào)用函數(shù)實(shí)參的原始值。對(duì)doublemin(doublex,doubley)的函數(shù)調(diào)用w=min(u,v);函數(shù)調(diào)用min(u,v)就是對(duì)函數(shù)min()的調(diào)用，它提供了兩個(gè)實(shí)參u和v，分別對(duì)應(yīng)形參x和y【例5.3.1】GCD試題來(lái)源：WorldFinalsWarmupI，2008在線測(cè)試：UVA11417輸入輸入最多會(huì)有100行。每行給出一個(gè)整數(shù)N（1＜N＜501），N的含義在上面的試題描述中給出。輸入以在一行中給出0終止，這個(gè)0不用進(jìn)行處理。輸出對(duì)于輸入的每一行，輸出一行，給出相應(yīng)于N的G值。試題解析基于【例5.2.2】求兩個(gè)正整數(shù)最大公因子的函數(shù)gcd()，根據(jù)題意，編寫(xiě)程序。在參考程序中，采用第1種計(jì)算最大公因子的解法，給出函數(shù)intgcd(inta,intb)。在主函數(shù)intmain()中調(diào)用gcd(j,i)，函數(shù)調(diào)用為傳值調(diào)用，把實(shí)參j和i的值分別傳給被調(diào)用函數(shù)的對(duì)應(yīng)形參a和b。參考程序（求解GCD的第1種方法）#include<stdio.h>intgcd(inta,intb){while(a!=b){if(a>b)a-=b;elseb-=a;}returna;}intmain(){intn;while(scanf("%d",&n)&&n){intg=0;for(inti=1;i<n;i++)for(intj=i+1;j<=n;j++)g+=gcd(j,i);printf("%d\n",g);}return0;}傳引用調(diào)用（callbyreference）把實(shí)參的地址傳給被調(diào)用函數(shù)的參數(shù)（形參）地址。這時(shí)，被調(diào)用函數(shù)對(duì)參數(shù)的改變，將影響到調(diào)用函數(shù)實(shí)參的原始值。函數(shù)voidswap(int*a,int*b)，互換兩個(gè)指針變量的變量值?！纠?.3.2】同【例4.2.5.1】Who'sintheMiddle在實(shí)現(xiàn)冒泡排序算法的參考程序中，a[j]與a[j+1]交換的程序段用函數(shù)voidswap(int*a,int*b)實(shí)現(xiàn)，實(shí)參變量a[j]與a[j+1]的地址傳給形參，以實(shí)現(xiàn)a[j]與a[j+1]的互換。#include<stdio.h>voidswap(int*a,int*b)//互換兩個(gè)變量值{inttemp=*a;*a=*b;*b=temp;}intmain(){inta[10010],N,i,j,temp;scanf("%d",&N);//輸入第1行整數(shù)N，表示N頭奶牛for(i=0;i<N;i++)//N頭奶牛的產(chǎn)奶量scanf("%d",&a[i]);for(i=0;i<N-1;i++)//冒泡排序N頭奶牛產(chǎn)奶量 for(j=0;j<N-i-1;j++) if(a[j]>a[j+1])

swap(&a[j],&a[j+1]); printf("%d\n",a[N/2]);//輸出排序后的中間元素return0; }《程序設(shè)計(jì)》41函數(shù)調(diào)用（續(xù)）如果調(diào)用無(wú)形參的函數(shù)，這時(shí)函數(shù)的調(diào)用形式變?yōu)楹瘮?shù)名()；其中函數(shù)名之后的一對(duì)圓括號(hào)是不能省略的

《程序設(shè)計(jì)》42函數(shù)調(diào)用（續(xù)）按函數(shù)調(diào)用在程序中的作用，有兩種不同類(lèi)型的應(yīng)用函數(shù)調(diào)用只是利用函數(shù)所完成的功能。此時(shí)，將函數(shù)調(diào)用作為一個(gè)獨(dú)立的語(yǔ)句。這種應(yīng)用不要求或無(wú)視函數(shù)的返回值如程序中經(jīng)常使用的調(diào)用格式輸入函數(shù)scanf()和格式輸出函數(shù)printf()等。函數(shù)調(diào)用是利用函數(shù)的返回值?；蛴眠@返回值繼續(xù)進(jìn)行表達(dá)式的計(jì)算，或輸出函數(shù)返回值等【例5.3.3】Addbricksinthewall試題來(lái)源：IVLocalContestinMurcia2006在線測(cè)試：UVA11040本題是一個(gè)添加數(shù)的問(wèn)題。給出一面三角形的墻，如圖所示。最上面的一行是第一行，最下面的一行是第9行，墻一共有9行，第i行恰好有i塊磚。有些磚被標(biāo)識(shí)著整數(shù)，而另一些磚則沒(méi)有被標(biāo)識(shí)整數(shù)。被標(biāo)識(shí)著整數(shù)的磚塊僅出現(xiàn)在奇數(shù)行上，并且它們?cè)谠撔兄形挥谄鏀?shù)的位置。本題要求您為每一塊沒(méi)有被標(biāo)識(shí)整數(shù)的磚找一個(gè)合適的整數(shù)來(lái)標(biāo)識(shí)，標(biāo)識(shí)整數(shù)的規(guī)則為：每一塊磚上被標(biāo)識(shí)的整數(shù)是其下面兩塊磚上的整數(shù)的和。顯然，這條規(guī)則對(duì)第9行不適用。輸入輸入的第一行給出一個(gè)整數(shù)N，表示測(cè)試用例的數(shù)量。在這一行之后，給出測(cè)試用例。每個(gè)測(cè)試用例5行；如上所述，這5行從上到下對(duì)應(yīng)于墻的奇數(shù)行；第i行給出墻上的第i行上的奇數(shù)塊磚（即標(biāo)識(shí)著整數(shù)的磚）相對(duì)應(yīng)的整數(shù)，從左到右給出整數(shù)，整數(shù)間用一個(gè)空格分隔。本題設(shè)定每個(gè)測(cè)試用例都是正確的，也就是說(shuō)，存在測(cè)試用例所描述的問(wèn)題的解決方案。輸出對(duì)于每個(gè)測(cè)試用例，輸出9行，給出墻上所有磚塊上標(biāo)識(shí)的整數(shù)。因此，第i行從左到右給出墻的第i行的i塊磚所標(biāo)識(shí)的整數(shù)，整數(shù)間用一個(gè)空格分隔。給出兩個(gè)樣例輸入輸出，其中第一個(gè)樣例輸入輸出對(duì)應(yīng)圖5.3-1給出的墻。試題解析對(duì)于本題，采用機(jī)理分析法，以順向思維方式，分析試題描述，順推出求解算法。由于“每一塊磚上被標(biāo)識(shí)的整數(shù)是其下面兩塊磚上的整數(shù)的和”，所以，對(duì)于三角形的墻中的任何一個(gè)三角形：[c][a+x][x+b][a][x][b]其中，位于奇數(shù)行奇數(shù)位置的a,b,c已知，則有c=(a+x)+(b+x)，則x=(c-a-b)/2；又由于“本題設(shè)定每個(gè)測(cè)試用例都是正確的”，所以，(c-a-b)除以2，余數(shù)一定是0。首先，計(jì)算出位于奇數(shù)行偶數(shù)位置的元素值x；然后，計(jì)算出位于偶數(shù)行的元素值。在參考程序中，三角形的墻用二維數(shù)組“inta[9][9]”表示?！癷nta[9][9]”在函數(shù)的外部定義，稱(chēng)為外部變量，也稱(chēng)為全局變量，它的有效范圍為從定義變量的位置開(kāi)始到本程序文件的末尾。輸入測(cè)試用例，對(duì)二維數(shù)組奇數(shù)行奇數(shù)位置的元素賦值。計(jì)算奇數(shù)行偶數(shù)位置的元素；計(jì)算偶數(shù)行；用無(wú)形參、無(wú)返回值的函數(shù)print()輸出三角形。參考程序#include<stdio.h>inta[9][9];voidprint()//無(wú)形參、無(wú)返回值的函數(shù)，輸出三角形{inti,j;for(i=0;i<9;i++){for(j=0;j<=i;j++){if(j)printf("");//整數(shù)間用一個(gè)空格分隔printf("%d",a[i][j]);}printf("\n");}}intmain(){intt,i,j;//t:測(cè)試用例數(shù)，i,j：循環(huán)變量scanf("%d",&t);//輸入測(cè)試用例數(shù)while(t--){//每次循環(huán)處理一個(gè)測(cè)試用例for(i=0;i<9;i+=2)//輸入當(dāng)前測(cè)試用例，二維數(shù)組奇數(shù)行奇數(shù)位置賦值for(j=0;j<=i;j+=2)scanf("%d",&a[i][j]);for(inti=8;i>0;i-=2)//計(jì)算奇數(shù)行偶數(shù)位置的元素for(intj=1;j<i;j+=2)a[i][j]=(a[i-2][j-1]-a[i][j-1]-a[i][j+1])/2;for(inti=1;i<9;i+=2)//計(jì)算偶數(shù)行for(intj=0;j<=i;j++)a[i][j]=a[i+1][j]+a[i+1][j+1];print();//無(wú)形參、無(wú)返回值的函數(shù)print()，輸出三角形}return0;}函數(shù)調(diào)用的兩種不同類(lèi)型的應(yīng)用函數(shù)調(diào)用只是利用函數(shù)所完成的功能函數(shù)調(diào)用被當(dāng)作一個(gè)獨(dú)立的語(yǔ)句來(lái)處理。這種應(yīng)用不要求或無(wú)視函數(shù)的返回值。scanf()和printf()；【例5.3.2】voidswap(int*a,int*b)；【例5.3.3】voidprint()。函數(shù)調(diào)用是利用函數(shù)的返回值。或用返回值繼續(xù)進(jìn)行表達(dá)式的計(jì)算，或輸出函數(shù)返回值等。【例5.3.1】中的函數(shù)intgcd(inta,intb)，返回正整數(shù)a和b的最大公因子。《程序設(shè)計(jì)》55函數(shù)調(diào)用的執(zhí)行過(guò)程為形參分配內(nèi)存空間計(jì)算實(shí)參表達(dá)式的值，并將值賦給對(duì)應(yīng)的形參為函數(shù)的局部變量分配內(nèi)存空間執(zhí)行函數(shù)體內(nèi)的語(yǔ)句序列函數(shù)體執(zhí)行完，或執(zhí)行了return語(yǔ)句后，釋放為這次函數(shù)調(diào)用分配的全部?jī)?nèi)存空間將函數(shù)值（如果有）返回到函數(shù)調(diào)用處繼續(xù)執(zhí)行《程序設(shè)計(jì)》56#include<stdio.h>doublex,y,d,min(double,double);voidmain(){printf(“Enterx,y.\n”);scanf(“%lf%lf”,&x,&y);d=min(x,y);printf(“MIN(%.3f,%.3f)=%.3f\n”,x,y,d);}doublemin(doublea,doubleb){doubletemp;temp=a>b?b:a;returntemp;}《程序設(shè)計(jì)》57對(duì)函數(shù)調(diào)用的說(shuō)明當(dāng)函數(shù)執(zhí)行return語(yǔ)句或執(zhí)行完函數(shù)體的語(yǔ)句序列后，函數(shù)的這次調(diào)用就執(zhí)行結(jié)束，隨之將控制返回到函數(shù)調(diào)用處繼續(xù)執(zhí)行函數(shù)的返回值是通過(guò)執(zhí)行return語(yǔ)句時(shí)，計(jì)算return之后的表達(dá)式值而獲得的。如果函數(shù)不提供返回值，則return語(yǔ)句不應(yīng)包含表達(dá)式。如果函數(shù)有返回值，則應(yīng)有確定的類(lèi)型，并在函數(shù)定義時(shí)指明。若函數(shù)定義時(shí)不指明返回值類(lèi)型，且函數(shù)有返回值，C語(yǔ)言約定該函數(shù)的返回值類(lèi)型為int型《程序設(shè)計(jì)》58對(duì)函數(shù)調(diào)用的說(shuō)明（續(xù)）為了明確指明函數(shù)不提供返回值，建議在函數(shù)定義時(shí)，在函數(shù)名之前寫(xiě)上void。并在這樣的函數(shù)體內(nèi)，所有的return語(yǔ)句都不應(yīng)該帶表達(dá)式當(dāng)函數(shù)執(zhí)行不帶表達(dá)式的return語(yǔ)句返回時(shí)，函數(shù)并不是一定不帶回值，而是返回一個(gè)不確定的值。這樣的函數(shù)調(diào)用不應(yīng)該利用函數(shù)返回值進(jìn)行再計(jì)算，否則會(huì)產(chǎn)生錯(cuò)誤結(jié)果函數(shù)定義中的return語(yǔ)句的表達(dá)式類(lèi)型應(yīng)與函數(shù)定義中指明的返回值類(lèi)型相一致。如果return語(yǔ)句中的表達(dá)式類(lèi)型與函數(shù)定義指明的返回值類(lèi)型不一致時(shí)，對(duì)于是基本類(lèi)型情況，則以函數(shù)的返回值類(lèi)型為準(zhǔn)，系統(tǒng)會(huì)自動(dòng)進(jìn)行類(lèi)型轉(zhuǎn)換《程序設(shè)計(jì)》59對(duì)函數(shù)調(diào)用的說(shuō)明（續(xù)）在函數(shù)未被調(diào)用時(shí)，函數(shù)定義中的形參和函數(shù)體中定義的局部變量并不占用存儲(chǔ)單元在函數(shù)定義中，必須為函數(shù)的形參指定數(shù)據(jù)類(lèi)型函數(shù)體中所使用的形參的初值是由函數(shù)調(diào)用時(shí)對(duì)應(yīng)的實(shí)參表達(dá)式給定的C語(yǔ)言規(guī)定，實(shí)參表達(dá)式對(duì)形參的數(shù)據(jù)傳遞是“值傳遞”的，即單向傳遞對(duì)于有多個(gè)實(shí)參的函數(shù)調(diào)用情況，C語(yǔ)言不規(guī)定實(shí)參的求值次序《程序設(shè)計(jì)》605.4函數(shù)形參函數(shù)設(shè)置形參的目的是讓函數(shù)被調(diào)用時(shí)，能從調(diào)用處獲得數(shù)據(jù)或指針信息C語(yǔ)言關(guān)于函數(shù)形參遵守以下規(guī)定函數(shù)調(diào)用時(shí)，形參從實(shí)參獲得初值函數(shù)形參可看作函數(shù)內(nèi)部的局部變量，函數(shù)體內(nèi)對(duì)形參的修改不會(huì)影響實(shí)參本身函數(shù)形參的作用由形參的類(lèi)型確定基本類(lèi)型、指針類(lèi)型、數(shù)組類(lèi)型當(dāng)函數(shù)的形參是某種指針類(lèi)型或數(shù)組類(lèi)型時(shí)，形參從實(shí)參處得到某環(huán)境變量的指針，函數(shù)體就能通過(guò)指針形參間接引用環(huán)境變量，能改變環(huán)境變量的值《程序設(shè)計(jì)》615.4函數(shù)說(shuō)明為什么要對(duì)函數(shù)進(jìn)行說(shuō)明？一個(gè)函數(shù)要調(diào)用另一個(gè)函數(shù)，應(yīng)知道被調(diào)用函數(shù)的有關(guān)如何正確調(diào)用的一些重要信息編譯程序根據(jù)這些信息檢查調(diào)用的正確性。對(duì)不正確的調(diào)用給出錯(cuò)誤信息，對(duì)正確的調(diào)用編譯出實(shí)現(xiàn)的機(jī)器代碼《程序設(shè)計(jì)》62調(diào)用函數(shù)與被調(diào)用函數(shù)調(diào)用函數(shù)與被調(diào)用函數(shù)之間在程序正文中可能會(huì)存在以下幾種情況調(diào)用同一程序文件中前面已定義的函數(shù)調(diào)用處于同一程序文件后面定義的函數(shù)調(diào)用別的程序文件中定義的函數(shù)對(duì)于第一種情況，在函數(shù)調(diào)用處，被調(diào)用函數(shù)的詳細(xì)信息已被編譯程序所接受對(duì)于后兩種情況，這時(shí)因被調(diào)用函數(shù)的信息還未被編譯程序所接受，不能檢查函數(shù)調(diào)用的正確性，所以在調(diào)用之前需對(duì)被調(diào)用函數(shù)有關(guān)調(diào)用的一些信息作出說(shuō)明《程序設(shè)計(jì)》63函數(shù)說(shuō)明形式函數(shù)與調(diào)用有關(guān)的信息包括函數(shù)的返回值類(lèi)型、函數(shù)名和函數(shù)有關(guān)形參的個(gè)數(shù)及其類(lèi)型等只給出函數(shù)的調(diào)用信息稱(chēng)作函數(shù)說(shuō)明函數(shù)說(shuō)明的一般形式為

類(lèi)型標(biāo)識(shí)符(形參類(lèi)型表);其中，形參類(lèi)型表順序給出各形參的類(lèi)型。形參類(lèi)型表可以為空。為了強(qiáng)調(diào)函數(shù)沒(méi)有形參，空形參類(lèi)型表可以寫(xiě)作void函數(shù)說(shuō)明對(duì)要定義的函數(shù)名及其返回值類(lèi)型和各形參的類(lèi)型作說(shuō)明，以便讓編譯程序預(yù)先知道該標(biāo)識(shí)符是函數(shù)名、它的返回值的類(lèi)型和它的形參個(gè)數(shù)及各形參的類(lèi)型《程序設(shè)計(jì)》64函數(shù)說(shuō)明示例#include<stdio.h>voidmain(){doublepower(double,int)，x;intn;printf("Enterxandn.\n");scanf("%lf%d",&x,&n);printf("power(%f,%d)=%f\n",x,n,power(x,n));}doublepower(doublex,intn){/*xn=x*xn-1,當(dāng)n為奇數(shù);或xn=(x2)n/2,當(dāng)n為偶數(shù)*/doublez,y;z=1.0;y=x;while(n>0){while(n%2==0){n/=2;y*=y;}n--;z*=y;}returnz;}《程序設(shè)計(jì)》65程序有函數(shù)說(shuō)明的兩種情況-1被調(diào)用函數(shù)是庫(kù)函數(shù)。程序需使用預(yù)處理命令#include將包含有庫(kù)函數(shù)的模型、它們所使用的常量、宏定義、數(shù)據(jù)類(lèi)型定義等信息的文件包含進(jìn)來(lái)習(xí)慣稱(chēng)文件名以“.h”為后綴的文件為頭文件(headerfile)在頭文件中通常包含宏定義、數(shù)據(jù)類(lèi)型說(shuō)明和定義、公共變量的外部說(shuō)明等在大型C程序設(shè)計(jì)中，用戶(hù)程序也會(huì)有自己的頭文件，如有頭文件名為d_type.h使用包含預(yù)處理命令#include"d_type.h"《程序設(shè)計(jì)》66程序有函數(shù)說(shuō)明的兩種情況-2調(diào)用同一程序文件中后面定義的函數(shù)，或是調(diào)用別的程序文件中定義的函數(shù)，應(yīng)在調(diào)用函數(shù)之前對(duì)被調(diào)用函數(shù)作函數(shù)說(shuō)明在C語(yǔ)言中，如被調(diào)用函數(shù)的返回值是整型或字符型，也可以不對(duì)其返回類(lèi)型作說(shuō)明。因編譯系統(tǒng)發(fā)現(xiàn)程序要調(diào)用一個(gè)還未被定義或說(shuō)明的函數(shù)時(shí)，就假定被調(diào)用函數(shù)的返回值是整型的，而字符型又是與整型相通的。但習(xí)慣仍給這樣的函數(shù)作說(shuō)明5.5函數(shù)嵌套調(diào)用一個(gè)函數(shù)為完成其的復(fù)雜工作，可以調(diào)用其他函數(shù)。從主函數(shù)main()出發(fā)，main()調(diào)用a函數(shù)，a函數(shù)又調(diào)用b函數(shù)。這樣從主函數(shù)出發(fā)，形成一個(gè)函數(shù)調(diào)用鏈，稱(chēng)為函數(shù)嵌套調(diào)用（nestedcall）。函數(shù)嵌套調(diào)用時(shí)，先被調(diào)用的函數(shù)后返回。如圖，待b函數(shù)完成計(jì)算返回后，a函數(shù)繼續(xù)計(jì)算（可能還要調(diào)用其他函數(shù)），待a函數(shù)計(jì)算完成，才返回到主函數(shù)main()?！纠?.5.1】HowManyKnights試題來(lái)源：ACM-ICPCNorthCentralRegionals1998在線測(cè)試：UVA696國(guó)際象棋是一種在棋盤(pán)上進(jìn)行的游戲。國(guó)際象棋的棋盤(pán)是一個(gè)由小方格組成的正方形，馬（knight）是國(guó)際象棋中的棋子。對(duì)于馬，每步棋攻擊距離其位置兩行一列的棋子，或者距離其位置一行兩列的棋子。如圖所示，標(biāo)記為N的小方格表示馬的位置，標(biāo)記為X的小方格表示走一步棋馬可以攻擊到的小方格。在本題中，給出一個(gè)m行n列的棋盤(pán)，請(qǐng)您計(jì)算最多能放多少個(gè)馬，使得這些馬彼此之間不會(huì)互相攻擊？m和n都不大于500。輸入輸入給出若干對(duì)m和n的值，最后以?xún)蓚€(gè)0標(biāo)識(shí)輸入結(jié)束。輸出對(duì)于每個(gè)輸入對(duì)，輸出棋盤(pán)的行數(shù)和列數(shù)，以及最多能放多少個(gè)馬的個(gè)數(shù)。試題解析對(duì)于本題，采用統(tǒng)計(jì)分析法，以逆向思維方式，從分析部分解出發(fā)，倒推出求解算法。設(shè)m<n，否則m與n互換。如果m=1，即棋盤(pán)只有一行，每個(gè)小方格放上馬，這些馬彼此之間都不會(huì)互相攻擊，所以最多可以放n個(gè)馬。如圖所示。如果m=2，即棋盤(pán)有兩行，那么以2

4為單位將棋盤(pán)劃分成的若干部分，每個(gè)部分最多能放4個(gè)馬，則2

n的棋盤(pán)最多可以放n/4*4+(n%4>=2?4:n%4*2)個(gè)馬。如圖所示：如果m

3，因?yàn)閲?guó)際象棋棋盤(pán)是由黑白（深色與淺色）相間的小方格組成，如圖所示。如果將馬間隔擺放，也就是，只在黑色小方格或者只在白色小方格上放置馬，則這些馬彼此之間都不會(huì)互相攻擊；此時(shí)，如果在另一顏色的小方格上擺放馬，則會(huì)有互相攻擊。以5

5的棋盤(pán)為例，馬被放置如圖。對(duì)于m

n的棋盤(pán)，將馬間隔擺放，則通過(guò)對(duì)部分解的求解，可以推導(dǎo)出擺放數(shù)為(m

n+1)/2。在參考程序中，函數(shù)intcal(intm,intn)用于計(jì)算m

n的棋盤(pán)最多能放多少個(gè)馬，而函數(shù)voidswap(int*a,int*b)則如前所述，用于兩個(gè)變量值的互換。在主函數(shù)main()中，每輸入一個(gè)測(cè)試用例，就調(diào)用函數(shù)cal(intm,intn)，計(jì)算m

n的棋盤(pán)最多能放多少個(gè)馬，然后輸出結(jié)果。在函數(shù)cal(intm,intn)中，如果n<m，則又調(diào)用函數(shù)swap(int*a,int*b)，對(duì)m與n進(jìn)行互換。在參考程序中，函數(shù)調(diào)用鏈為從主函數(shù)main()出發(fā)，調(diào)用函數(shù)cal(intm,intn)；而函數(shù)cal(intm,intn)又調(diào)用函數(shù)swap(int*a,int*b)；在swap(int*a,int*b)計(jì)算完成之后，返回cal(intm,intn)；在cal(intm,intn)計(jì)算完成之后，返回主函數(shù)main()。參考程序#include<stdio.h>voidswap(int*a,int*b)//互換兩個(gè)變量值{inttemp=*a;*a=*b;*b=temp;}intcal(intm,intn)//計(jì)算m

n的棋盤(pán)最多能放多少個(gè)馬{if(n<m)swap(&m,&n);if(m==1)returnn;elseif(m==2)returnn/4*4+(n%4>=2?4:n%4*2);elsereturn(m*n+1)/2;}intmain(){intm,n;while(scanf("%d%d",&m,&n)!=EOF&&(m||n))printf("%dknightsmaybeplacedona%drow%dcolumnboard.\n",cal(m,n),m,n);return0;}《程序設(shè)計(jì)》845.6遞歸函數(shù)基礎(chǔ)遞歸的定義若一個(gè)對(duì)象部分地包含它自己，或用它自己給自己定義，則稱(chēng)這個(gè)對(duì)象是遞歸的若一個(gè)函數(shù)直接地或間接地調(diào)用自己，則稱(chēng)這個(gè)函數(shù)是遞歸函數(shù)(recursivefunction)在以下三種情況下，常常用到遞歸方法定義是遞歸的數(shù)據(jù)結(jié)構(gòu)是遞歸的問(wèn)題的解法是遞歸的《程序設(shè)計(jì)》85【例5.6.1】對(duì)于自然數(shù)n，計(jì)算階乘n!用循環(huán)實(shí)現(xiàn)階乘計(jì)算的函數(shù)

longfac(intn){longs;inti;for(s=1L,i=1;i<=n;i++)s*=i;returns;}用遞歸實(shí)現(xiàn)階乘計(jì)算函數(shù)求解階乘函數(shù)的遞歸算法

longfac(intn

){if(

n==0)

return1L;elsereturn(long)n*fac(n-1);}階乘函數(shù):從【例5.6.1】可以得出：基于遞歸的定義給出遞歸函數(shù)；要有遞歸的邊界條件（遞歸的結(jié)束條件）；遞歸的過(guò)程則是向遞歸的邊界條件不斷逼近。fac(3)

的執(zhí)行流程（函數(shù)調(diào)用鏈）《程序設(shè)計(jì)》88fac(0)=1稱(chēng)之為遞歸邊界。fac(3)→fac(2)→fac(1)→fac(0)：遞歸過(guò)程；fac(0)→fac(1)→fac(2)→fac(3)：回代過(guò)程；fac(0)=1回代給fac(1)，fac(1)的值回代給fac(2)，…，直至求出fac(3)=6【例5.6.2】【例5.2.2】求兩個(gè)正整數(shù)最大公因子的函數(shù)gcd()遞歸定義遞歸函數(shù)gcd()intgcd(inta,intb)

{

if(a>b)

returngcd(a-b,b);

elseif(a<b)

returngcd(a,b-a);

else

returna;

}“輾轉(zhuǎn)相除法”

遞歸函數(shù)gcd()intgcd(inta,intb){returnb==0?a:gcd(b,a%b);}【例5.6.3】放蘋(píng)果試題來(lái)源：lwx@POJ在線測(cè)試：POJ1664把m個(gè)同樣的蘋(píng)果放在n個(gè)同樣的盤(pán)子里，允許有的盤(pán)子空著不放，問(wèn)共有多少種不同的分法？（用k表示）5，1，1和1，5，1是同一種分法。輸入第一行是測(cè)試用例的數(shù)目t（0

t

20）。以下每行均包含二個(gè)整數(shù)m和n，以空格分開(kāi)，1

m,n

10。輸出對(duì)輸入的每個(gè)測(cè)試用例m和n，用一行輸出相應(yīng)的k。試題解析設(shè)f(m,n)是m個(gè)同樣的蘋(píng)果放在n個(gè)同樣的盤(pán)子里的分法的數(shù)目，遞歸定義如下：（1）n>m：則至少有n-m個(gè)盤(pán)子會(huì)空著，去掉這n-m個(gè)盤(pán)子對(duì)放蘋(píng)果方法數(shù)不會(huì)產(chǎn)生影響；即f(m,n)=f(m,m)；（2）n

m：不同的放法可以分成兩類(lèi)：至少有一個(gè)盤(pán)子沒(méi)有放蘋(píng)果，即，f(m,n)=f(m,n-1)；所有盤(pán)子里都有蘋(píng)果，如果從每個(gè)盤(pán)子里拿走一個(gè)蘋(píng)果，不會(huì)影響分法的數(shù)目，即，f(m,n)=f(m-n,n)；所以，當(dāng)n

m時(shí)，根據(jù)加法原理，放蘋(píng)果的分法數(shù)目等于上述兩者的和，即，f(m,n)=f(m,n-1)+f(m-n,n)。對(duì)f(m,n)的遞歸邊界分析如下：（1）n==1時(shí)，所有蘋(píng)果就都必須放在一個(gè)盤(pán)子里，所以f(m,n)返回１；（2）m==0時(shí)，沒(méi)有蘋(píng)果可放，定義為１種放法，f(m,n)返回１；遞歸過(guò)程向遞歸邊界逼近：n減少，向遞歸邊界逼近，最終到達(dá)遞歸邊界n==1；m減少，當(dāng)n>m時(shí)，f(m,n)返回f(m,m)，最終到達(dá)遞歸邊界m==0。參考程序#include<stdio.h>intf(intm,intn)//遞歸函數(shù)：計(jì)算m個(gè)同樣的蘋(píng)果放在n個(gè)同樣的盤(pán)子里的分法數(shù){ if(n==1||m==0)//處理遞歸邊界 return1; if(m<n)//處理情況n>m returnf(m,m); else//處理情況n

m returnf(m,n-1)+f(m-n,n);}intmain(){ intt,m,n;//t：測(cè)試用例數(shù)，m和n：蘋(píng)果數(shù)和盤(pán)子數(shù) scanf("%d",&t);//輸入測(cè)試用例數(shù) while(t--)//依次處理每個(gè)測(cè)試用例 { scanf("%d%d",&m,&n);//輸入蘋(píng)果數(shù)和盤(pán)子數(shù) printf("%d\n",f(m,n));//計(jì)算和輸出m個(gè)蘋(píng)果放在n個(gè)盤(pán)子里的分法數(shù)目 } return0;}【例5.6.4】Hanoi（漢諾）塔問(wèn)題在古印度圣廟中，有一種被稱(chēng)為Hanoi（漢諾塔）的游戲。有3根桿，分別為A、B、C。開(kāi)始時(shí)，A桿自下而上、由大到小按順序放置64個(gè)大小不等的盤(pán)子?，F(xiàn)在要把這64個(gè)盤(pán)子從A桿移到C桿，規(guī)定：每次只允許移動(dòng)一個(gè)盤(pán)子；在移動(dòng)過(guò)程中，3個(gè)根桿都始終保持大盤(pán)在下，小盤(pán)在上；且在移動(dòng)過(guò)程中可以使用B桿。下圖給出將3個(gè)大小不等的盤(pán)子從A桿移到C桿的過(guò)程?！冻绦蛟O(shè)計(jì)》99把n個(gè)盤(pán)子從A桿移到C桿的遞歸函數(shù)：自頂向下、逐步求精，功能分解voidhanoi(intn,charA,charC,charB){/*將n個(gè)盤(pán)子從A桿移到C桿，搬動(dòng)過(guò)程可使用B桿*/if(n==1)/*對(duì)于只搬動(dòng)一個(gè)盤(pán)子情況*/(1)將盤(pán)子n

從A桿搬到C桿;else{/*搬n(>1)個(gè)盤(pán)子時(shí)，按同樣算法先搬前n-1張盤(pán)子*/(2)將A桿上的n-1個(gè)盤(pán)子搬到B桿上，中間可使用C桿;(3)將盤(pán)子n從A桿搬到C桿;/*搬動(dòng)第n個(gè)盤(pán)子*/

/*搬B桿上前n-1個(gè)盤(pán)子*/(4)將B桿上的n-1個(gè)盤(pán)子搬到C桿，中間可使用A桿;}}求解Hanoi塔問(wèn)題的遞歸函數(shù)voidhanoi(intn,charA,charC,charB){//解決漢諾塔問(wèn)題的算法if(n==1)printf("move%cto%c\n",A,C);else{hanoi(n-1,A,B,C); printf("move%cto%c\n",A,C);hanoi(n-1,B,C,A); }}Hanoi塔問(wèn)題代碼《C語(yǔ)言程序設(shè)計(jì)》P138-P139【例5.6.5】漢諾塔V試題來(lái)源：ECJTU2008SpringContest，周尚超在線測(cè)試：HDOJ1995用1,2,...,n表示n個(gè)盤(pán)子，稱(chēng)為1號(hào)盤(pán)，2號(hào)盤(pán),...。號(hào)數(shù)大，盤(pán)子就大。經(jīng)典的漢諾塔問(wèn)題經(jīng)常作為一個(gè)遞歸的經(jīng)典例題存在?？赡苡腥瞬⒉恢罎h諾塔問(wèn)題的典故。漢諾塔來(lái)源于印度傳說(shuō)的一個(gè)故事，上帝創(chuàng)造世界時(shí)造了三根金剛石柱子，在一根柱子上從下往上按大小順序摞著64片黃金圓盤(pán)。上帝命令婆羅門(mén)把圓盤(pán)從下面開(kāi)始按大小順序重新擺放在另一根柱子上。并且規(guī)定，在小圓盤(pán)上不能放大圓盤(pán)，在三根柱子之間一次只能移動(dòng)一個(gè)圓盤(pán)。我們知道最少需要移動(dòng)264-1次。在移動(dòng)過(guò)程中發(fā)現(xiàn)，有的圓盤(pán)移動(dòng)次數(shù)多，有的少。給出盤(pán)子總數(shù)和某個(gè)盤(pán)子的盤(pán)號(hào)，請(qǐng)您計(jì)算移動(dòng)該盤(pán)子的次數(shù)。輸入

輸入給出多個(gè)測(cè)試用例，首先輸入t，表示有t個(gè)測(cè)試用例。每個(gè)測(cè)試用例一行，給出盤(pán)子的數(shù)目n（1

n

60）和一個(gè)盤(pán)子的盤(pán)號(hào)k（1

k

n）。輸出對(duì)于每個(gè)測(cè)試用例，輸出一個(gè)數(shù)，到達(dá)目標(biāo)時(shí)k號(hào)盤(pán)子需要的最少移動(dòng)數(shù)。試題解析對(duì)于本題，采用統(tǒng)計(jì)分析法，分析部分解，由部分解推導(dǎo)出求解算法。分析如下：1個(gè)盤(pán)子，則1號(hào)盤(pán)移動(dòng)1次，總移動(dòng)次數(shù)為21-1=1。2個(gè)盤(pán)子，則1號(hào)盤(pán)移動(dòng)2次，2號(hào)盤(pán)移動(dòng)1次，總移動(dòng)次數(shù)為22-1=3。1號(hào)盤(pán)移動(dòng)次數(shù)=2號(hào)盤(pán)移動(dòng)次數(shù)

2。3個(gè)盤(pán)子，則1號(hào)盤(pán)移動(dòng)4次，2號(hào)盤(pán)移動(dòng)2次，3號(hào)盤(pán)移動(dòng)1次，總移動(dòng)次數(shù)為23-1=7。1號(hào)盤(pán)移動(dòng)次數(shù)=2號(hào)盤(pán)移動(dòng)次數(shù)

2，2號(hào)盤(pán)移動(dòng)次數(shù)=3號(hào)盤(pán)移動(dòng)次數(shù)

2。以此類(lèi)推。所以，如題目描述，64個(gè)盤(pán)子，最少需要移動(dòng)264-1次，且盤(pán)號(hào)最大的盤(pán)子移動(dòng)次數(shù)為1，每一張盤(pán)子移動(dòng)的次數(shù)=它下面盤(pán)子移動(dòng)次數(shù)

2。因此，給出盤(pán)子的數(shù)目n和盤(pán)子的盤(pán)號(hào)k，k號(hào)盤(pán)子需要的最少移動(dòng)數(shù)為2n-k。本題給出的數(shù)據(jù)范圍，盤(pán)子的數(shù)目n（1

n

60）存儲(chǔ)移動(dòng)該盤(pán)子的次數(shù)要用longlong如果在C程序中使用pow函數(shù)計(jì)算2的冪加頭文件:#include<math.h>。《程序設(shè)計(jì)》111遞歸函數(shù)(續(xù))對(duì)于算法間接地由其自身定義情況，稱(chēng)為間接遞歸。在間接遞歸情況下，函數(shù)調(diào)用鏈中，在同一個(gè)函數(shù)再次出現(xiàn)之前，有一個(gè)或多個(gè)其它別的函數(shù)遞歸程序特點(diǎn)通常，以遞歸形式定義算法與非遞歸算法比較，算法結(jié)構(gòu)會(huì)更緊湊、清晰但是，遞歸函數(shù)在遞歸調(diào)用過(guò)程中，會(huì)占用更多的內(nèi)存空間和需更多的運(yùn)行時(shí)間另外，在編寫(xiě)遞歸函數(shù)時(shí)，必須防止遺漏遞歸終止條件和防止振蕩式的相互遞歸調(diào)用，否則會(huì)產(chǎn)生無(wú)限遞歸調(diào)用現(xiàn)象《程序設(shè)計(jì)》112直接遞歸vs.間接遞歸直接遞歸間接遞歸《程序設(shè)計(jì)》113用遞推實(shí)現(xiàn)遞歸的示意程序勒讓得多項(xiàng)式的遞歸定義為

┌1，n=0;p(n,x)=┤x，n=1;└((2n-1)xp(n-1,x)-(n-1)p(n-2,x))/n，n>1程序設(shè)計(jì)分析用遞歸函數(shù)實(shí)現(xiàn)，能很容易地寫(xiě)出它的函數(shù)定義如下

doublep(intn,doublex){if(n==0)return1.0;if(n==1)returnx;return((2.0*n-1.0)*x*p(n-1,x)-(n-1.0)*p(n-2,x))/n;}《程序設(shè)計(jì)》114用遞推實(shí)現(xiàn)遞歸的示意程序(續(xù))勒讓得多項(xiàng)式用遞推方法實(shí)現(xiàn)程序設(shè)計(jì)分析計(jì)算p(n,x)的困難是n>1情況然而，若知道了p(n-2,x)和p(n-1,x)的話，就能立即按公式計(jì)算出p(n，x)由于p(0,x)與p(1,x)是能立即得到的這樣就能用遞推方法，從p(0,x)與p(1,x)出發(fā)，依次計(jì)算出p(2,x)，p(3,x)，…即從冪次低的勒讓得多項(xiàng)式到冪次高的勒讓得多項(xiàng)式的遞推解法《程序設(shè)計(jì)》115用遞推實(shí)現(xiàn)遞歸的示意程序(續(xù))勒讓得多項(xiàng)式用遞推方法實(shí)現(xiàn)，函數(shù)定義如下doublep(intn,doublex){doublefirst,second,third;intcount;if(n==0)return1.0;if(n==1)returnx;

first=1.0;second=x;for(count=2;count<=n;count++){

third=((2.0*count-1.0)*x*second-(count-1.0)*first)/count;

first=second;second=third;}

returnthird;}《程序設(shè)計(jì)》1165.7命令行參數(shù)執(zhí)行C程序，可以看作是對(duì)該程序的main()函數(shù)的調(diào)用。main()函數(shù)執(zhí)行結(jié)束，返回環(huán)境。為能從環(huán)境向C程序傳遞信息，啟動(dòng)C程序的命令行可帶有任選的參數(shù)命令行的一般形式為程序名參數(shù)1參數(shù)2…參數(shù)n其中程序名和各參數(shù)之間用空白符分隔為能讓main()函數(shù)讀取命令行中的參數(shù)，環(huán)境將多個(gè)參數(shù)以?xún)蓚€(gè)參數(shù)形式傳遞給main()函數(shù)。其中第一個(gè)參數(shù)(習(xí)慣記作argc)表示命令行中參數(shù)的個(gè)數(shù)(包括程序名)；第二個(gè)參數(shù)(習(xí)慣記作argv)是一個(gè)字符指針數(shù)組。其中argv[0]指向程序名字符串，argv[1]指向參數(shù)1字符串，...，argv[argc-1]指向最后一個(gè)參數(shù)字符串。如果argc等于1，則表示程序名后面沒(méi)有參數(shù)《程序設(shè)計(jì)》117【例5.7.1】說(shuō)明main()函數(shù)對(duì)參數(shù)argc與argv引用方法的程序打印啟動(dòng)程序時(shí)的命令行各參數(shù)

#include<stdio.h>voidmain(intargc,char*argv[]/*或char**argv;*/){intk;for(k=1;k<argc;k++)printf("%s%c",argv[k],k<argc-1?'':'\n');printf("\n\n");}如上述程序的執(zhí)行程序名為aecho.exe，執(zhí)行該程序的命令行為：aechoHelloworld!則程序?qū)⑤敵鯤elloworld!根據(jù)約定，main()函數(shù)的參數(shù)argc的值為3；argv[0]，argv[1]，argv[2]分別指向字符串"echo"、"Hello"、"world!"的第一個(gè)字符《程序設(shè)計(jì)》118命令行參數(shù)(續(xù))在程序的printf()函數(shù)調(diào)用中，字符轉(zhuǎn)換格式%c輸出一個(gè)字符，若是已輸出了命令行最后一個(gè)參數(shù)，該格式將輸出一個(gè)換行符，若是輸出其他參數(shù)，則輸出一個(gè)空白符因函數(shù)的數(shù)組參數(shù)是指向數(shù)組首元素的指針變量，所以在主函數(shù)main()中可對(duì)argv施行增量運(yùn)算例如，在argv[0]指針指向程序名字符串的第一個(gè)字符情況下，對(duì)argv施增量運(yùn)算++argv后，argv[0](或*argv)就指向參數(shù)1的第一個(gè)字符《程序設(shè)計(jì)》119命令行參數(shù)(續(xù))利用在主函數(shù)main()中可對(duì)argv施行增量運(yùn)算的性質(zhì)，可改寫(xiě)前述示例程序?yàn)橐韵滦问?/p>

#include<stdio.h>voidmain(intargc,char**argv){while(--argc>0)printf("%s%c",*++argv,argc>1?'':'\n');}這里，++argv使指針argv先加1，讓它一開(kāi)始就指向參數(shù)1；逐次增1，使它遍歷指向各參數(shù)又利用函數(shù)printf()的第一個(gè)格式參數(shù)是字符串表達(dá)式，上述程序?qū)rintf()的調(diào)用可改寫(xiě)成

printf((argc>1)?"%s":"%s\n",*++argv);《程序設(shè)計(jì)》120【例5.7.2】假定啟動(dòng)程序時(shí)給出的命令行參數(shù)是一串整數(shù)，程序?qū)⑷空麛?shù)求和后輸出。#include<stdio.h>#include<math.h>voidmain(intargc,char**argv){intk,s;for(s=0,k=1;k<argc;k++)s+=atoi(*++argv);/*從數(shù)字字符串譯出整數(shù)*/printf(“\t%d\n”,s);}atoi(表示asciitointeger)是把字符串轉(zhuǎn)換成整型數(shù)的一個(gè)函數(shù)；頭文件：

#include<stdlib.h>《程序設(shè)計(jì)》121《程序設(shè)計(jì)》122命令行參數(shù)(續(xù))利用指針數(shù)組作main()函數(shù)的形參，向程序傳遞命令行參數(shù)字符串，其中字符串的長(zhǎng)度可以不同，參數(shù)的個(gè)數(shù)也可以任意，這是指針數(shù)組作函數(shù)參數(shù)最為方便靈活的應(yīng)用命令行可帶任選的參數(shù)，程序(主要main()函數(shù)）應(yīng)能正確識(shí)別某參數(shù)的出現(xiàn)，及該參數(shù)的意義。通常，C程序?qū)⒚钚袇?shù)分成兩部分一部分是一定要出現(xiàn)的參數(shù)，它們通常被安排在命令行參數(shù)表的最后部分，并對(duì)這些參數(shù)出現(xiàn)順序也有明確的約定另一部分是可任選的參數(shù)，因它們中的某些或全部可以不出現(xiàn)，為使程序能正確識(shí)別出現(xiàn)的參數(shù)及其意義，C程序習(xí)慣用以下形式表示一個(gè)可任選的參數(shù)

-字符參數(shù)《程序設(shè)計(jì)》123命令行參數(shù)(續(xù))C程序習(xí)慣用以下形式表示一個(gè)可任選的參數(shù)

-字符參數(shù)其中負(fù)號(hào)表示一個(gè)任選參數(shù)，緊接的字符是任選參數(shù)的標(biāo)志符。其后的參數(shù)可以沒(méi)有。如有，就作為命令行的下一個(gè)參數(shù)。特別是對(duì)于標(biāo)志符之后的參數(shù)沒(méi)有的情況，多個(gè)參數(shù)標(biāo)志符緊接在一起，合用一個(gè)任選參數(shù)開(kāi)始符(負(fù)號(hào)字符)《程序設(shè)計(jì)》124命令行參數(shù)程序示例輸入正文，從中尋找包含特定字符串的行。其中特定字符串由命令行的參數(shù)指定。程序另設(shè)兩個(gè)供任選的參數(shù)參數(shù)1-x印出所有那些不包含特定字符串的行；無(wú)-x，則印出所有那些包含特定字符串的行參數(shù)2-n在輸出字符行之前，冠以該行在正文中的行號(hào)；否則，輸出時(shí)不帶行號(hào)另約定，特定字符串參數(shù)是命令行的最后一個(gè)參數(shù)；任選參數(shù)的出現(xiàn)順序可以任意。如兩個(gè)任選參數(shù)都出現(xiàn)時(shí)，可合在一起同時(shí)指定，如-xn或-nx。一個(gè)任選參數(shù)最多只能出現(xiàn)一次。運(yùn)行本程序的命令行的一般形式為find-x-npatternfilename《程序設(shè)計(jì)》125命令行參數(shù)程序示例(續(xù))#defineLINES500#defineMAXLINE300#include<stdio.h>#include<string.h>#include<malloc.h>intgetline(FILE*fp,char*s,intlim);intindex(char*s,char*t);intmain(intargc,char**argv){char*lineptr[LINES];intlineno[LINES];intlen,m;intnlines=0;intn=0;interr=0;intinverse=0;intnum=0;FILE*fp;charline[MAXLINE],*s;《程序設(shè)計(jì)》126命令行參數(shù)程序示例(續(xù))while(err==0&&--argc>0&&(*++argv)[0]==’-’)

/**++argv是指向任選參數(shù)串的首字符指針，(*++argv)[0]是任選參數(shù)字符串的首字符*/for(s=argv[0]+1;*s!=’\0’;s++)switch(*s){case'x':if(inverse)err=1;/*限制x最多只能出現(xiàn)1次*/elseinverse=1;/*inverse=1表示x出現(xiàn)*/break;case'n':if(num)err=1;/*

限制n最多只能出現(xiàn)1次*/elsenum=1;/*num=1表示n出現(xiàn)*/break;default:err=1;}/*正確情況下，至此argc應(yīng)為2*/if(err||argc!=2){/*如有使用不當(dāng)*/printf("Usage:find-x-npatternfilename\n");return1;}《程序設(shè)計(jì)》127命令行參數(shù)程序示例(續(xù))if((fp=fopen(*(argv+1),"r"))==NULL){fprintf(stderr,"Can'topen%s.\n",*(argv+1));return2;}while((len=getline(fp,line,MAXLINE))>0){nlines++;/*記錄行數(shù)*/if((index(line,*argv)>=0)!=inverse)if((s=(char*)malloc(len+1))==NULL)break;else{lineno[n]=nlines;strcpy(s,line);lineptr[n++]=s;}}fclose(fp);for(m=0;m<n;m++){if(num)printf("%4d:",lineno[m]);printf("%s\n",lineptr[m]);}return0;}《程序設(shè)計(jì)》128命令行參數(shù)程序示例(續(xù))intgetline(FILE*fp,char*s,intlim)/*從文件讀出一個(gè)串到s，返回串的長(zhǎng)度*/{intc;char*ps=s;while(ps<s+lim-1&&(c=fgetc(fp))!=EOF){*ps++=c;if(c=='\n')break;}*ps='\0';returnps-s;}intindex(char*s,char*t)/*判斷t是否出現(xiàn)在s中，并確定出現(xiàn)位置*/{inti,len1=strlen(s),len2=strlen(t);char*ps,*pt;for(i=0;i<=len1-len2;i++){for(ps=s+i,pt=t;*pt!='\0'&&*ps==*pt;ps++,pt++);if(*pt=='\0')returni;}return-1;}《程序設(shè)計(jì)》129函數(shù)程序設(shè)計(jì)實(shí)例編制求整數(shù)是幾位十進(jìn)位數(shù)的函數(shù)編制判定正整數(shù)n的d進(jìn)制表示形式是否是回文數(shù)的函數(shù)《程序設(shè)計(jì)》130函數(shù)程序設(shè)計(jì)實(shí)例-1編制求整數(shù)是幾位十進(jìn)位數(shù)的函數(shù)設(shè)函數(shù)模型為intdigit(intn)，函數(shù)的功能是求形參n是幾位十進(jìn)位數(shù)。引入變量c計(jì)數(shù)n的位數(shù)，則反復(fù)將n除以10，直至n等于0的重復(fù)次數(shù)，就能推算出n的十進(jìn)位的位數(shù)函數(shù)開(kāi)始時(shí)預(yù)置計(jì)數(shù)器c為0，循環(huán)的工作部分是讓c增1和n除以10，循環(huán)直至n除以10后為0結(jié)束如下面的函數(shù)digits()的定義

intdigits(intn){intc=0;do{c++;n/=10;}while(n);returnc;}問(wèn)題：如何把一個(gè)實(shí)數(shù)變成十進(jìn)位數(shù)串？《程序設(shè)計(jì)》131函數(shù)程序設(shè)計(jì)實(shí)例-2編制從兩個(gè)已知非空字符串中找出最長(zhǎng)公共子串的的長(zhǎng)度和最長(zhǎng)公共子串的個(gè)數(shù)的函數(shù)設(shè)函數(shù)模型為intcommStr(char*str1,char*str2,int*lenpt)函數(shù)的形參str1和str2是已知字符串首字符的指針，形參lenpt用于存儲(chǔ)找到的最長(zhǎng)子串的長(zhǎng)度，函數(shù)返回找到的最長(zhǎng)公共子串的個(gè)數(shù)函數(shù)算法的基本想法是對(duì)字符串s2的各種可能子串，在字符串s1中找是否有同樣的子串記兩個(gè)字符串str1和str2的長(zhǎng)度分別為len1和len2。假定len1>=len2。則它們最長(zhǎng)的公共子串長(zhǎng)度不會(huì)超過(guò)len2。設(shè)要尋找的子串長(zhǎng)為ln，ln的初值為len2，即以str2字符串的最長(zhǎng)子串開(kāi)始尋找，當(dāng)在str1中沒(méi)有長(zhǎng)為ln的相同子串時(shí)，就讓ln減1，即用str2更短的子串重新尋找。若找到，則該子串就可作為函數(shù)要找的str1和str2的一個(gè)最長(zhǎng)子串。若直至找遍了str2的所有可能的子串，還未在str1中找到相同的子串，則說(shuō)明str1和str2沒(méi)有公共子串《程序設(shè)計(jì)》132函數(shù)程序設(shè)計(jì)實(shí)例-2(續(xù))編制從兩個(gè)已知非空字符串中找出最長(zhǎng)公共子串的的長(zhǎng)度和最長(zhǎng)公共子串的個(gè)數(shù)的函數(shù)(續(xù))#include<stdio.h>intcommStr(char*str1,char*str2,int*lenpt)/*函數(shù)返回最長(zhǎng)公共子串的個(gè)數(shù),通過(guò)指針參數(shù)傳回最長(zhǎng)公共子串的長(zhǎng)度*/{intlen1,len2,ln,count,i,k,p;char*st;if((len1=strlen(str1))<(len2=strlen(str2))){/*把str2作為短的串*/st=str1;str1=str2;str2=st;ln=len1;len1=len2;len2=ln;}count=0;《程序設(shè)計(jì)》133函數(shù)程序設(shè)計(jì)實(shí)例-2(續(xù))for(ln=len2;ln>0;ln--){/*找長(zhǎng)ln的公共子串*/for(k=0;k+ln<=len2;k++){

/*自str2[k]開(kāi)始，長(zhǎng)為ln子串與str1的子串比較*/for(p=0;p+ln<=len1;p++){/*str1中的子串自str1[p]開(kāi)始，兩子串對(duì)應(yīng)字符逐一比較*/

for(i=0;i<ln;i++)if(str2[k+i]!=str1[p+i])break;if(i==ln)count++;/*找到一個(gè)最長(zhǎng)公共子串*/}}if(count)break;/*如找到過(guò)，退出尋找循環(huán)*/}*lenpt=ln;returncount;}voidmain(){intc,len;c=commStr("Abc1AbcsAbcd123","123bAbc",&len);printf("有%d個(gè)長(zhǎng)為%d的公共子串\n",c,len);}《程序設(shè)計(jì)》134函數(shù)程序設(shè)計(jì)實(shí)例-3編寫(xiě)函數(shù)inttrans(unsignedn,intd,chars[])，將無(wú)符號(hào)整數(shù)n翻譯成d(2<=d<=16)進(jìn)制的字符串s。函數(shù)的返回值是該d進(jìn)制的字符串長(zhǎng)度。當(dāng)d>10時(shí)，d進(jìn)制的數(shù)字位值可能要大于9，約定大于9的數(shù)字位值分別用字符A、B、C、D、E、F標(biāo)記數(shù)字位值10、