1.3 中国古代数学中的算法案例

张喜林制

1.3 中国古代数学中的算法案例

教材知识检索

考点知识清单

1．等值算法在我国古代也称为 ，它是用来求 的方法． 2．割圆术是我国魏晋时期的数学家____在注《九章算术》中采用一____的算法计算圆周率π 的一种方法． 3．秦九韶算法是我国南宋数学家____提出的一种用于 的方法．

要点核心解读

1．求两个正整数最大公约数的算法 (1)辗转相除法，

①辗转相除法的理论基础．

已知m，n，r为正整数，若m nq r(0 r n)（即r mmodn),则(m,n) (n,r).其中(m，n)表示m和n的最大公约数．

事实上，由m nq r知n和r的公约数都是m和n的公约数；由r m nq知m和n的公约数都是n,和r的公约数，故m和n的公约数与n和r的公约数都相同，其最大公约数也相同.

②辗转相除法的步骤．

用辗转相除法求两个正整数的最大公约数，其算法可以用自然语言描述如下： 第一步：给定两个正整数m，n；

第二步：计算m除以n,所得的余数r；

第三步：m n,n r,

第四步：若r 0,则m，n的最大公约数等于n；否则，返回第二步.

从其算法思想我们可以看出，辗转相除法的基本步骤是用较大的数（用a表示）除以较小的数（用b来表示），得到除式：a nb r(0 r b).

由于这是一个反复执行的步骤，且执行的次数由余数r是否等于0决定，所以我们可以把它看做一个循环体，用循环结构就可以来实现其算法．

[例] 求两个正数a，b（a>b）的最大公约数． [解析] 算法：Sl输入两个正整数a，b（a>b）；

S2 如果r mod(a,b) 0,执行S3 ,否则转到S4；

S3 把a÷b的余数赋予r，把b赋予a，把r赋予b，重新执行S2； S4 输出最大公约数b．程序框图如图1-3 -1所示，

根据框图程序如下：

第1页下一页