2018-2019学年人教B版 必修三 1.3 中国古代数学中的算法案例 教案
2018-2019学年人教B版   必修三  1.3  中国古代数学中的算法案例  教案第3页

1. 求两个正整数最大公约数的算法

学生通常会用辗转相除法求两个正整数的最大公约数:

例1:求78和36的最大公约数

(1) 利用辗转相除法

步骤:

计算出7836的余数6,再将前面的除数36作为新的被除数,366=6,余数为0,则此时的除数即为78和36的最大公约数。

理论依据: ,得与有相同的公约数

(2) 更相减损之术

指导阅读课本P----P,总结步骤

步骤:

以两数中较大的数减去较小的数,即78-36=42;以差数42和较小的数36构成新的一对数,对这一对数再用大数减去小数,即42-36=6,再以差数6和较小的数36构成新的一对数,对这一对数再用大数减去小数,即36-6=30,继续这一过程,直到产生一对相等的数,这个数就是最大公约数

即,

理论依据:

由,得与有相同的公约数

算法:

输入两个正数;

如果,则执行,否则转到;

将的值赋予;

若,则把赋予,把赋予,否则把赋予,重新执行;

输出最大公约数

程序:

a=input("a=")

b=input("b=")

while a<>b

if a>=b

  a=a-b;

 else

  b=b-a

 end

end

print(%io(2),a,b)

例1 :用等值算法(更相减损术)求下列两数的最大公约数。

(1)225,135 (2)98,280

例2:用辗转相除法验证上例中两数的最大公约数是否正确。