算法案例时辗转相除法与更相减损术学案-新人教A版必修.pptx

13算算 法法 案案 例例1用两数中的数减去的数，再用构成新的一对数，再用减，以同样的操作一直做下去，直到所得的两数相等为止，这个数就是这两个数的最大公约数这个方法称作“更相减损术”，用它编写的算法称作“等值算法”较大较小所得差和较小数大数小数2古希腊求两个正整数的最大公约数的方法是：用除以所得的和构成新的一对数，继续做上面的除法，直到大数被小数除尽，这个较小的数就是最大公约数据此编写的算法，也称作“欧几里得算法”辗转相除法较大数较小数余数较小数3对于正整数m与n(mn)，总能找到整数q和r(0rn)，用m除以n，若商为q1，余数为r1(0r1n)，则mnq1r1，显然若x是m和n的公约数，即x能整除m和n，则x也必然能整除r1，这样x也是n和r1的公约数，故求m和n的公约数就是求n和r1的公约数；同理，用n除以r1，得nr1q2r2(0r2nr1r2，所以到某一步必然有riri1qi2，即ri恰能被ri1整除，这时ri1是ri和ri1的最大公约数，它也必然是ri1和ri、ri2和ri1、r1与r2、n和r2、m和n的最大公约数(2)辗转相除法的算法分析：由以上辗转相除法的原理可以发现，辗转相除法的基本步骤是用较大的数除以较小的数，考虑到算法中的赋值语句可以对同一变量多次赋值，我们可以把较大的数用变量m表示，把较小的数用变量n表示，这样式子mnqr(0rb时，将ab赋给a，bb，当ab时，aa，将ba赋给b然后再进行比较，依次类推用循环结构实现(2)更相减损术求最大公约数的程序设计如下：请自行将其直到型循环结构算法写出来3辗转相除法与更相减损术有着相同的算法依据，但要注意运算过程的差别，辗转相除法的上一次运算的除数和余数分别作为下一次运算的被除数和除数，其结果直至余数为零得出更相减损术在上一次运算结束后，比较减数和差的大小，将大的作为下一次运算的被减数，小的作为减数，直至出现相等数时得到结果由此可见，二者算法是相似的主要区别在于，辗转相除法进行的是除法运算，即辗转相除，更相减损术进行的是减法运算，即辗转相减，但其实质都是一个不断的递归过程另外两者在算法设计上有一个重要的区别点，辗转相除法，下一次进行相除时，由上一次的除数和余数直接相除即可而更相减损术下一次相减前必须有一个判断大小的过程，以区别谁做被减数这些内容都是应特别注意的关键环节4用更相减损术求两正整数的最大公约数时，若两数为偶数，可先约去2，这时莫忘记求得的相等两数乘以约简的数才是所求最大公约数例1用辗转相除法和更相减损术两种方法求80和36的最大公约数解析用辗除相除法：803628，36844，8420.故80和36的最大公约数是4.用更相减损术：803644，44368，36828，28820，20812，1284，844.80和36的最大公约数是4.点评(1)辗转相除法是当大数被小数除尽时，结束除法运算，较小的数就是最大公约数；更相减损术是当大数减去小数的差等于小数时停止减法运算，较小的数就是最大公约数(2)用更相减损术求时，如果先约去22，则变为求20和9的最大约数，最后结果再乘以4.(1)用辗转相除法求288与123的最大公约数(2)用更相减损术求57与93的最大公约数(3)求567与405的最小公倍数解析(1)288123242,12342239，423913,39313，288和123的最大公约数是3.(2)(93,57)(36,57)(36,21)(15,21)(15,6)(9,6)(3,6)(3,3)，93与57的最大公约数是3.(3)5674051162405162281162812081是567与405的最大公约数，从而567与405的最小公倍数为567405812835.例2求324,243和135的最大公约数解析先求324与243的最大公约数a，再求a与135的最大公约数b，则b为这三个数的最大公约数3242431812438130则324与243最大公约数为：a81又135811548154127542720则81与135的最大公约数为27324、243、135的最大公约数为27.一、填空题1在对16和12求最大公约数时，整个操作如下：(16,12)(4,12)(4,8)(4,4)，由此可以看出12和16的最大公约数是_答案421443与999的最大公约数是_答案111解析(999,1443)(999,444)(555,444)(111,444)(111,333)(111,222)(111,111)或1443999444,999444555,555444111,444111333,333111222,222111111.自己用辗转相除法写出解答过程3运算速度快是计算机一个很重要的特点，而算法好坏的一个重要标志是_答案运算次数42004与4509的最大公约数为_答案501解析4509 33167，2004与 4509的 最 大 公 约 数 为3167501.自己用辗转相除法和更相减损术写出解答二、解答题5写出从键盘任意输入两个正整数a，b，输出这两个数的最小公倍数的算法，画出程序框图，写出算法语句ra MOD babbrLOOP UNTILr0pp/aPRINT“m、n的最小公倍数为”；pEND.