高級(jí)語言講課第24次課c2

1、第十章 遞歸程序設(shè)計(jì)計(jì)算n！遞歸程序設(shè)計(jì)程序設(shè)計(jì)實(shí)例計(jì)算算術(shù)表達(dá)式的值間接遞歸遞歸程序執(zhí)行過程作業(yè): 10.3練習(xí): 10.2 10.410.1 計(jì)算n!遞歸程序設(shè)計(jì)例10-1 編一個(gè)函數(shù) factorial 計(jì)算階乘 !按過去程序設(shè)計(jì)思想，該函數(shù)應(yīng)該寫成： int factorial ( int n ) int i,p; p=1; for ( i=1 ; i0按照該定義，! 就是一個(gè)簡(jiǎn)單的條件語句和表達(dá)式計(jì)算，可以編出如下函數(shù)： int factorial ( int n ) if ( n=0 ) return 1; else return n*factorial(n-1); 問題：在函數(shù)

2、factorial 內(nèi)又調(diào)用函數(shù) factorial 本身，行嗎？回答：行！ 按作用域規(guī)則，在函數(shù) factorial 內(nèi)又調(diào)用函數(shù) factorial 本身是合法的；其次 C 系統(tǒng)保證上述調(diào)用過程執(zhí)行的正確性，這就是遞歸。從靜態(tài)行文看，在定義一個(gè)函數(shù)時(shí)，若在定義它的內(nèi)部，又出現(xiàn)對(duì)它本身的調(diào)用，則稱該函數(shù)是遞歸的，或遞歸定義的。從動(dòng)態(tài)執(zhí)行角度看，當(dāng)調(diào)用一個(gè)函數(shù)時(shí)，在進(jìn)入相應(yīng)函數(shù)，還沒退出（返回）之前，又再一次的調(diào)用它本身，而再一次進(jìn)入相應(yīng)函數(shù)，則稱之為遞歸，或稱之為對(duì)相應(yīng)函數(shù)的遞歸調(diào)用。 稱遞歸定義的函數(shù)為遞歸函數(shù)。上述函數(shù) factorial 就是遞歸函數(shù)。若計(jì)算 5! ，使用函數(shù)調(diào)用fac

3、torial(5) ，觀察其計(jì)算過程: return 5*f(4) return 120f(4)f(3)f(2)f(1)f(0)return 4*f(3)return 3*f(2)return 2*f(1)return 1*f(0)return 1return 24return 1return 1int factorial ( int n ) if ( n=0 ) return 1; else return n*factorial(n-1); void main() printf(“%dn”,factorial (5) );return 2return 6【例10.2】 X 的 n 次冪，可以

4、定義為float power ( float x, int n ) if ( n=0 )return 1 ;else return x * power(x,n-1) ;【例10.3】 n 次勒讓德多項(xiàng)式計(jì)算它的遞歸函數(shù)是: float p ( int n , float x ) if ( n=0 ) return 1 ; else if (n=1) return x ; else return ( (2*n-1)*x*p(n-1,x) - (n-1)*p(n-2,x) )/n ; 遞歸程序設(shè)計(jì)的思想體現(xiàn)在：用逐步求精原則，先把一個(gè)問題分解成若干子問題這些子問題中有問題的與原始問題具有相同的特征

5、屬性，至多不過是某些參數(shù)不同，規(guī)模比原來小了此時(shí)，就可以對(duì)這些子問題實(shí)施與原始問題同樣的分析算法，直到規(guī)模小到問題容易解決或已經(jīng)解決時(shí)為止。也就是說，若將整個(gè)問題的算法設(shè)計(jì)成一個(gè)函數(shù)，則解決這個(gè)子問題的算法就表現(xiàn)為對(duì)相應(yīng)函數(shù)的遞歸調(diào)用.編寫遞歸程序要注意：遞歸程序漂亮、好看、好讀、風(fēng)格優(yōu)美，但執(zhí)行效率低。計(jì)算! 的函數(shù)即可以寫成循環(huán)形式，也可以寫成遞歸形式。但是有些循環(huán)程序?qū)懗蛇f歸很困難。反之，有些遞歸程序?qū)懗裳h(huán)也很困難，甚至是不可能的。終結(jié)條件。程序一定要能終止，不能無限遞歸下去。使用全局量要特別小心。用不好，單元發(fā)生沖突，將導(dǎo)致程序出錯(cuò)。 例10-4漢諾（ Hanoi ）塔游戲該問題又稱

6、世界末日問題。相傳，古印度布拉瑪婆羅門神廟的憎侶們，當(dāng)時(shí)作一種被稱為 Hanoi塔的游戲。該游戲是：在一個(gè)平板上，有三根鉆石針；在其中一根針上有成塔型落放的大小不等的64片金片；要求把這64片金片全部移到另一根鉆石針上。移動(dòng)規(guī)則是：每次只允許移動(dòng)一片金片；移動(dòng)過程中的任何時(shí)刻，都不允許有較大的金片放在較小的金片的上面；移動(dòng)過程中，三根鉆石針都可以利用，但是金片不許放在除鉆石針以外的任何地方。不論白天黑夜都有一個(gè)憎侶在移動(dòng)。據(jù)說當(dāng)64片金片全部從一根鉆石針移到另一根鉆石針上那天，就是世界的末日。到那時(shí)他們的虔誠(chéng)信徒可以升天，而其他人則要下地獄。當(dāng)然這只是傳說，按照規(guī)則把 64 片金片全部從一根針

7、移到另一根針上，總的移動(dòng)次數(shù)是 264-1次，若一秒移動(dòng)一次，不發(fā)生錯(cuò)誤，日夜不停的移動(dòng)，約需 5849 億年。而太陽系的壽命僅有100150億年而已。請(qǐng)編程序，打印金片的移動(dòng)順序。10.2 程序設(shè)計(jì)實(shí)例解：不妨設(shè)三根鉆石針順次編號(hào)為 a 、b 、c ；開始所有 64 片金片全部在 a 針上；現(xiàn)在要把它們移動(dòng)到 b 針上；移動(dòng)過程中 c 針可以利用。如圖所示 . .64片 a b c63片 . .63片 . .64片試想，若能夠把a(bǔ) 針上的64片金片全部移動(dòng)到b針上，必須能夠先把a(bǔ)針頂部的63片金片移到c針上?，F(xiàn)在，可以很容易的把a(bǔ)針上的一片金片移到 b 針上。最后，再按照把a(bǔ)針上的63片金片

8、移到c針上的算法，把c針上的63片金片全部移到b針上。從而，完成了題目要求的工作。重新觀察上述過程： 怎樣進(jìn)行移動(dòng)？開始就遇到把a(bǔ)針最上邊的金片先移到b針上，還是先移到c針上？沒有任何根據(jù)作出決定，按一般方法是不好解決這個(gè)問題的。下邊換一個(gè)角度來考慮該問題：按這個(gè)想法，移動(dòng) 64 片金片的問題可以被分解成：把a(bǔ)針上63片金片，從a針移到c針上，移動(dòng)過程中b針可用；把a(bǔ)針上一片金片移到b針上；把c針上63片金片，從c針移到b針上，移動(dòng)過程中a針可用。到此，問題雖然沒有解決，但是已經(jīng)向解的方向前進(jìn)了一步，移動(dòng)64 片金片的問題變成移動(dòng) 63 片金片的問題了。這一步雖然很小, 甚至是微不足道的，但是

9、卻是十分重要的。 . .64片 a b c63片 . .63片 . .64片設(shè)若有一函數(shù) move( n , x , y , z )能夠完成：“把 x 針上的 n 片金片，移動(dòng)到 y 針上，移動(dòng)過程中可以利用 z 針?！保瑒t上述原始問題可以描述成對(duì) move 的調(diào)用：move( 64 , a , b , c )移動(dòng)過程也可以描述成對(duì) move 的調(diào)用：move( 63 , a , c , b ) move( 63 , c , b , a )考慮move函數(shù): 按分解移動(dòng) 64 片金片問題的思路，問題：“把 x 針上的 n 片金片，移動(dòng)到 y 針上，移動(dòng)過程中 z 針可用”可以被分解成：把 x

10、針上 n-1 片金片，從 x 針移到 z 針，移動(dòng)過程中 y 針可用把 x 針上一片金片移到 y 針上；把 z 針上 n-1 片金片，從 z 針移到 y 針，移動(dòng)過程中 x 針可用 按該分解算法，并考慮遞歸出口 (顯然，當(dāng)移動(dòng)金片的片數(shù)為 0 時(shí)，便不用移動(dòng)了)，寫出move函數(shù)。 以64、a、b、c為實(shí)在參數(shù)調(diào)用該move函數(shù)，便可以解決Hanoi 塔問題。 最后得到完整的 Hanoi 塔解法程序如下void moveone ( char u , char v ) printf ( “%c - %cn” , u , v );void move ( int n, char x, char y,

11、 char z ) if ( n0 ) move( n-1 , x,z,y );moveone( x,y );move( n-1 , z,y,x ) int main(void) int n ;printf( “pleace input n:”); scanf( “%d” , &n ); move ( n , a , b , c ) 執(zhí)行 hanoi 程序時(shí)不要輸入太大的 n ，我們執(zhí)行該程序。執(zhí)行主程序：1、輸出提示信息；2、要求輸入金片個(gè)數(shù) n ，設(shè)輸入“3”；3、調(diào)用move函數(shù)：進(jìn)入move ；n=30， 參數(shù)替換后，實(shí)際printf( “pleace input n:”);scanf

12、( “%d” , &n );move ( n , a , b , c )move( n-1 , x , z , y );moveone( x , y );move( n-1 , z , y , x )move( 2 , a , c , b );moveone( a , b );move( 2 , c , b , a )執(zhí)行調(diào)用move ( 2 , a , c , b )：調(diào)用move函數(shù)：進(jìn)入move ；n=20，執(zhí)行參數(shù)替換后，實(shí)際是執(zhí)行：printf( “pleace input n:”);scanf( “%d” , &n );move ( n , a , b , c )move( n-1

13、 , x , z , y );moveone( x , y );move( n-1 , z , y , x );move( 2 , a , c , b );moveone( a , b );move( 2 , c , b , a );move( 1 , a , b , c );moveone( a , c );move( 1 , b , c , a );執(zhí)行調(diào)用move ( 1 , a , b , c )：調(diào)用move函數(shù)：進(jìn)入move ；n=10，執(zhí)行參數(shù)替換后，實(shí)際是執(zhí)行：printf( “pleace input n:”);scanf( “%d” , &n );move ( n , a

14、, b , c )move( n-1 , x , z , y );moveone( x , y );move( n-1 , z , y , x )move( 2 , a , c , b );moveone( a , b );move( 2 , c , b , a );move( 1 , a , b , c );moveone( a , c );move( 1 , b , c , a );move( 0 , a , c , b );moveone( a , b );move( 0 , c , b , a );執(zhí)行move( 0 , a , c , b )：調(diào)用move函數(shù)，進(jìn)入move ；n=0

15、，返回。調(diào)用moveone ，打印“a-b”調(diào)用move函數(shù)，進(jìn)入move ；n=0，返回。move函數(shù)執(zhí)行結(jié)束，返回。printf( “pleace input n:”);scanf( “%d” , &n );move ( n , a , b , c )move( 2 , a , c , b );moveone( a , b );move( 2 , c , b , a )move( 1 , a , b , c );moveone( a , c );move( 1 , b , c , a )move( 0 , a , c , b );moveone( a , b );move( 0 , c ,

16、 b , a );a-b 調(diào)用moveone ，打印“a-c”調(diào)用move函數(shù)，進(jìn)入move ；n=10，執(zhí)行參數(shù)替換后，實(shí)際執(zhí)行printf( “pleace input n:”);scanf( “%d” , &n );move ( n , a , b , c )move( 2 , a , c , b );moveone( a , b );move( 2 , c , b , a );move( 1 , a , b , c );moveone( a , c );move( 1 , b , c , a );a-ba-c move( n-1 , x , z , y );moveone( x , y

17、 );move( n-1 , z , y , x );move( 0 , b , a , c );moveone( b , c );move( 0 , a , c , b );調(diào)用move函數(shù)，進(jìn)入move ；n=0，返回。調(diào)用moveone ，打印“b-c”調(diào)用move函數(shù)，進(jìn)入move ；n=0，返回。move函數(shù)執(zhí)行結(jié)束，返回。move函數(shù)執(zhí)行結(jié)束，返回。調(diào)用moveone ，打印“a-b”執(zhí)行move( 2 , c , b , a )printf( “pleace input n:”);scanf( “%d” , &n );move ( n , a , b , c )move( 2 ,

18、 a , c , b );moveone( a , b );move( 2 , c , b , a );move( 1 , a , b , c );moveone( a , c );move( 1 , b , c , a );a-ba-cb-ca-bmove( 0 , b , a , c );moveone( b , c );move( 0 , a , c , b );調(diào)用move ( 2 , c , b , a )，進(jìn)入move 實(shí)際執(zhí)行調(diào)用move ( 1 , c , a , b )，進(jìn)入move 實(shí)際執(zhí)行調(diào)用move函數(shù)，進(jìn)入move ；n=0，返回。調(diào)用moveone ，打印“c-a”

19、調(diào)用move函數(shù)，進(jìn)入move ；n=0，返回。 move函數(shù)執(zhí)行結(jié)束，返回。printf( “pleace input n:”);scanf( “%d” , &n );move ( n , a , b , c )move( 2 , a , c , b );moveone( a , b );move( 2 , c , b , a )a-ba-ca-ca-bc-amove( n-1 , x , z , y );moveone( x , y );move( n-1 , z , y , x )move( 1 , c , a , b );moveone( c , b );move( 1 , a , b

20、 , c )move( n-1 , x , z , y );moveone( x , y );move( n-1 , z , y , x )move( 0 , c , b , a );moveone( c , a );move( 0 , b , a , c )調(diào)用moveone ，打印“c-b”調(diào)用move ( 1, a , b , c )，進(jìn)入move ；實(shí)際執(zhí)行調(diào)用move函數(shù)，進(jìn)入move ；n=0，返回。調(diào)用moveone ，打印“a-b”調(diào)用move函數(shù)，進(jìn)入move ；n=0，返回。move函數(shù)執(zhí)行結(jié)束，返回。move函數(shù)執(zhí)行結(jié)束，返回。程序執(zhí)行結(jié)束。printf( “pleace

21、 input n:”);scanf( “%d” , &n );move ( n , a , b , c )move( 2 , a , c , b );moveone( a , b );move( 2 , c , b , a )a-ba-cb-ca-bc-ac-ba-bmove( 1 , c , a , b );moveone( c , b );move( 1 , a , b , c )move( n-1 , x , z , y );moveone( x , y );move( n-1 , z , y , x )move( 0 , a , c , b );moveone( a , b );mov

22、e( 0 , c , b , a )按程序輸出的移動(dòng)順序，實(shí)際移動(dòng)。a-ba-cb-ca-bc-ac-ba-b a b c例10.5 三個(gè)齒輪嚙合問題 設(shè)有三個(gè)齒輪互相銜接，求當(dāng)三個(gè)齒輪的某兩對(duì)齒互相銜接后到下一次這兩對(duì)齒再互相銜接，每個(gè)齒輪最少各轉(zhuǎn)多少圈。 解:首先把問題數(shù)學(xué)化，這是求最小公倍數(shù)的問題。每個(gè)齒輪需轉(zhuǎn)圈數(shù)是三個(gè)齒輪齒數(shù)的最小公倍數(shù)除以自己的齒數(shù)。設(shè) 三個(gè)齒輪的齒數(shù)分別為:na、nb、nc ； 嚙合最小圈數(shù)分別為:ma、mb、mc ； 三齒輪齒數(shù)的最小公倍數(shù)為k3 。計(jì)算步驟表示為：開始讀入三齒輪齒數(shù)求三齒數(shù)的最小公倍數(shù) k3分別計(jì)算嚙合的最小圈數(shù)輸出結(jié)果結(jié)束 讀入三齒輪齒數(shù)和輸

23、出結(jié)果，分別只是一次調(diào)用讀或?qū)懞瘮?shù)，不必求精。 求精計(jì)算三齒數(shù)的最小公倍數(shù)k3 ?？梢园言搯栴}分解成 先求兩個(gè)齒數(shù)na與nb的最小公倍數(shù) k2 ， 然后再求k2與第三個(gè)齒數(shù) nc 的最小公倍數(shù) k3 ， k3 即為na、nb、nc三個(gè)齒輪齒數(shù)的最小公倍數(shù)。設(shè)已經(jīng)有求兩個(gè)數(shù)的最小公倍數(shù)的函數(shù) int lowestcm( int x, int y )則該求精過程可表示成 。求三齒數(shù)的最小公倍數(shù) k3=lowestcm( lowestcm(na,nb), nc )結(jié)束求精求兩個(gè)數(shù)的最小公倍數(shù)的函lowestcm 。 x、y 的最小公倍數(shù)是 x、y 的積除以 x、y 的最大公約數(shù)。設(shè)已經(jīng)有求兩個(gè)數(shù)的最

24、大公約數(shù)的函數(shù) int gcd(int x, int y)則該求精過程可表示成： int lowestcm(int x , int y)return x*y / gcd(x,y)結(jié)束def歐幾里德輾轉(zhuǎn)相除法u % v R1v % R1 R2R1% R2 R3R2 % R3 R4 Rn-2 % Rn-1 Rn=0 Rn-1 為正整數(shù)u 、v的最大公因數(shù) 繼續(xù)求精兩個(gè)數(shù)的求最大公約數(shù)：已經(jīng)知道“展轉(zhuǎn)相除法”求u、v最大公約數(shù)的計(jì)算過程如下 上述“展轉(zhuǎn)相除法”求兩個(gè)數(shù)的最大公約數(shù)的函數(shù)int gcd(int x, int y)可以定義為 被求精成下圖int gcd( int x, int y)結(jié)束y

25、0return gcd(y , x % y)return x最后，分別計(jì)算嚙合的最小圈數(shù)可以被求精成下圖 。開始ma = k3 / namb = k3 / nbmc = k3 / nc結(jié)束/* PROGRAM mesh */#include “stdio.h” /* 函數(shù)原型部分 *int lowestcm3(int x, int y，int z) ；/ 計(jì)算三個(gè)數(shù)的最小公倍數(shù) int lowestcm2(int x, int y) ； / 計(jì)算兩個(gè)數(shù)最小公倍數(shù)int gcd(int x, int y) ; / 計(jì)算x,y的最大公約數(shù)/* 主程序開始 */void main( ) int na

26、,nb,nc,k3; printf(please input n1 n2 n3:); scanf(“%d%d%d”,&na,&nb,&nc); k3 = lowestcm3(na,nb,nc); printf (“FOR mesh the first mnst rotate about %4d rings.n” , k3 / na ); printf (“FOR mesh the second mnst rotate about %4d rings.n” , k3 / nb ); printf (“FOR mesh the third mnst rotate about %4d rings.n

27、” , k3 / nc );/* 計(jì)算三個(gè)數(shù)的最小公倍數(shù) */int lowestcm3(int x, int y，int z) return lowestcm2(lowestcm2(x,y),z);/* 計(jì)算兩個(gè)數(shù)的最小公倍數(shù) */int lowestcm2(int x, int y) return x*y / gcd(x,y); /* lowestcm */* 計(jì)算x,y的最大公約數(shù) */int gcd(int x, int y) if (y=0) return x; else return gcd( y , x % y ); /* gcd */在本例中，函數(shù)gcd自己調(diào)用自己，產(chǎn)生直接遞

28、歸函數(shù)lowestcm3的語句return lowestcm2( lowestcm2 (x,y) , z );調(diào)用函數(shù)lowestcm2的執(zhí)行過程是：1.調(diào)用開始，在進(jìn)入函數(shù)lowestcm2；2.計(jì)算實(shí)在參數(shù)，又再一次調(diào)用函數(shù)lowestcm2； 遞歸的動(dòng)態(tài)含義是：在調(diào)用函數(shù)，進(jìn)入一個(gè)函數(shù)后還沒退出之前，又再一次調(diào)用該函數(shù)而進(jìn)入該函數(shù),同樣產(chǎn)生遞歸，這種遞歸稱為“由調(diào)用引起的遞歸”。函數(shù) lowestcm2 本身定義看不出遞歸，但是他調(diào)用的函數(shù)gcd存在遞歸。 【例10.6】從前 n 個(gè)自然數(shù) 1 , 2 , 3 , . , n 中取 r 個(gè)數(shù)作組合，打印全部所有組合。 例如，n=5 、r=

29、3 ，有如下的10種組合。 1 2 31 2 41 2 51 3 41 3 51 4 52 3 42 3 52 4 53 4 5解本題的一般想法是使用 r 重循環(huán) for ( i1 = 1 ; i1 =n-r+1 ; i1 + ) for ( i2 = i1+1 ; i2 = n-r+2 ; i2 + ) . . for ( ir = ir-1+1 ; ir = n ; ir + ) 印( i1 , . , ir )但是，由于 r 是可變的，所以循環(huán)嵌套層數(shù)亦是可變的，因此不知道應(yīng)該用多少個(gè) i 。換一個(gè)角度想問題。從前 n 個(gè)自然數(shù) 1 , 2 , 3 , . , n中取 r 個(gè)數(shù)作組合的問題可以分解成：先分別取這 n 個(gè)數(shù)中的一個(gè)數(shù) i （只需要在前 n-r+1 個(gè)數(shù)中取 i ）；然后從