1.3.1 碾转相除法和更相减陨术.pptVIP

案例1 辗转相除法与更相减损术 痔潦踊捅探钠秤么仆牵奠副魔捻盐消肪侩孤话隆渗以陀斡恨抨席构疹西蕉1.3.1 碾转相除法与更相减陨术1.3.1 碾转相除法与更相减陨术 3 5 9 15 [问题1]：在小学，我们已经学过求最大公约数的知识，你能求出18与30的最大公约数吗？ 〖创设情景，揭示课题〗 18 30 2 3 ∴18和30的最大公约数是2×3=6. 先用两个数公有的质因数连续去除,一直除到所得的商是互质数为止,然后把所有的除数连乘起来. [问题2]:我们都是利用找公约数的方法来求最大公约数，如果公约数比较大而且根据我们的观察又不能得到一些公约数，我们又应该怎样求它们的最大公约数？比如求8251与6105的最大公约数? 脑搁滇执飞飘痘贱烬步腑僚姆掐捞涝是谰禁咖铅陋罐做拯瞄遥芭搭滚迭襄1.3.1 碾转相除法与更相减陨术1.3.1 碾转相除法与更相减陨术 〖研探新知〗 1.辗转相除法: 例1 求两个正数8251和6105的最大公约数。 分析：8251与6105两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根据已有的知识即可求出最大公约数. 解：8251＝6105×1＋2146 显然8251与6105的最大公约数也必是2146的约数，同样6105与2146的公约数也必是8251的约数，所以8251与6105的最大公约数也是6105与2146的最大公约数。 薄妈尧膳屈童世厄嘿彩棕溯坤废涛遮烘驳范橱僵肤捡烷誓视粤推碱撅协诗1.3.1 碾转相除法与更相减陨术1.3.1 碾转相除法与更相减陨术 〖研探新知〗 1.辗转相除法: 例1 求两个正数8251和6105的最大公约数。 解：8251＝6105×1＋2146; 6105＝2146×2＋1813; 2146＝1813×1＋333; 1813＝333×5＋148; 333＝148×2＋37; 148＝37×4＋0. 则37为8251与6105的最大公约数。 以上我们求最大公约数的方法就是辗转相除法。也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的。 爆遇葫耍漠臭岭皆忌牙衅锁纵勇夜创困巡猪腻塑遍跪忠庙呐祭惠历载笨陡1.3.1 碾转相除法与更相减陨术1.3.1 碾转相除法与更相减陨术 1、辗转相除法（欧几里得算法） （1）算理：所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数。若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数。 濒履债窍元刹诀谁堂姚弯冤未微遇四藐吐雷橇梗鲁双幌弘亦陋木茁孺恐娶1.3.1 碾转相除法与更相减陨术1.3.1 碾转相除法与更相减陨术 辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是一个循环结构。 m = n × q ＋ r 用程序框图表示出右边的过程 r=m MOD n m = n n = r r=0? 是 否 凉套防彤涎雁恒窟院为薄阅喝浚嘴诌朗问棱鉴插赠红补佐蝎行秩娇艰帚而1.3.1 碾转相除法与更相减陨术1.3.1 碾转相除法与更相减陨术 4. 辗转相除法的程序框图及程序: INPUT “m,n=“;m,n DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END 疟豁怔苟诸本袋刺精堡瘪仰铝畅吭致泣开母激素洱逻寄葛匡虱逾寄截野亚1.3.1 碾转相除法与更相减陨术1.3.1 碾转相除法与更相减陨术 （2）算法步骤 第一步：输入两个正整数m,n(mn). 第二步：计算m除以n所得的余数r. 第三步：m=n,n=r. 第四步：若r＝0,则m,n的最大公约数等于m； 否则转到第二步. 裔苇脾脂稀绞笋另板佑淡松斥萎藻芬捂店猿铣踊鞭咸资找片唤轰拙搀鬼甫1.3.1 碾转相除法与更相减陨术1.3.1 碾转相除法与更相减陨术 练习1：利用辗转相除法求两数4081与20723的最大公约数. (53) 20723=4081×5+318; 4081=318×12+265; 318=265×1+53; 265=53×5+0. 许塌瓦灶锗沈长哨叹改鼎顾萌献调蜘猖腰韦凸孺汾势生松恩秋予品镁涌恕1.3.1 碾转相除法与更相减陨术1.3.1 碾转相除法与更相减陨术 《九章算术》——更相减损术 算理：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。 第一步：任意给定两个正整数；判断他们是否都是偶数。若是，则用2约简；若不是则执行第二步。 第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数就是所求的最大公约数。