1.3.3 遞歸算法舉例——求最大公約數(shù)

1.帶余除法

令a為整數(shù)，b為正整數(shù)，若存在唯一整數(shù)q,r（0≤r＜b），使得a=bq+r，稱a為被除數(shù)，b為除數(shù)，q為商，r為余數(shù)，r記作a mod b，即r=a mod b。

2.最大公約數(shù)

能整除兩個整數(shù)a、b的最大整數(shù)，稱為這兩個整數(shù)的最大公約數(shù)，記作gcd（a,b）。

3.最大公約數(shù)的求法——輾轉(zhuǎn)相除法

輾轉(zhuǎn)相除法是公元前300年左右由古希臘數(shù)學(xué)家歐幾里得首先提出的，因而又稱為歐幾里得算法。

（1）算法基礎(chǔ)。

定理：令a=bq+r（a、b、q、r都是整數(shù)），則gcd（a,b）=gcd（b,r）。

（2）輾轉(zhuǎn)相除法步驟。

設(shè)a、b是給定的兩個整數(shù)，且0≠b＜a，令r0=a,r1=b，則：

r 0=r1q0+r2（0＜r2＜r1）

r 1=r2q1+r3（0＜r3＜r2）

r 2=r3q2+r4（0＜r4＜r3）

…

rk=rk+1qk

輾轉(zhuǎn)相除法實質(zhì)上是把求兩個較大整數(shù)的最大公約數(shù)轉(zhuǎn)化為求兩個較小整數(shù)的最大公約數(shù)。

遞歸可使用遞歸算法實現(xiàn)，也可使用非遞歸算法（循環(huán)結(jié)構(gòu)）代替。

4.輾轉(zhuǎn)相除法算法的N-S圖與流程圖

算法步驟：

第一步：輸入兩個正整數(shù)a、b（a＞b）。

第二步：計算a除以b所得的余數(shù)r。

第三步：賦值a=b,b=r。

第四步：判斷：若r=0，則a,b的最大公約數(shù)等于a；否則轉(zhuǎn)到第二步。

第五步：輸出最大公約數(shù)a（見圖1.18）。

5.輾轉(zhuǎn)相除法的遞歸函數(shù)C語言偽代碼

課堂練習(xí)1.3

1.在正整數(shù)上遞歸定義：

（1）前n個奇數(shù)之和：1+3+5+…+（2n?1）。

（2）指數(shù)函數(shù)2n。

2.說出求斐波那契數(shù)列第5項的遞歸邏輯過程。

3.設(shè)計一個求斐波那契數(shù)列（a1 =a2 =1,an =an?1+an?2（n＞2））前 20 項和的算法，并畫出N-S圖。

*4.仿造C語言遞歸函數(shù)一般形式，寫出定義10！的遞歸函數(shù)的偽代碼。