高級語言講課第24次課c2

1、第十章 遞歸程序設(shè)計計算n！遞歸程序設(shè)計程序設(shè)計實例計算算術(shù)表達(dá)式的值間接遞歸遞歸程序執(zhí)行過程作業(yè): 10.3練習(xí): 10.2 10.410.1 計算n!遞歸程序設(shè)計例10-1 編一個函數(shù) factorial 計算階乘 !按過去程序設(shè)計思想，該函數(shù)應(yīng)該寫成： int factorial ( int n ) int i,p; p=1; for ( i=1 ; i0按照該定義，! 就是一個簡單的條件語句和表達(dá)式計算，可以編出如下函數(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)行文看，在定義一個函數(shù)時，若在定義它的內(nèi)部，又出現(xiàn)對它本身的調(diào)用，則稱該函數(shù)是遞歸的，或遞歸定義的。從動態(tài)執(zhí)行角度看，當(dāng)調(diào)用一個函數(shù)時，在進(jìn)入相應(yīng)函數(shù)，還沒退出（返回）之前，又再一次的調(diào)用它本身，而再一次進(jìn)入相應(yīng)函數(shù)，則稱之為遞歸，或稱之為對相應(yīng)函數(shù)的遞歸調(diào)用。 稱遞歸定義的函數(shù)為遞歸函數(shù)。上述函數(shù) factorial 就是遞歸函數(shù)。若計算 5! ，使用函數(shù)調(diào)用fac

3、torial(5) ，觀察其計算過程: 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 次勒讓德多項式計算它的遞歸函數(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è)計的思想體現(xiàn)在：用逐步求精原則，先把一個問題分解成若干子問題這些子問題中有問題的與原始問題具有相同的特征

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

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

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

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

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

10、針上 n-1 片金片，從 x 針移到 z 針，移動過程中 y 針可用把 x 針上一片金片移到 y 針上；把 z 針上 n-1 片金片，從 z 針移到 y 針，移動過程中 x 針可用 按該分解算法，并考慮遞歸出口 (顯然，當(dāng)移動金片的片數(shù)為 0 時，便不用移動了)，寫出move函數(shù)。 以64、a、b、c為實在參數(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 程序時不要輸入太大的 n ，我們執(zhí)行該程序。執(zhí)行主程序：1、輸出提示信息；2、要求輸入金片個數(shù) n ，設(shè)輸入“3”；3、調(diào)用move函數(shù)：進(jìn)入move ；n=30， 參數(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ù)替換后，實際是執(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ù)替換后，實際是執(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ù)替換后，實際執(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 實際執(zhí)行調(diào)用move ( 1 , c , a , b )，進(jìn)入move 實際執(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 ；實際執(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 )按程序輸出的移動順序，實際移動。a-ba-cb-ca-bc-ac-ba-b a b c例10.5 三個齒輪嚙合問題 設(shè)有三個齒輪互相銜接，求當(dāng)三個齒輪的某兩對齒互相銜接后到下一次這兩對齒再互相銜接，每個齒輪最少各轉(zhuǎn)多少圈。 解:首先把問題數(shù)學(xué)化，這是求最小公倍數(shù)的問題。每個齒輪需轉(zhuǎn)圈數(shù)是三個齒輪齒數(shù)的最小公倍數(shù)除以自己的齒數(shù)。設(shè) 三個齒輪的齒數(shù)分別為:na、nb、nc ； 嚙合最小圈數(shù)分別為:ma、mb、mc ； 三齒輪齒數(shù)的最小公倍數(shù)為k3 。計算步驟表示為：開始讀入三齒輪齒數(shù)求三齒數(shù)的最小公倍數(shù) k3分別計算嚙合的最小圈數(shù)輸出結(jié)果結(jié)束 讀入三齒輪齒數(shù)和輸

23、出結(jié)果，分別只是一次調(diào)用讀或?qū)懞瘮?shù)，不必求精。 求精計算三齒數(shù)的最小公倍數(shù)k3 ?？梢园言搯栴}分解成 先求兩個齒數(shù)na與nb的最小公倍數(shù) k2 ， 然后再求k2與第三個齒數(shù) nc 的最小公倍數(shù) k3 ， k3 即為na、nb、nc三個齒輪齒數(shù)的最小公倍數(shù)。設(shè)已經(jīng)有求兩個數(shù)的最小公倍數(shù)的函數(shù) int lowestcm( int x, int y )則該求精過程可表示成 。求三齒數(shù)的最小公倍數(shù) k3=lowestcm( lowestcm(na,nb), nc )結(jié)束求精求兩個數(shù)的最小公倍數(shù)的函lowestcm 。 x、y 的最小公倍數(shù)是 x、y 的積除以 x、y 的最大公約數(shù)。設(shè)已經(jīng)有求兩個數(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ù)求精兩個數(shù)的求最大公約數(shù)：已經(jīng)知道“展轉(zhuǎn)相除法”求u、v最大公約數(shù)的計算過程如下 上述“展轉(zhuǎn)相除法”求兩個數(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最后，分別計算嚙合的最小圈數(shù)可以被求精成下圖 。開始ma = k3 / namb = k3 / nbmc = k3 / nc結(jié)束/* PROGRAM mesh */#include “stdio.h” /* 函數(shù)原型部分 *int lowestcm3(int x, int y，int z) ；/ 計算三個數(shù)的最小公倍數(shù) int lowestcm2(int x, int y) ； / 計算兩個數(shù)最小公倍數(shù)int gcd(int x, int y) ; / 計算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 );/* 計算三個數(shù)的最小公倍數(shù) */int lowestcm3(int x, int y，int z) return lowestcm2(lowestcm2(x,y),z);/* 計算兩個數(shù)的最小公倍數(shù) */int lowestcm2(int x, int y) return x*y / gcd(x,y); /* lowestcm */* 計算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.計算實在參數(shù)，又再一次調(diào)用函數(shù)lowestcm2； 遞歸的動態(tài)含義是：在調(diào)用函數(shù)，進(jìn)入一個函數(shù)后還沒退出之前，又再一次調(diào)用該函數(shù)而進(jìn)入該函數(shù),同樣產(chǎn)生遞歸，這種遞歸稱為“由調(diào)用引起的遞歸”。函數(shù) lowestcm2 本身定義看不出遞歸，但是他調(diào)用的函數(shù)gcd存在遞歸。 【例10.6】從前 n 個自然數(shù) 1 , 2 , 3 , . , n 中取 r 個數(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)該用多少個 i 。換一個角度想問題。從前 n 個自然數(shù) 1 , 2 , 3 , . , n中取 r 個數(shù)作組合的問題可以分解成：先分別取這 n 個數(shù)中的一個數(shù) i （只需要在前 n-r+1 個數(shù)中取 i ）；然后從