1、第一章 算法初步1.3 算法案例1.3 算法案例(第 1 课时)辗转相除法与更相减损术学习目标1.理解辗转相除法与更相减损术中蕴含的数学原理,并能根据这些原理进行算法分析.2.基本上能根据程序框图与算法语句的知识设计完整的程序框图并写出算法程序.合作学习一、设计问题,创设情境问题 1:18 与 30 的最大公约数是多少 ?你是怎样得到的?问题 2:如何求两个正数 8 251 和 6 105 的最大公约数?二、信息交流,揭示规律导引 1:对于 8 251 与 6 105 这两个数,由于其公有的质因数较大,利用前面的方法求最大公约数比较困难.注意到 8 251=6 1051+2 146,那么 8
2、251 与 6 105 这两个数的公约数和 6 105 与 2 146 的公约数有什么关系呢?导引 2:又 6 105=2 1462+1 813,同理,6 105 与 2 146 的最大公约数和 2 146 与 1 813 的最大公约数相等.重复上述操作,你能得到 8 251 与 6 105 这两个数的最大公约数吗?问题 3:设两个正整数 mn,若 m-n=k,则 m 与 n 的最大公约数和 n 与 k 的最大公约数相等.反复利用这个原理,可求得 98 与 63 的最大公约数为多少?三、运用规律,解决问题问题 4:(1)用辗转相除法可以求两个正整数 m,n 的最大公约数,那么用什么逻辑结构来设
3、计该算法?其算法步骤又如何设计?(2)该算法的程序框图如何表示?该程序框图对应的程序如何表述?四、变式训练,深化提高1.下列有关辗转相除法的说法正确的是( )A.它和更相减损术一样是求多项式值的一种方法B.基本步骤是用较大的数 m 除以较小的数 n 得到除式 m=nq+r,直至 rn 为止C.基本步骤是用较大的数 m 除以较小的数 n 得到除式 m=qn+r(0rn) 反复进行,直到r=0 为止D.以上说法均不正确2.在 m=nq+r(0rn)中,若 k 是 n,r 的公约数,则 k m,n 的公约数( ) A.一定是 B.不一定是 C.一定不是 D.不能确定3.有甲、乙、丙三种溶液分别重 1
4、47 g,343 g,133 g,现要将它们分别全部装入小瓶中,每个小瓶装入溶液的质量相同,则每瓶最多装多少溶液?五、反思小结,观点提炼1.本节课我们学习了哪些知识内容?2.你认为辗转相除法、更相减损术的原理是什么?3.辗转相除法和更相减损术,哪一个效率更高?布置作业1.课本 P48 习题 1.3 A 组第 1 题.2.(1)用辗转相除法求 840 与 1 764 的最大公约数.(2)用更相减损术求 459 与 357 的最大公约数.参考答案一、设计问题,创设情境问题 1:先用两个数公有的质因数连续去除 ,一直除到所得的商是互质数为止,然后把所有的除数连乘起来即为最大公约数.由于 ,所以,18
5、 与 30 的最大公约数是 23=6.问题 2:略.二、信息交流,揭示规律导引 1:显然 8 251 与 6 105 这两个数的公约数也必是 2 146 的约数,同样 6 105 与 2 146的公约数也必是 8 251 的约数,所以 8 251 与 6 105 的最大公约数也是 6 105 与 2 146 的最大公约数.导引 2:8 251=6 1051+2 146,6 105=2 1462+1 813,2 146=1 8131+333,1 813=3335+148,333=1482+37,148=374.最后的除数 37 是 148 和 37 的最大公约数,也就是 8 251 与 6 10
6、5 的最大公约数.问题 3:由于 63 不是偶数,把 98 和 63 以大数减小数,并辗转相减,得98-63=35,63-35=28,35-28=7,28-7=2121-7=14,14-7=7.可知 98 与 63 的最大公约数为 7.三、运用规律,解决问题问题 4:(1)用直到型循环结构设计算法,如下:第一步,给定两个正整数 m,n.第二步,计算 m 除以 n 所得的余数 r.第三步,m=n,n=r.第四步,若 r=0,则 m,n 的最大公约数等于 m;否则,返回第二步.(2)程序框图:程序:INPUT m,nDOr=m MOD nm=nn=rLOOP UNTIL r=0PRINT mEND
7、四、变式训练,深化提高1.C2.解析:k 是 n,r 的公约数,则 n=kk1,r=kk2,m=nq+r=kk1q+kk2=(k1q+k2)k,所以 k 是 m 的约数,即k 一定是 m,n 的公约数.答案:A3.解:每个小瓶的溶液的质量应是三种溶液质量 147,343,133 的公约数,最大质量即是其最大公约数.先求 147 与 343 的最大公约数:343-147=196,196-147=49,147-49=98,98-49=49.所以 147 与 343 的最大公约数是 49.再求 49 与 133 的最大公约数:133-49=84,84-49=35,49-35=14,35-14=21,21-14=7,14-7=7.所以 49 与 133 的最大公约数是 7,所以 147,343,133 的最大公约数是 7.即每瓶最多装 7 g 溶液.五、反思小结,观点提炼略
浙公网安备33030202001339号