(必修三)1.3中国古代数学中的算法案例(一)(人教B版)

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

1. 求两个正整数最大公约数的算法 辗转相除法求两个数的最大公约数，其基本步骤 是带余除法m=nq+r(0≤r<n), 反复执行，直到余数r=0为止.

求任意两个数的最大公约数的算法是

第一步：输入两个 正整数a,b(a>b); 第二步：求出a÷b 的余数r; 第三步：令a=b, b=r,若r≠0,重复第二 步； 第四步：输出最大 公约数a.

举例说明. m=90,n=36, m=2n+18,r=18. 令m=36, n=18. 又有36=18×2, 即m=2n, 此时r=0. 令m=18,n=0. 故最大公约数为18.

开始

算理： 记为a;a=b×t+c; 若c≠0,记a=b, b=c,返 回第2步进行循环； 若c=0,输出b.

输入a,b

先找到a,b中较大的， = a Mod b cc=a mod b b=c a=b c≠0 N 输出b 结束 Y

a=input(“a=”); b=input(“b=”); c=mod(a,b); while c<>0 a=b; b=c; c=mod(a,b); end b

更相减损术 例如，求78和36的最大公约数： 以两数中较大的数减去较小的数，即78 -36=42;以差数42和较小的数36构成新 的一对数； 对这一对数再用大数减去小数，即42 -36=6,再以差数6和较小的数36构成新 的一对数；

对这一对数再用大数减去小数，即36- 6=30,再构成新的一对数；

继续这一过程,直到产生一对相等的数， 这个数就是最大公约数. 操作如下： (78,36) → (42,36) → (6,36) → (6,30) → (6,24) → (6,18) → (6,12) → (6,6). 理论依据： 由a-b=r → a=b+r,得(a, b)与(b, r)有相 同的公约数.

算法如下：

S1 输入两个正数a, b (a>b);S2 如果a≠b,则执行S3,否则转到S5; S3 将a-b的值赋予r; S4 若b>r,则把b赋予a,把r赋予b,否则 把r赋予a,重新执行S2; S5 输出最大公约数

开始 输入a,b

a=a-b Y a≠b N 输出b Y a> b

b=b-a N

结束

程序： a=input(“a=”); b=input(“b=”); while a<>b if a>=b a=a-b; else b=b-a; end end print(%io(2), b, “两数的最大公约数

例1 :用等值算法(更相减损术)求下列 两数的最大公约数。 (1)225,135; 答案: (1) 45; (2)98,280. (2) 14.

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

数学运用例1、两个正整数的最小公倍数，实际上就是这两数 乘积除以它们的最大公约数，试写出求正整数a,b最小 公倍数的程序。 a=input(“a=”);

b=input(“b=”); c=mod (a, b); d=a*b; While c<>0 a=b; b=c; c=mod (a,b); End print(%io(2), d/b)

数学运用例2、用更相减损术求98与63的最大公约数。

解：由于63不是偶数，把98和63以大数减小数， 并辗转相减98-63=35 63-35=28 35-28=7 28-7=21 21-7=14 14-7=7 所以，98和63的最大公约数等于7

回顾反思1、辗转相除法是当大数被小数除尽时，结束 除法运算，较小的数就是最大公约数. 2、更相减损术是当大数减去小

数的差等于小 数时减法停止.较小的数就是最大公约数. 3、求三个以上(含三个数)的数的最大公约数 时，可依次通过求两个数的最大公约数与第 三数的最大公约数来求得. 4、辗转相除法中蕴含的数学原理及算法语 言的表示； 5、如何实现当型循环。