1.3.3 递归算法举例——求最大公约数

1.带余除法

令a为整数，b为正整数，若存在唯一整数q,r（0≤r＜b），使得a=bq+r，称a为被除数，b为除数，q为商，r为余数，r记作a mod b，即r=a mod b。

2.最大公约数

能整除两个整数a、b的最大整数，称为这两个整数的最大公约数，记作gcd（a,b）。

3.最大公约数的求法——辗转相除法

辗转相除法是公元前300年左右由古希腊数学家欧几里得首先提出的，因而又称为欧几里得算法。

（1）算法基础。

定理：令a=bq+r（a、b、q、r都是整数），则gcd（a,b）=gcd（b,r）。

（2）辗转相除法步骤。

设a、b是给定的两个整数，且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

辗转相除法实质上是把求两个较大整数的最大公约数转化为求两个较小整数的最大公约数。

递归可使用递归算法实现，也可使用非递归算法（循环结构）代替。

4.辗转相除法算法的N-S图与流程图

算法步骤：

第一步：输入两个正整数a、b（a＞b）。

第二步：计算a除以b所得的余数r。

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

第四步：判断：若r=0，则a,b的最大公约数等于a；否则转到第二步。

第五步：输出最大公约数a（见图1.18）。

5.辗转相除法的递归函数C语言伪代码

课堂练习1.3

1.在正整数上递归定义：

（1）前n个奇数之和：1+3+5+…+（2n−1）。

（2）指数函数2n。

2.说出求斐波那契数列第5项的递归逻辑过程。

3.设计一个求斐波那契数列（a1 =a2 =1,an =an−1+an−2（n＞2））前 20 项和的算法，并画出N-S图。

*4.仿造C语言递归函数一般形式，写出定义10！的递归函数的伪代码。