第11講 函數(shù)與過(guò)程二

1、2006/9/1集里中學(xué)： 徐 晨 輝函數(shù)與過(guò)程（二）函數(shù)與過(guò)程（二） 1 1、函數(shù)與過(guò)程的關(guān)系、函數(shù)與過(guò)程的關(guān)系 和和區(qū)別區(qū)別2 2、遞歸算法、遞歸算法一.函數(shù)與過(guò)程的關(guān)系和區(qū)別常用的標(biāo)準(zhǔn)函數(shù)常用的標(biāo)準(zhǔn)函數(shù): :sqrt(xsqrt(x) , ) , sqr(xsqr(x) , ) , abs(xabs(x) , ) , exp(xexp(x) )在程序設(shè)計(jì)中，怎樣使用他們？在程序設(shè)計(jì)中，怎樣使用他們？不用定義，直接使用（不用定義，直接使用（pascalpascal編譯程序中集成了編譯程序中集成了上述函數(shù)）。上述函數(shù)）。一.函數(shù)與過(guò)程的關(guān)系和區(qū)別有返回值，因此在程序設(shè)計(jì)中不能作為一個(gè)單獨(dú)有返

2、回值，因此在程序設(shè)計(jì)中不能作為一個(gè)單獨(dú)的語(yǔ)句來(lái)使用（只能成為的語(yǔ)句來(lái)使用（只能成為表達(dá)式的一部分表達(dá)式的一部分）y:=sqrt(x); /rightsqr(x); /errorread(a ,b ,c); /right過(guò)程過(guò)程 vs vs 函數(shù)函數(shù)區(qū)別：有且只有一個(gè)返回值（函數(shù)）；區(qū)別：有且只有一個(gè)返回值（函數(shù)）； 無(wú)返回值（過(guò)程）；無(wú)返回值（過(guò)程）；函數(shù)的定義格式函數(shù)的定義格式Function 函數(shù)名（函數(shù)名（）：）：該函數(shù)該函數(shù)返回值的類(lèi)型返回值的類(lèi)型例如：例如： w:=upcase(ch); y:=sqrt(x);形式參數(shù)表形式參數(shù)表參數(shù)傳遞規(guī)則參數(shù)傳遞規(guī)則跟過(guò)程相同跟過(guò)程相同值形參：傳

3、值。值形參：傳值。變量形參：傳地址。變量形參：傳地址。樣例程序樣例程序結(jié)果：結(jié)果： 9 9 9 7 9 7 9 9 7 9 7 9形式參數(shù)表形式參數(shù)表規(guī)則：在函數(shù)體規(guī)則：在函數(shù)體執(zhí)行部分執(zhí)行部分，通過(guò)給，通過(guò)給函數(shù)名函數(shù)名標(biāo)識(shí)符標(biāo)識(shí)符 賦值賦值，用來(lái)表示函數(shù)的，用來(lái)表示函數(shù)的返回值返回值。注：函數(shù)名標(biāo)識(shí)符注：函數(shù)名標(biāo)識(shí)符只允許被賦值只允許被賦值，因此不允許出，因此不允許出 現(xiàn)在現(xiàn)在“：=”=”右邊。右邊。二二. .子程序之間的調(diào)用關(guān)系子程序之間的調(diào)用關(guān)系調(diào)用規(guī)則：調(diào)用規(guī)則：在在主程序中主程序中，可以，可以隨時(shí)調(diào)用隨時(shí)調(diào)用任何任何子程序子程序，任何子程序中都，任何子程序中都不能調(diào)用主程序。不能調(diào)

4、用主程序。子程序之間可以相互調(diào)用子程序之間可以相互調(diào)用在程序設(shè)計(jì)中，函數(shù)與過(guò)程統(tǒng)稱(chēng)為在程序設(shè)計(jì)中，函數(shù)與過(guò)程統(tǒng)稱(chēng)為子程序。子程序。是專(zhuān)是專(zhuān)門(mén)用來(lái)給人調(diào)用的功能模塊。門(mén)用來(lái)給人調(diào)用的功能模塊。在子程序體內(nèi)也可以聲明函數(shù)（過(guò)程），此函數(shù)（過(guò)程）在子程序體內(nèi)也可以聲明函數(shù)（過(guò)程），此函數(shù)（過(guò)程）稱(chēng)為稱(chēng)為內(nèi)嵌函數(shù)（過(guò)程）內(nèi)嵌函數(shù)（過(guò)程），但在子程序體內(nèi)聲明的函數(shù)（過(guò)，但在子程序體內(nèi)聲明的函數(shù)（過(guò)程），其作用范圍只局限于該子程序體內(nèi)。程），其作用范圍只局限于該子程序體內(nèi)。三、遞歸三、遞歸 一個(gè)過(guò)程一個(gè)過(guò)程(或函數(shù)或函數(shù))直接或間接調(diào)用自己本身直接或間接調(diào)用自己本身,這種這種過(guò)程過(guò)程(或函數(shù)或函數(shù))叫遞歸

5、過(guò)程叫遞歸過(guò)程(或函數(shù)或函數(shù)).procedureb;procedurec;beginbegin.c;b;.end;end; 采用遞歸方法編寫(xiě)的問(wèn)題解決程序具有結(jié)構(gòu)清晰，采用遞歸方法編寫(xiě)的問(wèn)題解決程序具有結(jié)構(gòu)清晰，可讀性強(qiáng)等優(yōu)點(diǎn)，且遞歸算法的設(shè)計(jì)比非遞歸算可讀性強(qiáng)等優(yōu)點(diǎn)，且遞歸算法的設(shè)計(jì)比非遞歸算法的設(shè)計(jì)往往要容易一些，所以當(dāng)問(wèn)題本身是遞法的設(shè)計(jì)往往要容易一些，所以當(dāng)問(wèn)題本身是遞歸定義的，或者問(wèn)題所涉及到的數(shù)據(jù)結(jié)構(gòu)是遞歸歸定義的，或者問(wèn)題所涉及到的數(shù)據(jù)結(jié)構(gòu)是遞歸定義的，或者是問(wèn)題的解決方法是遞歸形式的時(shí)定義的，或者是問(wèn)題的解決方法是遞歸形式的時(shí)候，往往采用遞歸算法來(lái)解決。候，往往采用遞歸算法來(lái)

6、解決。例：計(jì)算例：計(jì)算n! 用遞歸公式如下用遞歸公式如下: 1 當(dāng)當(dāng) n=0 時(shí)時(shí) n*fac(n-1) 當(dāng)當(dāng)n0時(shí)時(shí)programfac2;varn:integer;functionfac(n:integer):real;beginifn=0thenfac:=1elsefac:=n*fac(n-1)end;beginwrite(n=);readln(n);writeln(fac(,n,)=,fac(n):6:0);end.當(dāng)當(dāng)n0時(shí)，用時(shí)，用f(n-1)來(lái)定義來(lái)定義f(n)，用，用f(n-1-1)來(lái)定義來(lái)定義f(n-1)，這是對(duì)遞歸，這是對(duì)遞歸形式的描述。形式的描述。當(dāng)當(dāng)n=0時(shí)，時(shí)，f(n

7、)=1，這是遞歸結(jié)束的條件。這是遞歸結(jié)束的條件。執(zhí)行流程執(zhí)行流程 fac(3) fac(2) fac(1) fac(0) 3*fac(2) 2*fac(1) 1*fac(0) fac(0)=1如何設(shè)計(jì)遞歸算法如何設(shè)計(jì)遞歸算法1.確定遞歸公式確定遞歸公式2.確定邊界確定邊界(終了終了)條件條件練習(xí)：練習(xí)：1.求：求：1+2+3+.+n的值。的值。n從鍵盤(pán)上輸入。從鍵盤(pán)上輸入。2.有一對(duì)雌雄兔有一對(duì)雌雄兔,每?jī)蓚€(gè)月就繁殖雌雄各一對(duì)兔子每?jī)蓚€(gè)月就繁殖雌雄各一對(duì)兔子.問(wèn)問(wèn)n個(gè)月后共有多少對(duì)兔子個(gè)月后共有多少對(duì)兔子?3.已知已知:數(shù)列數(shù)列1,1,2,4,7,13,24,44,.求數(shù)列的第求數(shù)列的第n項(xiàng)項(xiàng)

8、.漢諾塔問(wèn)題漢諾塔問(wèn)題 有有n個(gè)半徑各不相同的圓盤(pán)，個(gè)半徑各不相同的圓盤(pán)，按半徑從大到小，自下而上依按半徑從大到小，自下而上依次套在次套在A柱上，另外還有柱上，另外還有B、C兩根空柱。要求將兩根空柱。要求將A柱上的柱上的n個(gè)圓盤(pán)全部搬到個(gè)圓盤(pán)全部搬到C柱上去，每柱上去，每次只能搬動(dòng)一個(gè)盤(pán)子，且必須次只能搬動(dòng)一個(gè)盤(pán)子，且必須始終保持每根柱子上是小盤(pán)在始終保持每根柱子上是小盤(pán)在上，大盤(pán)在下。上，大盤(pán)在下。 在移動(dòng)盤(pán)子的過(guò)程當(dāng)中發(fā)現(xiàn)要搬動(dòng)在移動(dòng)盤(pán)子的過(guò)程當(dāng)中發(fā)現(xiàn)要搬動(dòng)n個(gè)盤(pán)子，必須先個(gè)盤(pán)子，必須先將將n-1個(gè)盤(pán)子從個(gè)盤(pán)子從A柱搬到柱搬到B柱去，再將柱去，再將A柱上的最后一柱上的最后一個(gè)盤(pán)子搬到個(gè)盤(pán)子

9、搬到C柱，最后從柱，最后從B柱上將柱上將n-1個(gè)盤(pán)子搬到個(gè)盤(pán)子搬到C柱柱去。搬動(dòng)去。搬動(dòng)n個(gè)盤(pán)子和搬動(dòng)個(gè)盤(pán)子和搬動(dòng)n-1個(gè)盤(pán)子時(shí)的方法是一樣個(gè)盤(pán)子時(shí)的方法是一樣的，當(dāng)盤(pán)子搬到只剩一個(gè)時(shí)，遞歸結(jié)束。的，當(dāng)盤(pán)子搬到只剩一個(gè)時(shí)，遞歸結(jié)束。源柱源柱工作柱工作柱目標(biāo)柱目標(biāo)柱A B Cvar a,b,c,number:integer;procedure move(n: integer;a,b,c:char);begin if n=1 then writeln(a,-,c) else begin move(n-1,a,c,b); writeln(a,-,c); move(n-1,b,a,c) end;end

10、;begin write(the number of dish:); readln(number); move(number,A,B,C);end.l要求找出具有下列性質(zhì)的數(shù)的個(gè)數(shù)要求找出具有下列性質(zhì)的數(shù)的個(gè)數(shù)(包含輸入的自然數(shù)包含輸入的自然數(shù)n)：l先輸入一個(gè)自然數(shù)先輸入一個(gè)自然數(shù)n(n=500),然后對(duì)此自然數(shù)按照如下方法進(jìn)行處理然后對(duì)此自然數(shù)按照如下方法進(jìn)行處理:l. 不作任何處理不作任何處理;l. 在它的左邊加上一個(gè)自然數(shù)在它的左邊加上一個(gè)自然數(shù),但該自然數(shù)不能超過(guò)原數(shù)的一半但該自然數(shù)不能超過(guò)原數(shù)的一半;l. 加上數(shù)后加上數(shù)后,繼續(xù)按此規(guī)則進(jìn)行處理繼續(xù)按此規(guī)則進(jìn)行處理,直到不能再加自然

11、數(shù)為止直到不能再加自然數(shù)為止.l樣例樣例: 輸入輸入: 6l滿(mǎn)足條件的數(shù)為滿(mǎn)足條件的數(shù)為 l 6 l 16l 26l 126l 36l 136l輸出輸出: 6 var n,i:integer; s:real; procedure qiu(x:integer); var k:integer; begin if x0 then begin s:=s+1; for k:=1 to x div 2 do qiu(k) end end; begin readln(n); s:=0; qiu(n); writeln(s:2:0) end.求求m與與n的最大公約數(shù)的最大公約數(shù)l分析：從數(shù)學(xué)上可以知道求分析：

12、從數(shù)學(xué)上可以知道求m與與n的最大公約數(shù)等的最大公約數(shù)等價(jià)于求價(jià)于求n與與(m mod n)的最大公約數(shù)。這時(shí)可以把的最大公約數(shù)。這時(shí)可以把n當(dāng)作新的當(dāng)作新的m, (m mod n)當(dāng)作新的當(dāng)作新的n，這樣問(wèn)題又，這樣問(wèn)題又變成了求新的變成了求新的m與與n的最大公約數(shù)的最大公約數(shù)這種方法我這種方法我們稱(chēng)為輾轉(zhuǎn)相除法。們稱(chēng)為輾轉(zhuǎn)相除法。l設(shè)兩個(gè)整數(shù)分別為設(shè)兩個(gè)整數(shù)分別為m和和n，將，將m整除整除n得到一個(gè)余得到一個(gè)余數(shù)數(shù)r，若，若r=0，則除數(shù)，則除數(shù)n就是最大公約數(shù)，否則，將就是最大公約數(shù)，否則，將除數(shù)作為被除數(shù)，余數(shù)作為除數(shù)繼續(xù)相除，直到除數(shù)作為被除數(shù)，余數(shù)作為除數(shù)繼續(xù)相除，直到余數(shù)余數(shù)=0為止。為止。 Var m,n:integer;function gys(a,b:integer):integer;var r:integer;begin r:=a mod b; if r=0 then gys:b else gys:=gys(b,r);end;begin readln(m,n); writeln(gys is:,gys(m,n);end.有一個(gè)人爬樓梯，他上梯子的方法可以一有一個(gè)人爬樓梯，他上梯子的方法可以一步走步走1級(jí)，也可以一步走級(jí)，也可以一步走2級(jí)?，F(xiàn)