C語(yǔ)言程序設(shè)計(jì) 教案 7-3函數(shù)的嵌套與遞歸

《C語(yǔ)言程序設(shè)計(jì)》教案課程名稱C語(yǔ)言程序設(shè)計(jì)任課教師總課時(shí)64教學(xué)課題求小組若干門(mén)課程的總分及平均分授課班級(jí)授課日期課時(shí)2教學(xué)目標(biāo)知識(shí)目標(biāo)：1.掌握函數(shù)的嵌套調(diào)用的方法2.掌握函數(shù)的遞歸調(diào)用的方法能力目標(biāo)：能夠使用函數(shù)實(shí)現(xiàn)多個(gè)學(xué)生多門(mén)課成績(jī)的排序素質(zhì)目標(biāo)：團(tuán)隊(duì)合作能力、團(tuán)隊(duì)互助，自我學(xué)習(xí)的習(xí)慣、愛(ài)好和能力重點(diǎn)難點(diǎn)嵌套調(diào)用和遞歸調(diào)用教學(xué)方法演示、講解、啟發(fā)教學(xué)資源教材《C語(yǔ)言程序設(shè)計(jì)》設(shè)備準(zhǔn)備VC++6.0，極域電子教室軟件，分發(fā)工作任務(wù)單教學(xué)環(huán)節(jié)（教學(xué)過(guò)程）教學(xué)內(nèi)容教師活動(dòng)學(xué)生活動(dòng)教學(xué)目標(biāo)課時(shí)1發(fā)布任務(wù)進(jìn)行任務(wù)的問(wèn)題描述和分析傾聽(tīng)、思考讓學(xué)生理解任務(wù)要求和思路10分鐘2理論講解講授函數(shù)調(diào)用傾聽(tīng)、思考預(yù)備需要的理論知識(shí)15分鐘3舉例通過(guò)一個(gè)案例進(jìn)一步講解函數(shù)的調(diào)用傾聽(tīng)、思考通過(guò)實(shí)際應(yīng)用幫助學(xué)生理解理論知識(shí)20分鐘4應(yīng)用布置兩個(gè)相關(guān)題目思考、解答通過(guò)做相關(guān)練習(xí)題幫助學(xué)生更好的理解相關(guān)知識(shí)45分鐘教學(xué)內(nèi)容（詳細(xì)）：一．函數(shù)的嵌套調(diào)用C語(yǔ)言定義的函數(shù)都是互相獨(dú)立的，函數(shù)間不能嵌套定義，即在一個(gè)函數(shù)體內(nèi)不能再定義另一個(gè)函數(shù)，但可以嵌套調(diào)用，也就是說(shuō)在調(diào)用一個(gè)函數(shù)的過(guò)程中，該函數(shù)又調(diào)用另一個(gè)函數(shù)。【例7-7】輸入兩個(gè)數(shù)，編寫(xiě)函數(shù)，分別求該兩數(shù)的最大公約數(shù)和最小公倍數(shù)，在主函數(shù)中輸入兩個(gè)數(shù)，調(diào)用函數(shù)，輸出公倍數(shù)和公約數(shù)。問(wèn)題分析問(wèn)題分析算法設(shè)計(jì)首先需要兩個(gè)自定義函數(shù)，分別用來(lái)求兩數(shù)的最大公約數(shù)和最小公倍數(shù)。在主函數(shù)中輸入兩整數(shù)，作為實(shí)參調(diào)用函數(shù)。算法設(shè)計(jì)(1)定義2個(gè)整型變量m和n。(2)以整型變量作實(shí)參調(diào)用函數(shù)。(3)輸出公約數(shù)和公倍數(shù)。求公約數(shù)的算法：定義一個(gè)循環(huán)變量，循環(huán)范圍從2個(gè)整型變量中較小值~1。循環(huán)判斷該兩個(gè)整型變量能否整除循環(huán)變量，如果能整除，則返回循環(huán)變量的值，否則繼續(xù)循環(huán)。求公倍數(shù)的算法：定義1個(gè)變量存儲(chǔ)公倍數(shù)。公倍數(shù)等于兩個(gè)數(shù)的乘積除以公約數(shù)。返回公倍數(shù)。傳統(tǒng)流程圖傳統(tǒng)流程圖圖7-15最大公約數(shù)、最小公倍數(shù)和主函數(shù)流程圖程序代碼程序代碼#include<stdio.h>intfnMax(intn,intm){inti;for(i=n;i>=1;i--)if(m%i==0&&n%i==0)returni;}longfnMin(intn,intm){longi;i=m*n/fnMax(n,m);returni;}voidmain(){intiNum1,iNum2;intiMax;longiMin;printf("\nInputtwonumber:");scanf("%d%d",&iNum1,&iNum2);iMax=fnMax(iNum1,iNum2);iMin=fnMin(iNum1,iNum2);printf("thecommondivisoris%d,thecommonmultipleis%ld",iMax,iMin);}程序執(zhí)行的結(jié)果為：說(shuō)明說(shuō)明（1）程序中main()函數(shù)調(diào)用fnMax()、fnMin()函數(shù)完成求最大公約數(shù)和最小公倍數(shù)的任務(wù)，fnMin()函數(shù)調(diào)用fnMax()函數(shù)計(jì)算最小公倍數(shù)。在執(zhí)行fnMin()函數(shù)時(shí)又調(diào)用fnMax()函數(shù)，即為函數(shù)的嵌套調(diào)用。main()函數(shù)fnMax()函數(shù)fnMin()函數(shù)（2）無(wú)論函數(shù)在何處調(diào)用，調(diào)用結(jié)束后都會(huì)返回到調(diào)用該函數(shù)的地方。本例main()函數(shù)、fnMin()函數(shù)和fnMax()函數(shù)調(diào)用關(guān)系如圖7-16所示。main()函數(shù)fnMax()函數(shù)fnMin()函數(shù)voidfnMax(intn,intm){返回函數(shù)的值voidfnMax(intn,intm){返回函數(shù)的值}voidfnMin(intn,intm){i=m*n/fnMax(n,m);返回函數(shù)的值}voidmain(){fnMin(iNum1,iNum2)}③②③②④①④①⑤⑧⑤⑧⑦⑨⑦⑨⑥⑥二．函數(shù)的遞歸調(diào)用在調(diào)用一個(gè)函數(shù)的過(guò)程中又直接地或間接地調(diào)用該函數(shù)本身，稱為函數(shù)的遞歸調(diào)用。顯然，遞歸調(diào)用是嵌套調(diào)用的特例。C語(yǔ)言提供兩種形式的遞歸調(diào)用：直接遞歸調(diào)用：指函數(shù)直接調(diào)用函數(shù)本身的形式，其執(zhí)行過(guò)程如圖7-17所示。間接遞歸調(diào)用：指函數(shù)調(diào)用其他函數(shù)，其他函數(shù)又調(diào)用原函數(shù)的形式，其執(zhí)行過(guò)程如圖7-17所示。圖7-17執(zhí)行過(guò)程1.函數(shù)遞歸調(diào)用的條件可采用遞歸算法解決的問(wèn)題有這樣的特點(diǎn)：原始的問(wèn)題可轉(zhuǎn)化為解決方法相同的新問(wèn)題，而新問(wèn)題的規(guī)模要比原始問(wèn)題小，新問(wèn)題又可轉(zhuǎn)化為規(guī)模更小的問(wèn)題，直至最終歸結(jié)到最基本的情況——遞歸的終結(jié)條件。利用函數(shù)遞歸調(diào)用解決問(wèn)題，必須具備如下兩個(gè)條件：(1)原問(wèn)題求解，能轉(zhuǎn)化為一個(gè)與原問(wèn)題相似的較小的問(wèn)題求解。(2)必須有一個(gè)明確的遞歸結(jié)束條件，稱為遞歸出口。【例7-8】用遞歸調(diào)用的方法，編寫(xiě)計(jì)算n！的程序。問(wèn)題分析問(wèn)題分析根據(jù)階乘的定義有如下遞推關(guān)系：n！=1*2*3*…*(n-2)*(n-1)*n=[1*2*3*…*(n-2)*(n-1)]*n=(n-1)！*n由上面的關(guān)系可知計(jì)算n的階乘問(wèn)題，可以歸結(jié)為n-1的階乘問(wèn)題。同理，計(jì)算n-1的階乘問(wèn)題可以歸結(jié)為n-2的階乘問(wèn)題……依此類(lèi)推，最終將歸結(jié)為計(jì)算1的階乘。所以計(jì)算n！n！=n！=1n=1n*(n-1)n>1fact(n)1當(dāng)n=1fact(n)1當(dāng)n=1n*fact(n-1)當(dāng)n>1程序代碼程序代碼#include<stdio.h>longfact(intn); /*函數(shù)fact()聲明*/longfact(intn)/*遞歸函數(shù)*/{if(n<=1)return1;/*終止條件*/return(fact(n-1)*n);/*遞歸調(diào)用*/}voidmain(){ intnum; longm;printf("請(qǐng)輸入一個(gè)正整數(shù)(小于12):");scanf("%d",&num); m=fact(num);printf("%d!=%ld\n",num,m);}程序執(zhí)行的結(jié)果為：說(shuō)明說(shuō)明（1）這是一個(gè)遞歸調(diào)用的函數(shù)。四次調(diào)用和返回的情況如圖7-所示。第一次調(diào)用函數(shù):fact(4)24最終得到結(jié)果24第一次調(diào)用函數(shù):fact(4)24最終得到結(jié)果24第二次調(diào)用函數(shù):fact(3)*46*4計(jì)算fact(4)=24第三次調(diào)用函數(shù):fact(2)*32*3計(jì)算fact(3)=6四次調(diào)用函數(shù):fact(1)*21*2計(jì)算fact(2)=2fact(1)=1圖7-16遞歸函數(shù)fact(n)的執(zhí)行過(guò)程（2）該程序運(yùn)行時(shí)，當(dāng)n取值較大時(shí)，比如n=10時(shí)，n！的值超出了int和long的取值范圍，因此，此題中的變量建議定義成float類(lèi)型。2.函數(shù)遞歸調(diào)用的執(zhí)行過(guò)程在函數(shù)執(zhí)行過(guò)程中由遞推和回歸兩個(gè)過(guò)程組成。(1)“遞推”階段:將原問(wèn)題不斷地分解為新的子問(wèn)題，逐步從未知的方向向已知方向推測(cè)，最終達(dá)到已知的結(jié)束條件，即遞歸結(jié)束條件，這時(shí)遞推階段結(jié)束，如圖7-14所示左邊部分。(2)“回歸”階段:從已知的條件出發(fā)，按照“遞推”的逆過(guò)程，逐一求值返回，直到返回到遞推的開(kāi)始處，結(jié)束回歸階段，完成遞歸調(diào)用。如圖7-14所示右邊部分。三．多個(gè)學(xué)生多門(mén)課成績(jī)的排序參考代碼如下：#include"stdio.h"/*輸出線條函數(shù)*/ppp()#include"stdio.h"{printf("-------------------------------------\n");}/*某個(gè)小組若干門(mén)課程的平均分與總分函數(shù)*/voidavgevery(intn,intkm){intx,i,j;floats,avg;for(j=1;j<=km;j++){s=0;printf("請(qǐng)輸入本小組第%d門(mén)考試成績(jī)\n",j);ppp();for(i=1;i<=n;i++){scanf("%d",&x);s+=x;}avg=s/n;printf("第%d課程的總分=%.0f\t平均分=%.1f\n",j,s,avg);ppp();}}/*主函數(shù)*/main(){intk,n,km;floatsum,average;charch;ppp();printf("\t班級(jí)成績(jī)統(tǒng)計(jì)\n");ppp();printf("1、統(tǒng)計(jì)小組一門(mén)課程的總分及平均分\n",n);printf("2、統(tǒng)計(jì)小組若干門(mén)課程的總分及平均分\n");printf("3、輸出小組排序后三門(mén)課程的成績(jī)單\n");printf("請(qǐng)輸入1~3之間的一個(gè)數(shù):");scanf