学科：数学 主编人：霍延杰 审核： 集备时间： 学科组长： 编号：SX2-007
批阅时间
装
订
线
装
订
线
1.3.1 辗转相除法、更相减损术及秦九昭算法
姓名 班级 组别 使用时间
【学习目标】
1.理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析。
2.了解秦九昭算法可以减少计算次数提高计算效率的实质。
学习重难点：辗转相除法和更相减损术的算法思想，秦九昭算法的思想。
【自主学习】
1.辗转相除法
辗转相除法求两个数的最大公约数，其算法步骤可以描述如下：
第一步，给定两个正整数 ， .
第二步，求余数r：计算m除以n，将所得 存放到变量r中.
第三步，更新被除数和余数：m=n，n=r.
第四步，判断余数r是否为 .若余数为0，则输出结果；否则转向 继续循环执行.
如此循环，直到得到结果为止. 这种算法是由欧几里得在公元前300年左右首先提出的，因而又叫欧几里得算法.
2. 更相减损术
第一步，任意给定两个正整数，判断它们是否都是 ，若是，用2约简；若不是，执行第二步.
第二步，以较大的数 较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数相等为止，则这个数（等数）或这个数与约简的数的乘积就是所求的最大公约数.
3.秦九昭算法用于求次多项式当时的值，算法反复执行的一个递推公式为 .
【合作探究】
C级1．（1）用辗转相除法求123和48的最大公约数.
（2）用更相减损术求80和36的最大公约数.
点评：对比两种方法控制好算法的结束，辗转相除法是到达余数为0，更相减损术是到达减数和差相等.
B级2. 分别用辗转相除法和更相减损术求1 734，816的最大公约数．
3.设计利用秦九韶算法计算5次多项式当时的值的程序框图。
【课堂小结】
1.辗转相除法。2.更相减损术。3.秦九昭算法
【当堂检测】
1.两个整数490和910的最大公约数是（ ）
A.2 B.10 C.30 D.70
2.用辗转相除法求得3141,1278的最大公约数为
3.分别用辗转相除法和更相减损术求261，319的最大公约数.
4用秦九韶算法求多项式f(x)=7x7+6x6+5x5+4x4+3x3+2x2+x当x=3时的值.
第1页 第2页
微信/支付宝扫码支付