C語言程序設(shè)計活頁式教程 課件 -05 面向過程編程

C語言程序設(shè)計活頁式教程項目5面向過程編程經(jīng)驗豐富的中學(xué)班主任在開家長會前，會將家長會的準備工作安排得井井有條。比如，安排兩名學(xué)生負責黑板報，安排六名學(xué)生負責課室清潔，安排兩名學(xué)生負責粘貼學(xué)生名牌，安排兩名學(xué)生負責準備茶水，安排四名學(xué)生進行接待指引等等。如此一來，開家長會這個“龐大”的項目就被分解成了一個個小“任務(wù)”，只需完成所有任務(wù)，就能保證家長會的順利進行。在程序設(shè)計中，也會采用類似的操作，將一個較大的程序分解成若干個程序模塊，一個程序模塊實現(xiàn)某個特定的功能。在C語言中，用函數(shù)來實現(xiàn)模塊功能。函數(shù)是構(gòu)成C語言程序的基本單位，程序從主函數(shù)main開始執(zhí)行，最后由main()函數(shù)結(jié)束整個程序。C語言程序一般由一個主函數(shù)和若干個其他函數(shù)共同構(gòu)成。主函數(shù)調(diào)用其他函數(shù)實現(xiàn)特定功能，其他函數(shù)之間也可以相互調(diào)用。在程序的開發(fā)過程中，常將多次用到的功能模塊編寫成函數(shù)。程序設(shè)計人員通過函數(shù)調(diào)用，可以大大減少重復(fù)的工作量，從而提高編程工作的效率。到目前為止，我們所編寫的程序都只有一個main()函數(shù)。但在編寫程序的過程中，都在不斷地使用scanf()、printf()、getchar()和putchar()等輸入輸出函數(shù)，這些函數(shù)都稱為C語言的標準庫函數(shù)，它們由系統(tǒng)提供可以直接使用。由于標準庫函數(shù)只包括一些基本的、通用的功能函數(shù)，而在實際應(yīng)用中需要解決具體復(fù)雜的問題時，標準庫函數(shù)不能滿足要求，這就要求程序員根據(jù)實際情況來編寫函數(shù)，實現(xiàn)某些特定的功能。綜上所述，函數(shù)可分為標準庫函數(shù)和自定義函數(shù)。對于標準庫函數(shù)，重點要了解有哪些庫函數(shù)，分別能完成什么功能及如何調(diào)用。而對于自定義函數(shù)，重點要根據(jù)需求來劃分功能，并將功能定義成函數(shù)。項目任務(wù)知識目標學(xué)習(xí)目標任務(wù)1：定義和調(diào)用函數(shù)任務(wù)2：用函數(shù)解決數(shù)學(xué)難題任務(wù)3：用遞歸函數(shù)解決特殊問題任務(wù)4：使用主函數(shù)的參數(shù)（1）了解函數(shù)的定義和調(diào)用。（2）了解全局變量和局部變量的特點。（3）掌握程序模塊劃分。（4）掌握遞歸函數(shù)的定義、調(diào)用以及適用的場景。（5）能夠設(shè)計并使用程序的參數(shù)。任務(wù)準備任務(wù)實施任務(wù)描述任務(wù)1定義和調(diào)用函數(shù)任務(wù)描述模塊化的程序設(shè)計方法通常是將比較復(fù)雜的問題分解成若干個相對簡單的子問題，然后分別求解，以降低解決問題的復(fù)雜度。一個C語言程序由一個或多個程序模塊組成，每個程序模塊由一個或多個函數(shù)組成。將一段很長的代碼按功能拆分成若干個函數(shù)，有以下優(yōu)點：（1）有利于代碼閱讀。函數(shù)給一組語句命名，讓它們成為一個代碼塊，這樣更有利閱讀代碼和調(diào)試。（2）減少重復(fù)代碼的使用。函數(shù)讓程序代碼總行數(shù)變的更少，之后如果需要修改代碼，只需要改很少的地方。（3）方便拆分調(diào)試。將一段很長的代碼拆分成幾個函數(shù)之后，可以對每一個函數(shù)進行單獨的調(diào)試。單個函數(shù)調(diào)試通過后，再將它們組合起來形成一個完整的軟件產(chǎn)品。（4）通用性強。一個設(shè)計良好的函數(shù)，可以在很多程序中被反復(fù)調(diào)用，不需要重新編寫或修改。本任務(wù)會將一些常見功能編寫成函數(shù)，如判斷素數(shù)、求一維整型數(shù)組的最大值、對一維整型數(shù)組排序等。通過這些例子，向?qū)W生講解函數(shù)的定義、聲明和調(diào)用規(guī)則，讓學(xué)生掌握函數(shù)的相關(guān)操作，具備模塊化程序設(shè)計能力。任務(wù)準備任務(wù)實施Part

1Part

2Part

3任務(wù)描述任務(wù)準備1.函數(shù)的定義函數(shù)本質(zhì)是一段可以被重復(fù)調(diào)用、功能相對獨立的程序段。函數(shù)的定義形式如下：返回類型函數(shù)名1(){

函數(shù)體;}或：返回類型函數(shù)名2(類型1形參1,類型2形參2,…,類型n形參n){

函數(shù)體;}任務(wù)準備一個函數(shù)由函數(shù)名、參數(shù)、函數(shù)體、返回類型組成。定義函數(shù)時要注意以下幾點：（1）函數(shù)名要避免與標準庫函數(shù)同名。（2）參數(shù)可以有0個或多個，以逗號隔開。沒有參數(shù)的函數(shù)叫“無參函數(shù)”，如“函數(shù)名1”就是無參函數(shù)；有參數(shù)的函數(shù)叫“有參函數(shù)”，如“函數(shù)名2”就是有參函數(shù)。（3）每個參數(shù)都是以“類型變量”形式給出?！靶螀”就是一個變量名，它被稱為“形式參數(shù)”。顧名思義，形式參數(shù)只是一個形式，它的名字不重要，重要是的它的類型。形式參數(shù)告訴調(diào)用者，此處應(yīng)該放一個指定類型的數(shù)據(jù)?？梢赃@么理解，形式參數(shù)就像電影里的“路人甲”，他叫什么名字、長得怎么樣都無關(guān)緊要，他站在那里的意義是充當一個士兵的角色，即他代表一個士兵類型。（4）函數(shù)體必須在一對大括號中，它是函數(shù)名所代表的代碼段，可以是一句或多句代碼。（5）函數(shù)的返回類型可以是void類型或非void類型。返回類型是void的函數(shù)，它執(zhí)行完函數(shù)體后不會返回數(shù)據(jù)。非void類型可以是int、char、double、結(jié)構(gòu)體、指針等類型，返回類型不是void的函數(shù)，它的函數(shù)體內(nèi)必須有一個return語句。return后跟一個表達式，表達式的類型與函數(shù)的返回類型一致。（6）函數(shù)的功能必須單一。初學(xué)者最容易犯的錯誤是將函數(shù)實現(xiàn)某功能后得出的結(jié)果輸出，按函數(shù)功能單一的原則，該函數(shù)只需要將得出的結(jié)果返回，將結(jié)果輸出是多此一舉、畫蛇添足。（7）函數(shù)不能嵌套定義，即不能在一個函數(shù)中定義另一個函數(shù)。任務(wù)準備定義一個函數(shù)時，重點要弄清楚這個函數(shù)應(yīng)該代入什么參數(shù)，返回什么類型的數(shù)據(jù)。以設(shè)計世界上第一臺豆?jié){機為例，比較好的設(shè)計是，往豆?jié){機里放入水和黃豆，啟動豆?jié){機，不久后就能從豆?jié){機里倒出豆?jié){來。如果把豆?jié){機比作一個函數(shù)，它應(yīng)該代入什么、返回什么呢？很顯然，它代入的形式參數(shù)是水和黃豆，返回類型是豆?jié){。定義豆?jié){機的函數(shù)偽代碼如下：豆?jié){豆?jié){機(水x,黃豆y){

制作豆?jié){的代碼段;}任務(wù)準備以定義一個求兩個整數(shù)的最大公約數(shù)的函數(shù)為例，它需要代入這兩個整數(shù)，返回整型的最大公約數(shù)。求最大公約數(shù)的思路是：找出兩個整數(shù)的較小的那一個，從1循環(huán)到較小數(shù)，記錄能被兩個整數(shù)都除盡的最大值。求最大公約數(shù)的函數(shù)定義如下：intgys(inta,intb){ inti,x=1; intc=(a<b?a:b);/*條件表達式,返回a與b中的較小者*/ for(i=1;i<=c;i++)/*i從1開始*/ { if(a%i==0&&b%i==0)/*a和b都能把i除盡,說明找到公約數(shù)*/ x=i; } returnx;}任務(wù)準備初學(xué)者最容易犯的錯誤就是，將求得的最大公約數(shù)輸出，錯誤地將求兩數(shù)的最大公約數(shù)的函數(shù)定義成如下形式：voidgys2(inta,intb){ inti,x=1; intc=(a<b?a:b); for(i=1;i<=c;i++) { if(a%i==0&&b%i==0) x=i; } printf("%d和%d的最大公約數(shù)是%d\n",a,b,x);}函數(shù)gys()能應(yīng)用在任何需要求兩數(shù)的最大公約數(shù)的場合，而函數(shù)gys2()只能應(yīng)用在輸出兩個數(shù)的最大公約數(shù)的情形下。很顯然，功能單一的gys()函數(shù)應(yīng)用范圍更廣。任務(wù)準備再以定義一個輸出一維整型數(shù)組所有元素的函數(shù)為例，它需要代入整型數(shù)組的首地址和元素個數(shù)，不需要返回任何數(shù)據(jù)。該函數(shù)的定義如下：voidshuchu(inta[],intn){ inti; for(i=0;i<n;i++) printf("%d,",a[i]);}當一維數(shù)組作函數(shù)參數(shù)時，代入的是該數(shù)組的首地址，即數(shù)組名。但數(shù)組名只是一個地址，編譯系統(tǒng)并不知道它有多少個元素，因此，當要把一維數(shù)組傳入函數(shù)時，要代入函數(shù)名和元素個數(shù)。任務(wù)準備2.函數(shù)的調(diào)用定義函數(shù)的目的是為了重復(fù)使用某種功能或某段代碼，我們將函數(shù)的使用稱為函數(shù)調(diào)用。定義函數(shù)時需要寫清楚代入?yún)?shù)、返回類型和實現(xiàn)代碼，而調(diào)用函數(shù)則簡單很多，函數(shù)的調(diào)用形式如下：函數(shù)名1(實際參數(shù)列表);或：數(shù)據(jù)類型變量=函數(shù)名2(實際參數(shù)列表);任務(wù)準備函數(shù)的定義不同，調(diào)用時的寫法也不相同。調(diào)用函數(shù)時要注意以下幾點：（1）形式參數(shù)是定義函數(shù)時給出的參數(shù)，它們必須指明數(shù)據(jù)類型和順序，而形式參數(shù)的名字最好能代表實際的意義，如age、height、maxIndex。（2）實際參數(shù)是調(diào)用函數(shù)時給出的參數(shù)，它們必須與形式參數(shù)的類型和順序?qū)?yīng)。實際參數(shù)的前面不用再寫數(shù)據(jù)類型，也不需要與形式參數(shù)同名。實際參數(shù)可以是常量、變量、表達式甚至另一個函數(shù)。（3）無參函數(shù)不需要代入?yún)?shù)。（4）有參函數(shù)在代入實際參數(shù)時，必須保證實際參數(shù)的類型和順序與定義的形式參數(shù)的類型和順序一致。（5）void函數(shù)由于沒有返回值，它的調(diào)用一般單獨成行，如“函數(shù)名1”。（6）非void函數(shù)有返回值，調(diào)用時一般用變量接收它的返回值，如“函數(shù)名2”。但也存在調(diào)用非void函數(shù)后不接收它的返回值的情況。（7）由于非void函數(shù)有返回值，它可以被當作一個變量使用，如與其它常量或變量組成表達式，或被當成另一個函數(shù)的實際參數(shù)。任務(wù)準備以求兩數(shù)最大公約數(shù)的gys()函數(shù)和輸出一維整型數(shù)組的shuchu()函數(shù)為例，它們的調(diào)用可以是如下幾種形式：intx=6,y=14,z;intsz[10]={0,1,2,3,4,5,6,7,8,9};z=gys(5,10);z=gys(x,y)+2;z=gys(5,y+1);z=gys(5,gys(15,45));/*非void函數(shù)作為函數(shù)的參數(shù)*/gys(7,y);/*不接收函數(shù)返回值的情況*/shuchu(sz,10);/*void函數(shù)的調(diào)用*/任務(wù)準備3.函數(shù)的聲明在C語言中，函數(shù)的定義順序是有講究的。默認情況下，只有后面定義的函數(shù)才可以調(diào)用前面定義過的函數(shù)。如果想把函數(shù)的定義寫在main()函數(shù)后面，而且main()函數(shù)能正常調(diào)用這些函數(shù)，那就必須在main()函數(shù)的前面進行函數(shù)的聲明。在調(diào)用標準庫函數(shù)時，不需要預(yù)先聲明，但必須在程序的開頭用“#include”命令將庫函數(shù)所在的頭文件包含進來。調(diào)用用戶自定義函數(shù)時，則要對函數(shù)進行聲明，聲明函數(shù)的格式有如下兩種：數(shù)據(jù)類型函數(shù)名(類型1,類型2,…);數(shù)據(jù)類型函數(shù)名(類型1形參1,類型2形參2,…);函數(shù)的聲明可以只給出形式參數(shù)的類型，也可以像定義函數(shù)時一樣同時給出參數(shù)的類型和名稱，而且聲明時的參數(shù)名可以與定義時的參數(shù)名不一樣。但無論是哪種寫法，對應(yīng)參數(shù)的類型必須一致。任務(wù)準備以求兩數(shù)最大公約數(shù)的gys()函數(shù)和輸出一維整型數(shù)組的shuchu()函數(shù)為例，它們的聲明可以是如下幾種形式：intgys(int,int);intgys(intc,intd);voidshuchu(int[],int);/*int[]代表一維整型數(shù)組的類型*/voidshuchu(intx[],inty);函數(shù)聲明的作用是告知編譯軟件，某標識符（函數(shù)名）代表一個自定義函數(shù)，它必須代入幾個參數(shù)，參數(shù)類型是什么，該自定義函數(shù)返回什么類型的數(shù)據(jù)。函數(shù)聲明通常寫在程序的開頭（或頭文件中），執(zhí)行函數(shù)的代碼在函數(shù)聲明之后。在C語言中，返回類型為int的函數(shù)默認可以不用聲明，但推薦初學(xué)者養(yǎng)成編程的好習(xí)慣，在自定義函數(shù)時先聲明再調(diào)用。任務(wù)準備【實例1】寫一個函數(shù)，判斷某個正整數(shù)是不是素數(shù)。然后在main()函數(shù)中要求用戶輸入一個正整數(shù)，調(diào)用該函數(shù)判斷用戶輸入的正整數(shù)是不是素數(shù)。#include<stdio.h>intsushu(intn); /*聲明函數(shù)*/intmain(){ intx,f; printf("請輸入一個正整數(shù):"); scanf("%d",&x); f=sushu(x); /*調(diào)用函數(shù)*/ if(f==1) printf("%d是素數(shù)!",x); else printf("%d不是素數(shù)!",x); return1;}intsushu(intn) /*定義函數(shù)*/{ /*先假定n是素數(shù).flag=1代表n是素數(shù),flag=0代表n不是素數(shù)*/ inti,flag=1; for(i=2;i<n;i++) { /*除盡了*/ if(n%i==0) { flag=0; break; } } returnflag;}任務(wù)準備編譯運行，分別輸入13和25的結(jié)果如圖5-1所示：在定義判斷素數(shù)的sushu()函數(shù)時，需要代入一個正整數(shù)，返回該正整數(shù)是不是素數(shù)的結(jié)果，即“是”或“否”。在C語言中沒有專用于表示是或否的類型，一般用1代表“是”，0代表“否”。判斷正整數(shù)n是不是素數(shù)的思路是：先假定n是素數(shù)，再用n去除以2～n-1的每一個數(shù)，只要有一次除盡就證明n不是素數(shù)。由于自定義函數(shù)sushu()返回int類型的數(shù)據(jù)，所以在調(diào)用它時用變量f接收了它的返回值。圖5-1判斷素數(shù)任務(wù)準備【實例2】定義函數(shù)，求一維整型數(shù)組元素的最小值。然后在main()函數(shù)中定義并初始化一個一維整型數(shù)組，調(diào)用該函數(shù)求出最小值并輸出。#include<stdio.h>intzuixiao(inta[],intn); /*聲明函數(shù)*/intmain(){ intsz[]={1,2,3,4,5,-6,7,8,9,45,99,-100,33}; intc; /*調(diào)用函數(shù),帶入數(shù)組名和元素個數(shù)*/ c=zuixiao(sz,13); printf("數(shù)組元素的最小值是:%d\n",c); return0;}/*定義函數(shù)*/intzuixiao(inta[],intn) { /*先假定最小值是某個數(shù)組元素*/ intmin=a[0],i; for(i=0;i<n;i++) { if(min>a[i])/*用min記錄更小的*/ min=a[i]; } returnmin;}任務(wù)準備編譯運行的結(jié)果如圖5-2所示：在定義求一維整型數(shù)組元素最小值的zuixiao()函數(shù)時，需要代入一維數(shù)組的首地址（即數(shù)組名）和元素個數(shù)（即數(shù)組長度），返回求得的元素最小值。自定義函數(shù)zuixiao()能求所有給定的一維整型數(shù)組的元素最小值，在要用到該功能的場合直接調(diào)用該函數(shù)即可，不需要去重新修改和編譯該函數(shù)的代碼，具有通用性。初學(xué)者很容易犯的一個錯誤是將一維整型數(shù)組定義在函數(shù)zuixiao()內(nèi)部，這樣的做法不可取，因為每當要求另一個一維整型數(shù)組的最小值時，都要去修改函數(shù)內(nèi)部的數(shù)組元素，這樣就失去了函數(shù)能重復(fù)使用的優(yōu)點。圖5-2求一維整型數(shù)組的最小值任務(wù)準備4.return語句return語句一般用在有返回值的函數(shù)（非void函數(shù)）中，用于返回一個與函數(shù)返回類型一致的數(shù)據(jù)。return語句也可以用在沒有返回值的函數(shù)（void函數(shù)）中，作用是退出所在的函數(shù)，它后面不跟任何表達式，寫法為“return;”。任務(wù)準備5.全局變量與局部變量根據(jù)變量的作用范圍，可將變量分為全局變量和局部變量。全局變量在函數(shù)外定義，一般在#include語句后定義，它在定義時會自動初始化（即有默認值），在整個程序運行過程中可隨時訪問，每個函數(shù)都可以使用全局變量。局部變量在函數(shù)內(nèi)部定義，它不會自動初始化（即無默認值），只能在函數(shù)內(nèi)部使用。任務(wù)準備以下面的代碼為例，變量x就是全局變量，變量a、b、c、y和z都是局部變量。#include<stdio.h>intadd(inta,intb);intx=10; /*全局變量*/intmain(){ inty=5,z; /*局部變量*/ z=add(x,y); printf("z=%d\n",z); return0;}intcal(inta,intb){ intc=a+b; /*a,b,c均為局部變量*/ c=c*x; /*訪問全局變量*/ returnc;}局部變量a、b、c、y、z在進入它所在的函數(shù)時獲得內(nèi)存空間，退出函數(shù)時釋放內(nèi)存空間，也從側(cè)面說明局部變量只在定義它的函數(shù)內(nèi)有效。而全局變量x則在整個程序執(zhí)行過程中都有效。任務(wù)準備6.靜態(tài)變量由于局部變量在退出定義它的函數(shù)后內(nèi)存空間被釋放，當再次調(diào)用并進入該函數(shù)時，局部變量會被重新分配內(nèi)存空間，無法保留上一次的值。如果希望局部變量能保持上一次的值，可以將它定義成靜態(tài)變量，一般的定義格式如下：static數(shù)據(jù)類型變量名;任務(wù)準備例如在函數(shù)add()中定義一個靜態(tài)變量c并初始化為0，再在主函數(shù)中調(diào)用它，實現(xiàn)求1+2+3+4+5的值，代碼如下：#include<stdio.h>intadd(inta);intmain(){ inti,z; /*局部變量*/ for(i=1;i<=5;i++) z=add(i); printf("z=%d\n",z); return0;}intadd(inta){ staticintc=0; /*靜態(tài)變量c*/ c=c+a; returnc;}上述代碼輸出的結(jié)果為“z=15”，說明函數(shù)add()并沒有在每次調(diào)用時將靜態(tài)變量c初始化為0，而是將c的值進行了累加。任務(wù)準備7.參數(shù)的傳值與傳址當函數(shù)的參數(shù)是基本數(shù)據(jù)類型（整型、字符型、浮點型、結(jié)構(gòu)體類型）時，屬于傳值調(diào)用。傳值調(diào)用是將實際參數(shù)的值復(fù)制一份給對應(yīng)的形式參數(shù)，當在函數(shù)中修改形式參數(shù)的值，并不會影響原實際參數(shù)的值?？梢哉J為傳值調(diào)用的實際參數(shù)是原件，而形式參數(shù)是實際參數(shù)的復(fù)印件，在復(fù)印件上亂畫并不會影響到原件。當函數(shù)的參數(shù)是數(shù)組類型、指針類型時，屬于傳址調(diào)用，也稱傳地址調(diào)用。傳址調(diào)用是將實際參數(shù)的地址復(fù)制一份給對應(yīng)的形式參數(shù)，在函數(shù)中就可以通過副本地址來修改原地址中的數(shù)據(jù)?？梢哉J為傳址調(diào)用的實際參數(shù)是一把鑰匙（地址），函數(shù)調(diào)用時會配一把相同的鑰匙給形式參數(shù)，通過鑰匙副本也能打開相同的房間，修改房間內(nèi)的數(shù)據(jù)。綜上所述，傳值調(diào)用無法修改原數(shù)據(jù)，但傳址調(diào)用能修改原數(shù)據(jù)。任務(wù)準備【實例3】定義一個傳值函數(shù)和一個傳址函數(shù)，在main()函數(shù)中調(diào)用它們，輸出調(diào)用前后的數(shù)據(jù)值。voidchangeVar(inta,intb);voidchangeArray(inta[]);intmain(){ intx=5,y=10,z[5]={8,4,9,12,7}; printf("調(diào)用函數(shù)前：x=%d,y=%d\n",x,y); changeVar(x,y); printf("調(diào)用函數(shù)后：x=%d,y=%d\n",x,y); printf("調(diào)用函數(shù)前：z[0]=%d,z[1]=%d\n",z[0],z[1]); changeArray(z); printf("調(diào)用函數(shù)后：z[0]=%d,z[1]=%d\n",z[0],z[1]); return0;}voidchangeVar(inta,intb) /*傳值*/{ a=a+1; b=b+1; printf("在函數(shù)中：a=%d,b=%d\n",a,b);}voidchangeArray(inta[]) /*傳址*/{ a[0]=a[0]+1; a[1]=a[1]+1;}任務(wù)準備編譯運行的結(jié)果如圖5-3所示：函數(shù)changeVar()的參數(shù)都是傳值，在該函數(shù)中修改了形式參數(shù)a和b的值，但并不影響實際參數(shù)x和y的值。函數(shù)changeArray()的參數(shù)是一維數(shù)組，是傳址調(diào)用，在該函數(shù)中通過下標就能修改數(shù)組中的數(shù)據(jù)。圖5-3傳值調(diào)用和傳址調(diào)用任務(wù)準備任務(wù)實施Part

1Part

2Part

3任務(wù)描述任務(wù)實施【任務(wù)1】定義一個函數(shù)，用冒泡排序法對一維整型數(shù)組進行排序。在main()函數(shù)中調(diào)用該函數(shù)對給定數(shù)組排序，然后輸出排序后的數(shù)組。1.任務(wù)分析本任務(wù)考查函數(shù)的定義、聲明和調(diào)用。凡是對一維數(shù)組進行操作的函數(shù)，都需要將數(shù)組的首地址和元素個數(shù)作為參數(shù)代入。因此，對一維整型數(shù)組進行冒泡排序的函數(shù)應(yīng)該代入數(shù)組名和元素個數(shù)，通過數(shù)組名和下標可以實現(xiàn)數(shù)組元素的交換。函數(shù)不需要返回任何數(shù)據(jù)，返回類型是void。由于經(jīng)常要輸出整個一維整型數(shù)組，所以也可以定義函數(shù)專用于輸出一維整型數(shù)組的元素。任務(wù)實施2.任務(wù)實現(xiàn)實現(xiàn)代碼如下，請將代碼中空白處補充完整。#include<stdio.h>voidmaopao(inta[],intn);/*聲明函數(shù)*/voidshuchu(inta[],intn);intmain(){ inttemp,i,j;inta[10]={76,66,23,19,-5,44,33,22,9,13}; printf("排序前:"); shuchu(a,10); maopao(a,10); /*調(diào)用函數(shù)進行排序*/ printf("\n排序后:"); shuchu(a,10); return0;}voidmaopao(inta[],intn)/*定義函數(shù)*/{ inti,j,temp; for(i=0;i<

;i++) for(j=0;j<

;j++) if(

) { temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; }}voidshuchu(inta[],intn)/*定義函數(shù)*/{ inti; for(i=0;i<10;i++) printf("%d,",a[i]);}任務(wù)實施編譯運行的結(jié)果如圖5-4所示：圖5-4冒泡排序任務(wù)實施3.任務(wù)總結(jié)冒泡排序的原理在項目四的任務(wù)1中有詳細的介紹，在此不再贅述。自定義函數(shù)maopao()之所以能交換數(shù)組元素，實現(xiàn)對一維數(shù)組排序，是因為函數(shù)將數(shù)組首地址作為參數(shù)傳入，通過數(shù)組的首地址和下標，可以修改數(shù)組中的任何數(shù)據(jù)。同理，調(diào)用函數(shù)對二維數(shù)組進行操作時，需要代入二維數(shù)組名、行數(shù)和列數(shù)。二維數(shù)組名代表第0行的首地址，通過行下標和列下標就能訪問二維數(shù)組中的每一個元素。任務(wù)實施【任務(wù)2】定義函數(shù)統(tǒng)計某整數(shù)中指定數(shù)字出現(xiàn)的次數(shù)，并在main()函數(shù)中調(diào)用。1.任務(wù)分析統(tǒng)計某整數(shù)中指定數(shù)字出現(xiàn)的次數(shù),如整數(shù)-21252中數(shù)字2的出現(xiàn)的次數(shù)為3。當整數(shù)或數(shù)字為負數(shù)時，難以判斷數(shù)字是否相等，因此需要將兩個數(shù)都變成正數(shù)。本任務(wù)中分別采用條件表達式和庫函數(shù)abs()來實現(xiàn)。判斷整數(shù)21252中是否出現(xiàn)數(shù)字2的思路是：從個位開始循環(huán)取出21252中的每個數(shù)字，再與數(shù)字2比較，如果相等就將數(shù)字2出現(xiàn)的次數(shù)加1。每次循環(huán)取出的個位數(shù)字、剩下的數(shù)和出現(xiàn)的次數(shù)如表5-1所示：表5-1循環(huán)詳情表第幾次循環(huán)取出的個位剩下整數(shù)是否等于22出現(xiàn)的次數(shù)第1次22125是1第2次5212否1第3次221是2第4次12否2第5次20是3循環(huán)結(jié)束

任務(wù)實施2.任務(wù)實現(xiàn)實現(xiàn)代碼如下，請將代碼中空白處補充完整。#include<stdio.h>#include<math.h>intcishu(intx,intsz); /*聲明函數(shù)*/intmain03(){ intx,sz,y; printf("請輸入一個整數(shù)和一個數(shù)字,以空格隔開:"); scanf("%d%d",&x,&sz); y=cishu(

,

); /*調(diào)用函數(shù)*/ printf("數(shù)字%d在整數(shù)%d中出現(xiàn)的次數(shù)是:%d\n",sz,x,y); return0;}intcishu(intx,intsz) /*定義函數(shù)*/{ /*gw存儲每次從x中取出的個位上的數(shù)字,cs用于記錄sz出現(xiàn)的次數(shù)*/ intgw,cs=0; /*先把x和sz都變成絕對值*/ sz=(sz>0?sz:-1*sz);/*條件表達式*/ x=abs(x); /*調(diào)用庫函數(shù)求絕對值*/ /*循環(huán)取出x個位上的數(shù)字*/ while(x!=0) { gw=

;/*取出x的個位數(shù)字*/ /*個位gw與數(shù)字sz相等,次數(shù)加1*/ if(

) cs++; x=

;/*去掉x的個位數(shù)字*/ } returncs;}任務(wù)實施編譯運行的結(jié)果如圖5-5所示：圖5-5統(tǒng)計數(shù)字出現(xiàn)的次數(shù)任務(wù)實施3.任務(wù)總結(jié)統(tǒng)計某整數(shù)中指定數(shù)字出現(xiàn)次數(shù)的cishu()函數(shù)，需要代入某整數(shù)和數(shù)字，返回數(shù)字出現(xiàn)的次數(shù)。循環(huán)取出某整數(shù)的個位數(shù)字后，再通過除以10去除個位數(shù)字，直到該整數(shù)等于0為止。這種逐個取出個位數(shù)字的算法很高效且實用。任務(wù)準備任務(wù)實施任務(wù)描述任務(wù)2用函數(shù)解決數(shù)學(xué)難題任務(wù)描述有到這樣一道數(shù)學(xué)題：求滿足abcd*e=fghi的式子，其中a～i是1～9之間的數(shù)字且各不相等，即一個四位數(shù)乘以一個數(shù)字等于另一個四位數(shù)。與數(shù)學(xué)的解法不同，程序更傾向于用循環(huán)、比較和判斷來解決問題，通過多次嘗試和比較來找出答案。初學(xué)者容易犯的錯誤是用九層嵌套循環(huán)來拼湊出符合等式的數(shù)，這樣做雖然能得出答案，但不推薦這種“蠻力”式編程。在學(xué)習(xí)了函數(shù)的定義和調(diào)用后，我們可以將解這道數(shù)學(xué)題的過程進行模塊（或功能）劃分，將每個模塊（或功能）編寫成函數(shù)，這樣就能將問題大大簡化。任務(wù)準備任務(wù)實施Part

1Part

2Part

3任務(wù)描述任務(wù)準備由題目“a～i是1～9之間的數(shù)字且各不相等”的要求可得出如下限制條件：（1）四位數(shù)abcd和fghi不能包含數(shù)字e。（2）四位數(shù)abcd和fghi不能包含0。（3）四位數(shù)abcd中不能有重復(fù)的數(shù)字，四位數(shù)fghi中不能有重復(fù)的數(shù)字。（4）四位數(shù)abcd與fghi不能有相同的數(shù)字。經(jīng)過上述分析，可以從解這道數(shù)學(xué)題的過程中劃分出三個小功能，定義成如下三個函數(shù)：（1）判斷一個四位數(shù)是否包含某個數(shù)字的函數(shù)。判斷四位數(shù)abcd是否包含數(shù)字e、判斷四位數(shù)abcd是否包含0，都可以調(diào)用該函數(shù)。（2）判斷一個四位數(shù)中是否有重復(fù)數(shù)字的函數(shù)。（3）判斷一個四位數(shù)是否與另一個四位數(shù)有相同數(shù)字的函數(shù)。完成上述三個函數(shù)的編寫，基本就能解出這道數(shù)學(xué)題的答案了。任務(wù)準備1.判斷一個四位數(shù)是否包含某個數(shù)字的函數(shù)定義判斷一個四位數(shù)是否包含某個數(shù)字的函數(shù)，需要將這個四位數(shù)、某個數(shù)字作為參數(shù)代入，返回“是”或“否”。在C語言中，一般用“1”代表“是”，用“0”代表“否”，因此，該函數(shù)的返回類型應(yīng)該是int。在實現(xiàn)該函數(shù)代碼時，初學(xué)者最先想的就是分別求出這個四位數(shù)的個、十、百、千位上的數(shù)字，再與代入的數(shù)字比較，判斷它們是否相等，就知道這個四位數(shù)是否包含某個數(shù)字。這種做法不推薦，因為下次需要判斷一個九位數(shù)是否包含某個數(shù)字時，就需要定義9個變量存儲各位上的數(shù)字，它們與代入的數(shù)字比較的條件也變得很繁瑣。簡而言之，這種做法不具有通用性。任務(wù)準備可以考慮將函數(shù)功能設(shè)計成判斷一個多位數(shù)是否包含某個數(shù)字，實現(xiàn)的思路是：從多位數(shù)的個位開始，循環(huán)依次取出該多位數(shù)中的數(shù)字與某數(shù)字比較，只要有相等的情況出現(xiàn)，就說明該多位數(shù)包含某個數(shù)字。函數(shù)的定義如下：intbaohan(intabcd,inte){ intgw,flag=0; /*假定flag=0代表不包含*/ while(abcd>0){ gw=abcd%10; /*取出個位*/ abcd=abcd/10; /*去掉個位*/ if(gw==e){ flag=1; /*flag=1代表包含*/ break; /*跳出while循環(huán)*/ }

} returnflag;}任務(wù)準備在baohan()函數(shù)的實現(xiàn)代碼中，將變量flag賦值為0，用于假定多位數(shù)abcd不包含數(shù)字e。在while循環(huán)中，每次將abcd切割成個位數(shù)字和其余部分，個位數(shù)字存于變量gw中，其余部分仍然存到abcd中。每次循環(huán)都將個位數(shù)字gw與數(shù)字e比較，如果它們相等就說明這個多位數(shù)包含數(shù)字e，將變量flag修改為1，并跳出循環(huán)。如果gw始終沒有與e相等，循環(huán)會在abcd等于0時結(jié)束。循環(huán)結(jié)束后，變量flag的值為1就代表包含，為0就代表不包含。以判斷多位數(shù)123456是否包含數(shù)字2為例，循環(huán)過程中各變量的值如表5-2所示：表5-2baohan()函數(shù)的循環(huán)過程第幾次循環(huán)變量gw變量abcd數(shù)字egw與e變量flag第1次6123452不等0第2次512342不等0第3次41232不等0第4次3122不等0第5次212相等1跳出循環(huán)

任務(wù)準備【實例1】輸入一個多位數(shù)和一個數(shù)字，定義并調(diào)用自定義函數(shù)，判斷多位數(shù)是否包含輸入的數(shù)字。#include<stdio.h>intbaohan(intabcd,inte); /*聲明函數(shù)*/intmain(){ intx,y,f; printf("請輸入一個多位整數(shù)和一個數(shù)字:"); scanf("%d,%d",&x,&y); f=baohan(x,y);/*調(diào)用函數(shù)*/ if(f==1) printf("多位數(shù)%d包含數(shù)字%d\n",x,y); else printf("多位數(shù)%d不包含數(shù)字%d\n",x,y); return1;}intbaohan(intabcd,inte) /*定義函數(shù)*/{ intgw,flag=0; while(abcd>0) { gw=abcd%10; if(gw==e) { flag=1; break; } abcd=abcd/10; } returnflag;}任務(wù)準備編譯運行，分別輸入“123456,2”和“123456,7”的結(jié)果如圖5-6所示：函數(shù)baohan()只返回1或0來代表包含或不包含，而不是以文字形式輸出是否包含，體現(xiàn)了函數(shù)功能應(yīng)該單一的原則。而它能判斷一個多位數(shù)是否包含某個數(shù)字，而不僅僅局限于四位數(shù)，體現(xiàn)了函數(shù)應(yīng)該具有通用性的原則。圖5-6判斷多位數(shù)是否包含數(shù)字任務(wù)準備2.判斷一個四位數(shù)中是否有重復(fù)數(shù)字的函數(shù)定義判斷一個四位數(shù)中是否有重復(fù)數(shù)字的函數(shù)，需要將這個四位數(shù)作為參數(shù)代入，返回“1”或“0”，分別代表“有重復(fù)數(shù)字”和“無重復(fù)數(shù)字”，因此返回類型應(yīng)該是int。同樣，將此函數(shù)拓展成判斷一個多位整數(shù)中是否有重復(fù)數(shù)字，實現(xiàn)的思路是：循環(huán)多次，每次將多位數(shù)切割成個位數(shù)字和其余部分，調(diào)用自定義函數(shù)baohan()判斷其余部分是否包含個位數(shù)字，直到其余部分變成0時循環(huán)結(jié)束，或其余部分包含個位數(shù)字時跳出循環(huán)。任務(wù)準備函數(shù)的定義如下：intchongfu(intabcd){ intgw,flag=0;/*先假定沒有重復(fù)數(shù)字，用flag=0表示*/ while(abcd>0) { gw=abcd%10; /*將多位數(shù)切割成個位和其余部分*/ abcd=abcd/10; if(baohan(abcd,gw)==1) /*調(diào)用另一個自定義函數(shù)baohan()*/ { flag=1;/*其余部分包含個位數(shù)字，說明有重復(fù)數(shù)字*/ break; } } returnflag;}任務(wù)準備在chongfu()函數(shù)的實現(xiàn)代碼中，將變量flag賦值為0，用于假定多位數(shù)abcd中沒有重復(fù)數(shù)字。在while循環(huán)中，每次將abcd切割成個位數(shù)字和其余部分，個位數(shù)字存于變量gw中，其余部分仍然存到abcd中。每次循環(huán)都調(diào)用自定義函數(shù)baohao()判斷其余部分abcd是否包含個位數(shù)字gw，如果包含就說明多位數(shù)中有重復(fù)數(shù)字，將變量flag修改為1，并跳出循環(huán)。如果始終沒有出現(xiàn)包含的情況，循環(huán)會在abcd等于0時結(jié)束。循環(huán)結(jié)束后，變量flag的值為1就代表多位數(shù)有重復(fù)數(shù)字，為0就代表沒有重復(fù)數(shù)字。以判斷多位數(shù)12324567是否有重復(fù)數(shù)字為例，循環(huán)過程中各變量的值如表5-3所示：表5-3chongfu()函數(shù)的循環(huán)過程第幾次循環(huán)變量gw變量abcdabcd是否包含gw變量flag第1次71232456否0第2次6123245否0第3次512324否0第4次41232否0第5次2123是1跳出循環(huán)

任務(wù)準備【實例2】輸入一個多位數(shù)，定義并調(diào)用自定義函數(shù)，判斷輸入的多位數(shù)中是否有重復(fù)數(shù)字。#include<stdio.h>intbaohan(intabcd,inte);intchongfu(intabcd);intmain(){ intx,f; printf("請輸入一個多位整數(shù):"); scanf("%d",&x); f=chongfu(x); if(f==1) printf("多位數(shù)%d中有重復(fù)數(shù)字",x); else printf("多位數(shù)%d中沒有重復(fù)數(shù)字",x); return1;}/*判斷多位數(shù)abcd中是否有重復(fù)的數(shù)字*/intchongfu(intabcd){ intgw,flag=0; while(abcd>0) { gw=abcd%10; abcd=abcd/10; if(baohan(abcd,gw)==1) { flag=1; break; } } returnflag;}任務(wù)準備編譯運行，分別輸入“12324567”和“1234567”的結(jié)果如圖5-7所示：本實例中省略了函數(shù)baohan()的定義代碼。在定義chongfu()函數(shù)時調(diào)用了另一個自定義函數(shù)baohan()，充分說明各函數(shù)之間可以相互調(diào)用，但唯獨main()函數(shù)不能被其他函數(shù)調(diào)用。圖5-7判斷一個多位數(shù)是否有重復(fù)數(shù)字任務(wù)準備3.判斷兩個四位數(shù)是否有相同的數(shù)字的函數(shù)定義判斷兩個四位數(shù)是否有相同的數(shù)字的函數(shù)，需要將兩個四位數(shù)作為參數(shù)代入，返回“1”或“0”，分別代表“有相同數(shù)字”和“無相同數(shù)字”，因此返回類型應(yīng)該是int。將此函數(shù)拓展成判斷兩個多位整數(shù)是否有相同的數(shù)字，實現(xiàn)的思路是：假設(shè)兩個多位整數(shù)分別是abcd和fghi，循環(huán)多次，每次取出fghi中的一個數(shù)字，調(diào)用自定義函數(shù)baohan()判斷abcd是否包含這個數(shù)字，直到取完fghi中的數(shù)字時循環(huán)結(jié)束，或abcd包含fghi中的某個數(shù)字時跳出循環(huán)。任務(wù)準備函數(shù)的定義如下：intxiangtong(intabcd,intfghi){ intgw,flag=0; /*先假定abcd不包含fghi中的數(shù)字*/ while(fghi>0) { gw=fghi%10; /*取出fghi中的個位數(shù)字*/ fghi=fghi/10; /*去掉fghi中的個位數(shù)字*/ if(baohan(abcd,gw)==1) /*abcd包含fghi中的數(shù)字*/ { flag=1; break; } } returnflag;}任務(wù)準備在xiangtong()函數(shù)的實現(xiàn)代碼中，將變量flag賦值為0，用于假定多位數(shù)abcd不包含多位數(shù)fghi中的數(shù)字。在while循環(huán)中，每次將fghi切割成個位數(shù)字和其余部分，個位數(shù)字存于變量gw中，其余部分仍然存到fghi中。每次循環(huán)都調(diào)用自定義函數(shù)baohao()判斷abcd是否包含個位數(shù)字gw，如果包含就說明兩個多位數(shù)有相同數(shù)字，將變量flag修改為1，并跳出循環(huán)。如果始終沒有出現(xiàn)包含的情況，循環(huán)會在fghi等于0時結(jié)束。循環(huán)結(jié)束后，變量flag的值為1就代表兩個多位數(shù)有相同的數(shù)字，為0就代表沒有相同數(shù)字。以判斷多位數(shù)123456與456789是否有重復(fù)數(shù)字為例，循環(huán)過程中各變量的值如表5-4所示：表5-4chongfu()函數(shù)的循環(huán)過程第幾次循環(huán)變量gw變量fghi變量abcdabcd是否包含gw變量flag第1次945678123456否0第2次84567123456否0第3次7456123456否0第4次645123456是1跳出循環(huán)

任務(wù)準備【實例3】輸入兩個多位數(shù)，定義并調(diào)用自定義函數(shù)，判斷兩個多位數(shù)是否有相同數(shù)字。#include<stdio.h>intbaohan(intabcd,inte);intxiangtong(intabcd,intfghi);intmain(){ intx,y,f; printf("請輸入兩個多位整數(shù):"); scanf("%d,%d",&x,&y); f=xiangtong(x,y); if(f==1) printf("%d與%d有相同的數(shù)字",x,y); else printf("%d與%d沒有相同的數(shù)字",x,y); return1;}/*判斷兩個多位數(shù)abcd與fghi是否有相同的數(shù)字*/intxiangtong(intabcd,intfghi){ intgw,flag=0; while(fghi>0) { gw=fghi%10; fghi=fghi/10; if(baohan(abcd,gw)==1) { flag=1; break; } } returnflag;}任務(wù)準備編譯運行，分別輸入“123456,456789”和“123456,7890”的結(jié)果如圖5-8所示：本實例中也省略了函數(shù)baohan()的定義代碼。從實例2和實例3可以看出，自定義函數(shù)chongfu()和xiangtong()依賴調(diào)用函數(shù)baohan()提供的基礎(chǔ)功能，使自身的實現(xiàn)代碼變得簡單易懂。圖5-8判斷兩個多位數(shù)是否有相同數(shù)字任務(wù)準備任務(wù)實施Part

1Part

2Part

3任務(wù)描述任務(wù)實施【任務(wù)1】a～i是1～9中的各不相同的數(shù)字，且滿足式子abcd*e=fghi。請輸出滿足要求的式子。1.任務(wù)分析在任務(wù)準備中，我們已經(jīng)將解決這道數(shù)學(xué)題會用到的三個功能寫成了函數(shù)，它們分別是判斷一個四位數(shù)是否包含某個數(shù)字的函數(shù)、判斷一個四位數(shù)中是否有重復(fù)數(shù)字的函數(shù)、判斷兩個四位數(shù)是否有相同的數(shù)字的函數(shù)。接下來梳理解決這道數(shù)學(xué)題的思路，通過調(diào)用這三個功能，得出解決問題的流程。任務(wù)實施解決該題的流程如下：（1）讓abcd取每一個四位數(shù)的值，即從1000遞增到9999。（2）如果abcd包含0，或者abcd中有重復(fù)數(shù)字，說明abcd不符合題意的要求，舍棄當前值后，取下一個值。（3）如果abcd不包含0且abcd中沒有重復(fù)數(shù)字，則讓e的值從2遞增到9。（4）如果abcd包含數(shù)字e，說明e不符合題意的要求，舍棄e的當前值后，取下一個值。（5）如果abcd不包含數(shù)字e，則計算它們的乘積，用fghi存儲。（6）根據(jù)題意的要求，如果乘積fghi滿足以下五個條件，則找到了滿足題意的一個式子。必須滿足的五個條件如下：①fghi是一個四位數(shù)。②fghi不包含0。③fghi不包含數(shù)字e。④fghi中沒有重復(fù)數(shù)字。⑤fghi與abcd沒有相同數(shù)字。任務(wù)實施根據(jù)上述流程分析，得出解決這道數(shù)學(xué)題的偽代碼如下：intabcd,e,fghi;for(abcd=1000;abcd<10000;abcd++){ if(abcd中有重復(fù)數(shù)字||abcd包含0) continue; /*不再向下執(zhí)行,直接跳轉(zhuǎn)到abcd++*/ for(e=2;e<10;e++) /*e取值2～9*/ { if(abcd包含數(shù)字e) continue; /*跳轉(zhuǎn)到e++*/ fghi=abcd*e; if(fghi是四位數(shù)&&fghi不包含0 &&fghi不包含數(shù)字e&&fghi中沒有重復(fù)數(shù)字&&fghi與abcd沒有相同數(shù)字) /*輸出滿足條件的等式*/ }}任務(wù)實施2.任務(wù)實現(xiàn)實現(xiàn)代碼如下，請將代碼中空白處補充完整。#include<stdio.h>intbaohan(intabcd,inte);intchongfu(intabcd);intxiangtong(intabcd,intfghi);intmain(){ intabcd,e,fghi; for(abcd=1000;abcd<10000;abcd++) { if(chongfu(abcd)==1||baohan(abcd,0)==1) /*不再向下執(zhí)行,直接跳轉(zhuǎn)到abcd++*/

; for(e=2;e<10;e++) { if(

) continue; /*跳轉(zhuǎn)到e++*/ fghi=abcd*e;/*求出乘積*/ if(fghi<10000&&baohan(fghi,0)==

&&baohan(fghi,e)==

&&chongfu(fghi)==

&&xiangtong(abcd,fghi)==

) printf("%d*%d=%d\n",abcd,e,fghi); } } return0;}/*函數(shù)baohan()、chongfu()、xiangtong()代碼省略*/任務(wù)實施編譯運行的結(jié)果如圖5-9所示：圖5-9滿足abcd*e=fghi的式子任務(wù)實施3.任務(wù)總結(jié)本任務(wù)列出了式子abcd*e=fghi中，乘數(shù)abcd、乘數(shù)e和乘積fghi必須滿足的要求，針對它們的每一個取值都進行嚴格的檢測，只有通過檢測才能進入下一個環(huán)節(jié)的運算。continue語句的使用極大地簡化的程序，當abcd或e不滿足要求時，調(diào)用continue語句便不再往下執(zhí)行，而是跳轉(zhuǎn)到abcd++或e++，舍棄當前取值，直接進入下一個取值的判斷。返回值為int類型的函數(shù)，可以當作一個int類型的變量使用。因此，類似“baohan(fghi,0)==0”或“chongfu(abcd)==1”的關(guān)系表達式的用法與“x==1”是一樣的，可以將函數(shù)baohan()和chongfu()直接當作變量使用。任務(wù)準備任務(wù)實施任務(wù)描述任務(wù)3用遞歸函數(shù)解決特殊問題任務(wù)描述大家小時候或許聽過這樣一個故事：“從前有座山，山上有座廟，廟里有個老和尚。老和尚他說：從前有座山，山上有座廟，廟里有個老和尚。老和尚他說：……”這個故事的特點是故事里的人物講述了故事本身，這導(dǎo)致故事陷入無限循環(huán)之中，永遠講不完。那么這個故事在什么情況下會結(jié)束呢？如果在第n個的故事中講故事的老和尚去世了，那么這個故事就可以完結(jié)了。像這種故事中講述了故事本身的現(xiàn)象，我們稱之為“遞歸”。同樣，如果一個函數(shù)在定義時調(diào)用了它本身，我們稱這種函數(shù)為“遞歸函數(shù)”。本任務(wù)將會定義一些遞歸函數(shù)解決一些特殊類型的問題，例如求某數(shù)的階乘、求第幾個Fibonacci數(shù)、解決猴子吃桃的問題等。通過這些例子，向?qū)W生講解遞歸函數(shù)的定義、遞歸函數(shù)的使用條件，讓學(xué)生掌握使用遞歸函數(shù)解決特殊問題的能力。任務(wù)準備任務(wù)實施Part

1Part

2Part

3任務(wù)描述任務(wù)準備遞歸是一個在數(shù)學(xué)和計算機科學(xué)領(lǐng)域常用的概念，它指的是在定義函數(shù)或解決問題時，該函數(shù)會調(diào)用自身作為一個參數(shù)或者解決方案的一部分。這個過程可以被視為一種自我參照的方式，通過不斷調(diào)用自身來處理越來越小的部分，直到最終能夠完全解決問題。遞歸的一個關(guān)鍵特性是它可以避免重復(fù)計算，因為它總是依賴于之前的計算結(jié)果。任務(wù)準備1.遞歸函數(shù)的定義函數(shù)在定義的時候直接或間接調(diào)用了它本身，這種函數(shù)叫遞歸函數(shù)。正整數(shù)n的階乘指1*2*3*…*n的結(jié)果，用n!來表示，記作：n!=1*2*3*…*n。將求n!的過程定義成一個遞歸函數(shù)，代碼如下：intjc(intn){ intsum; if(n==1) sum=1; else sum=n*jc(n-1);/*調(diào)用函數(shù)本身*/ returnsum;}從jc()函數(shù)的函數(shù)體代碼可以看出，該函數(shù)在定義時調(diào)用了它本身，符合遞歸函數(shù)的定義。任務(wù)準備【實例1】分別輸入一個正整數(shù)，定義并調(diào)用普通函數(shù)和遞歸函數(shù)，求該整數(shù)的階乘并輸出。#include<stdio.h>intjc(intn);intjc02(intn);intmain(){ intx,s; printf("請輸入一個12以內(nèi)的正整數(shù):"); scanf("%d",&x); s=jc02(x); printf("普通函數(shù)求階乘:%d!=%d\n",x,s); printf("請輸入一個12以內(nèi)的正整數(shù):"); scanf("%d",&x); s=jc(x); printf("遞歸函數(shù)求階乘:%d!=%d\n",x,s) return1;}/*定義遞歸函數(shù),用于求n的階乘*/intjc(intn){ intsum; if(n==1) sum=1; else sum=n*jc(n-1); returnsum;}/*定義普通函數(shù),用于求n的階乘*/intjc02(intn){ intsum=1,i; for(i=1;i<=n;i++) sum=sum*i; returnsum;}任務(wù)準備編譯運行，分別輸入“5”和“6”的結(jié)果圖5-10所示：從結(jié)果圖可以看出，調(diào)用普通函數(shù)和遞歸函數(shù)求階乘，都能得出正確的結(jié)果。普通函數(shù)jc02()采用循環(huán)求n!。將循環(huán)變量i從1遞增到n，每次循環(huán)都將i的取值乘到sum上，循環(huán)結(jié)束就能得到1*2*3*…*n的值。遞歸函數(shù)jc()采用遞推方法將求n!變成求(n-1)!，因為n!=n*(n-1)!。以此類推可得遞推關(guān)系：n!→(n-1)!→(n-2)!→…→2!→1!。而1的階乘很容易得出結(jié)果是1，經(jīng)過回歸運算能得到2!=2、3!=6……最終能求得n!的值。圖5-10求階乘任務(wù)準備2.遞歸函數(shù)的推導(dǎo)能用遞歸函數(shù)解決的問題，必須滿足以下兩個條件：（1）問題規(guī)模可以轉(zhuǎn)化。即可以將原問題的求解轉(zhuǎn)化成一個新問題的求解，兩個問題解決方法一樣，只是規(guī)模大小不同的情況。如將求n!轉(zhuǎn)化成求(n-1)!，再將求(n-1)!轉(zhuǎn)化成求(n-2)!，直至最后轉(zhuǎn)化成求1!。（2）有明確的結(jié)束遞歸的條件。即在適當?shù)臈l件下可以結(jié)束遞歸調(diào)用。如當n為1時得出1!為1，遞歸調(diào)用在這里結(jié)束，經(jīng)過回歸運算就能依次求出2!、3!…n!。根據(jù)遞歸問題的適用條件，可以歸納出定義遞歸函數(shù)的兩個步驟：（1）尋找遞歸表達式。尋找遞歸表達式就是找出問題規(guī)模轉(zhuǎn)化的式子。以求n!為例，f(n)表示求n的階乘，遞歸表達式為f(n)=n*f(n-1)，該式子成功將求n!轉(zhuǎn)化為求(n-1)!，使將求n!最終轉(zhuǎn)化成求1!成為可能。（2）尋找遞歸的出口。尋找遞歸的出口就是找出遞歸的結(jié)束條件。以求n!為例，當n等于1時得出1!等于1，遞歸調(diào)用在這里結(jié)束。任務(wù)準備經(jīng)過上述兩個步驟的分析，最終可以得出求解遞歸問題的遞推公式，該公式簡明地給出了遞歸表達式和遞歸的結(jié)束條件。以f(n)表示求n的階乘，遞推公式如下：斐波那契（Fibonacci）數(shù)列是指這樣一個數(shù)列：1，1，2，3，5，8，13，21，34，55，89……這個數(shù)列的前兩項均定義為1，從第3項開始，每一項都等于前兩項之和。由Fibonacci數(shù)列的規(guī)律可以推斷出它的遞推公式如下：任務(wù)準備由Fibonacci數(shù)列的遞推公式可以輕松寫出對應(yīng)遞歸函數(shù)的定義：intfibo(intn){ ints; if(n==1||n==2) s=1; /*第1、2項都是1*/ else s=fibo(n-1)+fibo(n-2); /*從第3項開始,每項是前2項之和*/ returns;}任務(wù)準備【實例2】分別輸入一個正整數(shù)n，定義并調(diào)用普通函數(shù)和遞歸函數(shù)，求第n個Fibonacci數(shù)并輸出。#include<stdio.h>intfibo(intn);intfibo02(intn);intmain(){ intn,result; printf("請輸入一個正整數(shù):"); scanf("%d",&n); result=fibo02(n); printf("普通函數(shù)求得第%d個Fibonacci數(shù)是:%d\n",n,result); printf("請輸入一個正整數(shù):"); scanf("%d",&n); result=fibo(n); printf("遞歸函數(shù)求得第%d個Fibonacci數(shù)是:%d\n",n,result); return1;}intfibo(intn){ ints; if(n==1||n==2) s=1; else s=fibo(n-1)+fibo(n-2); returns;}任務(wù)準備intfibo02(intn){ intx1,x2,x,i; if(n==1||n==2) x=1; else{ x1=1; x2=1; for(i=3;i<=n;i++) {/*第3項開始,每項是前2項之和*/ x=x1+x2; x1=x2; x2=x; } } returnx;}圖5-11求第n個Fibonacci數(shù)編譯運行，分別輸入“6”和“7”的結(jié)果如圖5-11所示：任務(wù)準備與Fibonacci數(shù)列（1，1，2，3，5，8，13，21，34，55，89……）對比，實例2的輸出結(jié)果是正確的。普通函數(shù)fibo02()中定義x、x1和x2三個變量，分別存儲第n項和它前面兩項的數(shù)值。當n等于1或2時，第n項的數(shù)值為1。當n大于等于3時，第n項的數(shù)值為前面兩項的數(shù)值之和，用循環(huán)來實現(xiàn)，在循環(huán)過程中不斷修改x、x1和x2的值。遞歸函數(shù)fibo()的實現(xiàn)思路就比較簡單，當n等于1或2時，第n項的數(shù)值為1。當n大于等于3時，將求第n項轉(zhuǎn)化為求第n-1項和第n-2項的和，即將求fibo(n)轉(zhuǎn)化為求fibo(n-1)+fibo(n-2)之和。從此，對于n大于等于3的某項，都可以遞推成求前面兩項之和，直到最終轉(zhuǎn)化成若干個fibo(1)和fibo(2)之和，就能輕易得出某項的數(shù)值，再經(jīng)過回歸運算，算出fibo(n)的結(jié)果。任務(wù)準備3.遞歸函數(shù)的執(zhí)行過程一個遞歸函數(shù)的調(diào)用過程類似于多個函數(shù)的嵌套的調(diào)用，只不過調(diào)用函數(shù)和被調(diào)用函數(shù)是同一個函數(shù)。遞歸函數(shù)調(diào)用的執(zhí)行過程分為兩個階段：（1）遞推階段：從原問題出發(fā)，按遞歸公式遞推，最終達到遞歸終止條件。（2）回歸階段：按遞歸終止條件求出結(jié)果，逆向逐步代入遞歸公式，回歸到原問題求解。為了保證遞歸函數(shù)的正確執(zhí)行，系統(tǒng)需設(shè)立一個工作棧。棧（stack）是一種運算受限的線性表，限定僅在表尾進行插入和刪除操作的線性表。棧的一端被稱為棧頂，另一端稱為棧底。向一個棧插入新元素又稱作進棧、入?；驂簵?，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個棧刪除元素又稱作出?；蛲藯?，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素。棧內(nèi)數(shù)據(jù)遵循“先進后出，后進先出”的原則，即最先存入棧里的數(shù)據(jù)最后才能取出來。由于棧的大小不是無限的，所以，遞歸調(diào)用的次數(shù)過多會導(dǎo)致棧溢出，程序無法正常運行。可以把棧比作一個杯子，杯口的大小剛好能放入一個雞蛋，把雞蛋比作棧內(nèi)的元素。因此，每次向杯里放入雞蛋時，該雞蛋都處于最頂端；而對于杯里的雞蛋來說，最先放進去的雞蛋最后才能取出，遵循“先進后出，后進先出”的原則；將雞蛋放入杯里叫“入?！?，從杯里取出雞蛋叫“出?！薄Ｈ蝿?wù)準備以在某函數(shù)中執(zhí)行遞歸調(diào)用為例，將該函數(shù)稱為A，它執(zhí)行的遞歸函數(shù)稱為B，那么在A中遞歸調(diào)用B的內(nèi)部執(zhí)行過程如下:（1）運行開始時，首先為遞歸調(diào)用建立一個工作棧，其結(jié)構(gòu)包括參數(shù)、局部變量和返回地址。（2）每次執(zhí)行遞歸調(diào)用B之前，把函數(shù)A的參數(shù)、局部變量的當前值以及調(diào)用后的返回地址壓棧;（3）每次遞歸調(diào)用B結(jié)束后，將棧頂元素出棧，使相應(yīng)的參數(shù)和局部變量恢復(fù)為調(diào)用前的值，然后轉(zhuǎn)向返回地址指定的位置繼續(xù)執(zhí)行函數(shù)A。任務(wù)準備以用遞歸函數(shù)jc()求6！的執(zhí)行過程為例，先是將求jc(6)遞推到求jc(1)，在得出jc(1)的結(jié)果為1后，又回歸進行代入運算，求出jc(6)的結(jié)果。該遞歸函數(shù)的遞推和回歸過程、出入棧情況如表5-5所示：表5-5jc(6)的執(zhí)行過程jc(6)過程階段出入棧=>6*jc(5)遞推參數(shù)6、局部變量s、jc(6)地址入棧=>6*(5*jc(4))遞推參數(shù)5、局部變量s、jc(5)地址入棧=>6*(5*(4*jc(3)))遞推參數(shù)4、局部變量s、jc(4)地址入棧=>6*(5*(4*(3*jc(2))))遞推參數(shù)3、局部變量s、jc(3)地址入棧=>6*(5*(4*(3*(2*jc(1)))))遞推參數(shù)2、局部變量s、jc(2)地址入棧=>6*(5*(4*(3*(2*1))))

=>6*(5*(4*(3*2)))回歸參數(shù)2、局部變量s、jc(2)地址出棧=>6*(5*(4*6))回歸參數(shù)3、局部變量s、jc(3)地址出棧=>6*(5*24)回歸參數(shù)4、局部變量s、jc(4)地址出棧=>6*120回歸參數(shù)5、局部變量s、jc(5)地址出棧=>720回歸參數(shù)6、局部變量s、jc(6)地址出棧任務(wù)準備2010年上映的美國電影《盜夢空間》，是一部萊昂納多·迪卡普里奧主演的科幻電影，它所講述的故事情節(jié)就類似遞歸函數(shù)的執(zhí)行過程。該電影的主線情節(jié)是：日本大亨齋藤給男主角柯布（萊昂納多·迪卡普里奧飾）的任務(wù)是，讓競爭對手的繼承人費舍放棄繼承家業(yè)，那樣齋藤的公司就可以生存下去。所以柯布需要做的就是把“放棄繼承家業(yè)”這種想法植入到費舍的潛意識中。為了在夢中向費舍的潛意識植入放棄繼承家業(yè)的想法，柯布和他的團隊一共創(chuàng)造了四層夢境，即夢中還有夢。第一層夢是在城市街道上，柯布團隊遭遇追殺，在大巴即將墜河時，他們創(chuàng)造并進入了第二層夢境；第二層夢是在賓館里，在這里柯布團隊創(chuàng)造并進入了第三層夢境；第三層夢是在雪地堡壘里，在這里柯布團隊又創(chuàng)造并進入了第四層夢境；第四層夢來到奇幻海灘，在這層夢里成功將想法植入到費舍的潛意識中；最后柯布團隊從一層層的夢境中醒來，回到了現(xiàn)實世界。在電影《盜夢空間》中，每次進入一層夢境，就好比調(diào)用了一次遞歸函數(shù)。當在第一層夢中無法達到植入潛意識的目的時，將實現(xiàn)該目的遞推給第二層夢，以此類推，直到遞推到第四層夢時才實現(xiàn)了植入潛意識的目的。于是，從夢境中層層回歸，最終回到現(xiàn)實世界。因此，可以認為電影《盜夢空間》拍出了遞歸函數(shù)的執(zhí)行過程。任務(wù)準備任務(wù)實施Part

1Part

2Part

3任務(wù)描述任務(wù)實施【任務(wù)1】分別定義普通函數(shù)和遞歸函數(shù)，解決猴子吃桃問題：猴子第1天摘了若干個桃子，當即吃了一半，還不解饞，又多吃了一個；第2天，吃剩下的桃子的一半，還不過癮，又多吃了一個；以后每天都吃前一天剩下的一半多一個，到第10天想再吃時，只剩下一個桃子了。問第1天共摘了多少個桃子？。任務(wù)實施1.任務(wù)分析定義函數(shù)時，首先要分析函數(shù)帶入什么參數(shù)，返回什么類型。針對猴子吃桃的問題，不應(yīng)該于僅局限于求第1天有多少桃子，而應(yīng)該定義函數(shù)求第幾天有多少桃子。因此，本任務(wù)中的自定義函數(shù)應(yīng)該代入第幾天作為參數(shù)，返回這一天的桃子數(shù)量。由于第10天桃子數(shù)量為1，定義普通函數(shù)tz02()求第n天的桃子數(shù)量時，可以利用循環(huán)從第9天遞減到第n天，每天的桃子數(shù)量都等于前一天桃子數(shù)量加1后乘以2。由于第10天桃子數(shù)量為1，定義遞歸函數(shù)tz()求第n天的桃子數(shù)量時，遞推公式有如下兩種：tz(n)=2*(tz(n+1)+1) ……①tz(n)=tz(n-1)/2-1 ……②那么哪一個遞推公式是正確的呢？前面有提到，定義遞歸函數(shù)時有兩個步驟：尋找遞歸表達式和遞歸出口。公式①和②都是遞歸表達式，而遞歸的出口是n=10時桃子數(shù)量為1，n的取值范圍是1≤n<10。遞推公式②只會讓n的取值越推越小，無法到達遞歸的出口n=10；而遞推公式①會讓n的取值越推越大，當n=10時得到結(jié)果1，結(jié)束遞歸調(diào)用。因此，遞推公式①才是正確的遞歸表達式。任務(wù)實施2.任務(wù)實現(xiàn)本任務(wù)實現(xiàn)代碼如下，請將代碼中空白處補充完整。#include<stdio.h>inttz(intn);inttz02(intn);intmain(){ intn,s; printf("第幾天(1-10):"); scanf("%d",&n); s=tz02(n); printf("普通函數(shù)求得第%d天的桃子數(shù)量是:%d\n",n,s); printf("第幾天(1-10):"); scanf("%d",&n); s=tz(n); printf("遞歸函數(shù)求得第%d天的桃子數(shù)量是:%d\n",n,s); return1;}/*遞歸函數(shù),求第n天的桃子數(shù)量*/inttz(intn) /*n屬于1～10*/{ intsum; if(n==10) sum=; /*第10天只剩下1個*/ else sum=; returnsum;}任務(wù)實施/*普通函數(shù),求第n天的桃子數(shù)量*/inttz02(intn){ inti,sum=1; for(i=;i>=;i--) { sum=2*(sum+1); } returnsum;}編譯運行的結(jié)果如圖5-12所示：圖5-12猴子吃桃問題任務(wù)實施3.任務(wù)總結(jié)在用遞歸算法解決問題時，必須確定遞推公式和遞歸出口條件。遞推公式或許有多種寫法，但只有能遞推到遞歸出口條件的公式才能作為遞歸表達式。任務(wù)準備任務(wù)實施任務(wù)描述任務(wù)4使用主函數(shù)的參數(shù)任務(wù)描述在C語言中，main()函數(shù)是程序的入口，是程序執(zhí)行的第一個函數(shù)。main()函數(shù)的參數(shù)可以用來接收外部傳入的數(shù)據(jù)，這些數(shù)據(jù)可以用來控制程序的執(zhí)行，或者用來傳遞程序所需要的參數(shù)。本任務(wù)會介紹Windows自帶的命令以及命令