辗转相除法与更相减损术课件.ppt
算法案例,辗转相除法与更相减损术,知识回顾,1 回顾算法的三种表述：自然语言,程序框图,程序语言.程序框图有三种逻辑结构:顺序结构,条件结构,循环结构.程序语言有五种基本算法语句:输入语句,输出语句,赋值语句,条件语句,循环语句.,2回顾求两个数的最大公约数的法,先用两个公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来.3.求24与30的最大公约数 求210与462的最大公约数,如何求8251和6105的最大公约数？,所以，24和30的最大公约数为6,210和462的最大公约数为42,1、辗转相除法（欧几里得算法）,所谓辗转相除法,就是对于给定的两个数,用较大的数除以较小的数.若余数不为零,则将余数和较小的数构成新的一对数,继续上面的除法,直到大数被小数除尽,则这时较小的数就是原来两个数的最大公约数.,例1.用辗转相除法求98与63的最大公约数.,98=1633563=1 352835=1 28728=4 70,所以，98与63的最大公约数为7,新 课,探究1。用辗转相除法求225和135的最大公约数,完整的过程,显然37是148和37的最大公约数，也就是8251和6105的最大公约数,显然45是90和45的最大公约数，也就是225和135的最大公约数,探究2：辗转相除法的解题步骤如何？其蕴含的数学原理是什么？,225=1351+90,135=901+45,90=452,辗转相除法是一个反复执行直到余数等于0停止的步骤,这实际上是一个循环结构,m=nqr,思考：辗转相除法中的关键步骤是哪种逻辑结构？,程序框图,程 序,程序框图,程 序,4问题提出：除了用上述算法求两个数的最 大公约数之外还有没有别的算法？,5点拨：用“更相减损术”：更相减损术，是我国数学家刘徽的专著九章算术中记载的更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母分子之数，以少减 多，更相减损，求其等也.，以等数约之,翻译出来为：第一步：任意给出两个正数；判断它们是否都是偶数若是，用2约简；若不是，执行第二步第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数,例2 用更相减损术求91与49的最大公约数，并用辗转相除法检验结果,解法1：（更相减损术）由于49不是偶数，把91和49以大数减小数，并辗转相减，即：914942 49427 42735 35728 28721 21714 147791与49的最大公约数是7。,解法2（辗转相除法）9149142 494217 4276 91与49的最大公约数是7。,探究3:怎样用更相减损术求182与98的最大公约数?,方法：由于 182与98 都是偶数，故将它们同除以2，得91与49，再用上面的方法求得91与49的最大公约数为7，则72=14为182与98的最大公约数.,探究4:用更相减损术求80与36的最大公约数，并用辗转相除法检验结果,用更相减损术:用辗转相除法检验:80-36=44 80=3628 44-36=836=844 36-8=28 8=420 28-8=20 20-8=12 80与36的最大公约数是4 12-8=4 8-4=4 80与36的最大公约数是4,思考:“辗转相除法”与“更相减损术”的区别是什么？,都是求最大公约数的方法，辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显结果上，辗转相除法体现结果是以相除余数为0得到，而更相减损术则以减数与差相等而得到.,板块三：知识拓展,问题提出：如何求三个正整数的最大公约数？分析：可以先求出其中两个数的最大公约数，用这两个数的最大公约数再与第三个数求最大公约数，所得结果就是这三个数的最大公约数。,例3求三个数175、100、75的最大公约数,解：先求175与100的最大公约数：175=1001+75,100=751+25,75=253,175与100的最大公约数是25.再求75与25的最大公约数:由75=253,或752550，502525，得75与25的最大公约数是25，三个数175、100、75的最大公约数是25,探究6:如何求4个正整数的最大公约数？,方法1:可以先求其中两个数的最大公约数a，再求a与第三个数的公约数b，再求b与第四个数的公约数c，则c为这4个数的最大公约数。方法2:将4个数分两组，每组两个数，先求 每组两个数的最大公约数a与b，再求a与b的 最大公约数c,则c就是这4个数的最大公约数。,板块五：课堂总结,1“辗转相除法”与“更相减损术”都是求最大公约数有的效方法；2计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显；从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到3求三个以上(含三个数)的数的最大公约数时，可依次通过求两个数的最大公约数与第三数的最大公约数来求得,
