•1. 3算法案例第1课时極特相除法与更相濒损术* T «• ** T • -t * * 1 « *KQZZYX课前自主预习• 1.用两数中较人的数减去较小的数, 再用所得差和较小数构成新的一对数，再用______ ^减______ ;数以同样的操作一直做下去，直到所得的两数相等为止，这个数就是这两个数的最大公约数.这个方法称作“更相减损术”，用它编写的算法称作“等值算法”・• 2.古希腊求两个正整数的最大公约数的方法是辗转相除法：用较大数除以较小数所得的余数和较小数构成新的一对数，继续做上面的除法，直到大数被小数除尽, 这个较小的数就是最大公约数.据此编写的算法，也称作“欧几里得算法” •3・对于正整数加与n(m>n),总能找到整数g 和r(O<r<n)使得m=nq+rf^立，这个除法称为带余除法.通常记r=mMODn.ZDNDZS 重点难点展示•重点：算法案例的原理、算法设计及算法思想的体会.•难点：理解算法案例的内容及具体算法设计的关键步骤.XXYDDB学习要点点拨• 一、弄清算法原理，掌握算法程序，经历蠶翳■，聶’体会算法设计的关键环节,• 1 •辗转相除法•(1)辗转相除的原理：・设zn, 〃是两个整数(不妨设m>ri),用加除以〃，若商为务, 余数为厂1(00］<小则m = n・牛+厂1，显然若兀是加和〃的公约数，即x能整除加和弘贝吹也必然能整除厂1，这样x也是〃和厂］的公约数，故求加和〃的公约数就是求〃和厂1的公约数；同理，用〃除以厂1，得n = r x -^2 + ^(0<^<^),故求加和斤的公约数就是求厂2和厂1的公约薮，…，依次下去，由于加>〃>厂］>厂2>…，所以到某一步必然有r z = r/+19q汁"即耳恰能被厂计］整除，这时耳+1是耳和厂j+1的最关公约数，它也必然是耳_1和乙、厂—2和耳_1、…、厂1与厂2、〃和厂2、加和〃的最大公约数.• (2)辗转相除法的算法分析:•由以上辗转相除法的原理可以发现，辗转相除法的基本步骤是用较大的数除以较小的数，考虑到算法中的赋值语句可以对同一变量多次赋值，我们可以把较大的数用变量加表示，把较小的数用变量〃表示，这样式子m = n -q + r(O<r<^)就是一个反复执行的步骤，因此可以用循环结构实现算法.如图.• (3)用辗转相除法求任意两个正整数最大公约数的程序框图. •由于辗转相除法总是用较大的数去除以较小的数，所以首先要对一开始给定的两数的大小进行判断，并将大数赋给加，小数赋给弘然后再执行下面的过程.程序框图如图.（开始）*/输入a，bt 二a 仃二I)b=tEND IF丁二 1WHILE r< >0 「二a MOD b a = b b -rWENDPRINT aEND•2.更相减损术•（1）更相减损术求两数最大公约数的过程与算法设计.•对于给定的两个数，用较大的数减去较小的数，接着把得到的差与较小的数比较，用这时两个数中较大的数减去较小的数，继续这样的操作（夭数减小藪：），直到所得的数相等为止，那么这个数（相等数）就是所求的最大公约数.•显然，上述过程中大数减去小数是一个重复执行的过程，因此只需将大数赋给变量a,小数赋给变量b,那么就可以通过循环结构实现算法.或当时，将d —b赋给b = b,当xb 时，a=a,将赋给b然后再进行比较，依次类推用循环结构实现.•⑵更相减损术求最大公约数的程序设计女口T：•请自行将其直到型循环结构算法写岀来. • 3 •辗转相除法与更相减损术有着相同的算法依据，但要注意运算过程的差别，辗转相除法的上一次运算的除数和余数分别作为下一次运算的被除数和除数，其结果直至余数为零得出.更相减损术在上一次运算结束后，比较减数和差的大小，将大的作为下一次运算的被减数，小的作为减数，直至岀现相等数时得到结果.•由此可见，二者算法是相似的.主要区别在于，辗转相除法进行的是除法运算，即辗转相除，更相减损术进行的是减法运算, 即辗转相减，但其实质都是一个不断的递归过程.另外两者在算法设计上有一个重要的区别点，辗转相除法，下一次进行相除时，由上一次的除数和余数直接相除即可.而更相减损术下一次相减前必须有一个判断大小的过程，以区别谁做被减数.这些内容都是应特别注意的关键环节.• 4.用更相减损术求两正整数的最大公约数时，若两数为偶数，可先约去2,这时莫忘记求得的相等两数乘以约简的数才是所求最夫公约薮.STYYLX 随堂应用练习•一、填空题•1.在对16和12求最大公约数时，整个操作如下：(16,12)—- (4,12)—- (4,8)—-(4,4),由匕可以看出12和16的最大公约数是•［答案］4• 2. 1443与999的最大公约数是_________ •［答案］111•［解析］• (999,1443)——(999,444)——(555,444)一-> (111,444)一一(111,333)—一(111,222)一->( 111,111)•或1443 ・ 999 = 444,999 - 444 = 555,555 - 444 = 111,444 - 111 = 333,333 - 111 = 222,222 - 111 = 111.•自己用辗转相除法写出解答过程.• 3.运算速度快是计算机一个很重要的特点，而算法好坏的一个重要标志是■•［答案］运算次数• 4. 2004与4509的最大公约数为167.・・ 2004 = 22 x3 x 167.450915()3501167•［答案］5012004 2 1002 2 501 3•「.4509 = 33x167 , •••2004与4509的最大公约数为3x167 = 501.•自己用辗转相除法和更相减损术写出解答.•二、解答题• 5.写出从键盘任意输入两个正整数a, b, 输出这两个数的最小公倍数的算法，画出程序框图，写出算法语句.［解析］约数匕程序框图如右图.程序为：INPUT “正整数°, b = p=a*bIF a<b THENEND IFDO从键盘输入两数Q, 再计算两数的最小公倍数b后，先求两数的最大公a-b亠人tP~~k，输出P即可.r/ 输* a,b 7。
