高中数学《算法案例——辗转相除法与更相减损术》课件 北师大版必修3

跟踪训练1 用辗转相除法求204与85的最大公约数时，需要做除法的次数是__3__. 解析 用辗转相除法可得 204÷85＝2……34， 85÷34＝2……17， 34÷17＝2， 此时可以判断204与85的最大公约数是17，做了3次除法得出结果.
题型二 更相减损术
例2 试用更相减损术求612,396的最大公约数.
知识点二 更相减损术 更相减损术的运算步骤 第一步，任意给定两个正整数，判断它们是否都是 偶数 .若是，用 2 约简；若 不是，执行 第二步 . 第二步，以 较大 的数减去 较小 的数，接着把所得的差与 较小 的数比较，并 以大数减小数，继续这个操作，直到所得的数 相等 为止，则这个数(等数)或 这个数与约简的数的乘积就是所求的最大公约数.
12345
5.用辗转相除法求85与51的最大公约数. 解 85＝51×1＋34， 51＝34×1＋17， 34＝17×2＋0， 所以8与51的最大公约数为17.
12345
√C.85和357的最大公约数是34
D.105和315的最大公约数是105 解析 85和357的最大公约数是17.
12345
3.用更相减损术求36与134的最大公约数，第一步应为_先__除__以__2_，__得__到__1_8_与__6_7__. 解析 ∵36与134都是偶数， ∴第一步应为先除以2，得到18与67. 4.已知a＝333，b＝24，则使得a＝bq＋r(q，r均为自然数，且0≤r＜b)成立的q 和r的值分别为__1_3_,2_1___. 解析 用333除以24，商即为q，余数就是r.333÷24＝13……21.
第一章 §1.3 算法案例
第1课时 辗转相除法与更相减损术
学习目标
XUEXIMUBIAO

进而由贝祖等式就可 以求解二元一次不定 方程的通解。
01.07.2019
93 168 1
75 93 18 75 4 18 72 03
3、利用辗转相除法求最大公约数的步骤如下： 第一步：用较大的数m除以较小的数n得到
一个商q0和一个余数r0；(m=n×q0+r0) 第二步：若r0＝0，则n为m，n的最大公约
数. 2. 更相减损术，就是对于给定的两个正
整数，用较大的数减去较小的数，然后将差 和较小的数构成新的一对数，继续上面的减 法，直到差和较小的数相等，此时相等的两 数0即1.07.20为1损术的区别
（1）都是求最大公约数的方法，计算上辗转相除 法以除法为主，更相减损术以减法为主，计算次数 上辗转相除法计算次数相对较少，特别当两个数字 大小区别较大时计算次数的区别较明显。
教学难点 ：转相除法与更相减损术的方法转 换成程序框图与程序语言。
01.07.2019
问题提出
1.研究一个实际问题的算法，主要从 算法步骤、程序框图和编写程序三方面 展开.在程序框图中算法的基本逻辑结构 有哪几种？在程序设计中基本的算法语 句有哪几种？
2.“求两个正整数的最大公约数” 是数学中的一个基础性问题，它有各种 解决办法，我们以此为案例，对该问题 的算法作一些探究.
m=n
否
输出m 结束
INPUT m，n WHILE m<>n
k=m-n IF mn=>nk THEN
n=k ELSEm=k END IF WEND PRINT m
01.07.2019
n=k
END
例2 分别用更相减损术和辗转相除法求98
与63的最大公约数。
解：由于63不是偶数，把98和63以大数减小数，

若m是6105与2146的公约数，则8251必能被m整除。
第二步：对6105和2146重复第一步的做法 6105=2146×2+1813
同理6105和2146的最大公约数也是2146和1813的最 大公约数。
完整的过程 8251=6105×1+2146 6105=2146×2+1813
探究1：用辗转相除法求225 和135的最大 公约数
探究2：辗转相除法的解题步骤 如何？其蕴含的数学原理是什 么？
辗转相除法算法步骤：
第一步：输入两个正整数a、b(a>b) ; 第二步：求a除以b的余数r； 第三步： 若r≠0，则把b的值赋于a， r的值
赋于b，转到第二步；否则转到第四步； 第四步：输出最大公约数b 数学原理是 ：在展转相除的过程中的b与r的 公约数始终和a与b的公约数相等，且相除的 步骤是有限的。
3.① 求24与30的最大公约数． ②求210与462的最大公约数．
（1） 2 24 30
3 12 15
45
（2）2 210 462
3 105 231 7 35 77
5 11
所以，24和30的最大公约数为6 210和462的最大公约数为42
如何求8251和6105的最大公约数？
新知探究
问题提出：当两个数公有的质因数较大时， 用原来的显然困难，须改进算法，用什么方 法好？
3．求三个以上(含三个数)的数的最大公约数时， 可依次通过求两个数的最大公约数与第三数的最 大公约数来求得．
区别是什么？
①都是求最大公约数的方法，辗转相除法以 除法为主，更相减损术以减法为主，计算次 数上辗转相除法计算次数相对较少，特别当 两个数字大小区别较大时计算次数的区别较 明显． ②结果上，辗转相除法体现结果是以相除余 数为0得到，而更相减损术则以减数与差相等 而得到.

[分析] 1. 七 进 制 数 从 右 边 数 第 二 位 的 数 字 若 是 k(k ＝ 0,1,2,3,4,5,6)，其在十进制中表示的数是多少？
2 ．相同进制中，位数越多的数越大对吗？不同进制中的
数如何比较大小？
第一章 1.3 第2课时
成才之路 ·高中新课程 ·学习指导 ·人教A版 ·数学 ·必修3
●自我检测 1．以下各数有可能是五进制数的是( A．15 C．731 B．106 D．21340 五进制数中各个数字均是小于5的自然数，则仅有 )
[答案] D
[解析] 21340满足，故选D.
第一章
1.3
第2课时
成才之路 ·高中新课程 ·学习指导 ·人教A版 ·数学 ·必修3
2．将二进制数1101(2)化为十进制数为( A．10 C．12 [答案] D B．11 D．13
第一章
1.3
第2课时
成才之路 ·高中新课程 ·学习指导 ·人教A版 ·数学 ·必修3
第一章
1.3
第2课时
成才之路 ·高中新课程 ·学习指导 ·人教A版 ·数学 ·必修3
程序： INPUT “a，k，n＝”；a，k，n b＝0 i＝1 t＝a MOD 10 DO b＝b＋t*k^(i－1) a＝a\10 t＝a MOD 10 i＝i＋1 i>n LOOP UNTIL _______ PRINT b END
1)． (2)在k进制中，由低位向高位是按“满k进一”的规则进行 计数． (3)不同进位制都是按位置原则计数的．
第一章 1.3 第2课时
成才之路 ·高中新课程 ·学习指导 ·人教A版 ·数学 ·必修3
[特别提醒]
在k进制数中，从右向左数第i位的数字m，在
十进制中表示m个ki－1.