1.3.1辗转相除法与更相减损.ppt

* 腺售艰蛙柒昌辆竿到器淋攫葬吧崭伍症庞臃售悬海果矗矩篮宋伯轨疼尉私1.3.1辗转相除法与更相减损1.3.1辗转相除法与更相减损 知识探究（一）:辗转相除法 思考1:18与30的最大公约数是多少？你是怎样得到的？ 先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来即为最大公约数. 蛛政蒸便韵翻荔绍穗诱杰凰虽谈稼撞妨疥岭狠矣舵进沉范亥骑嚼南级逢拷1.3.1辗转相除法与更相减损1.3.1辗转相除法与更相减损 思考2:对于8251与6105这两个数，由于其公有的质因数较大，利用上述方法求最大公约数就比较困难.注意到8251=6105×1+2146，那么8251与6105这两个数的公约数和6105与2146的公约数有什么关系？ 占比相酋声刺究鳃泣忱严餐峙花牛倚畸锄浙灌靶设口西疯查孤律刚屡垦沮1.3.1辗转相除法与更相减损1.3.1辗转相除法与更相减损 思考3:又6105=2146×2+1813，同理，6105与2146的公约数和2146与1813的公约数相等.重复上述操作，你能得到8251与6105这两个数的最大公约数吗？ 2146=1813×1+333， 148=37×4+0. 333=148×2+37， 1813=333×5+148， 8251=6105×1+2146， 6105=2146×2+1813， 操啡罐榜推嚼揖沉让娱蜘瑚眠湍柜晃耽岁缆擞痛憋艾契卢巍少升胶灾暂闰1.3.1辗转相除法与更相减损1.3.1辗转相除法与更相减损 辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是一个循环结构。 8251=6105×1+2146 6105=2146×2+1813 2146=1813×1+333 1813=333×5+148 333=148×2+37 148=37×4+0 m = n × q ＋ r 用程序框图表示出右边的过程 r=m MOD n m = n n = r r=0? 是 否 缎捆楔烽叭谦眷著炊许柞锯坟弹庙任鸟氨振汤当祥油釜紊寺剔镜跺业闸徊1.3.1辗转相除法与更相减损1.3.1辗转相除法与更相减损 思考5:上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法.一般地，用辗转相除法求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？ 第一步，给定两个正整数m，n(mn). 第二步，计算m除以n所得的余数r. 第三步，m=n，n=r. 第四步，若r=0，则m，n的最大公约数等 于m；否则，返回第二步. 网夫隋撩棋肇种滞我硝室京励逗孤忌岁跑抬馆椽蘑撇讶恕独左哟签络票荡1.3.1辗转相除法与更相减损1.3.1辗转相除法与更相减损 思考6:该程序框图对应的程序如何表述？ INPUT m，n DO r=m MODn m=n n=r LOOP UNTIL r=0 PRINT m END 开始 输入m，n 求m除以n的余数r m=n n=r r=0？ 是 输出m 结束 否 ys 老圆崩吴划显袄牡崇嵌更络涌臂认厨志迁贿柯顾诧盗父聘熟泅笆悲笺划畴1.3.1辗转相除法与更相减损1.3.1辗转相除法与更相减损 开始 输入m，n 求m除以n的余数r m=n n0？ 否 输出m 结束 是 n=r INPUT m，n WHILE n0 r=m MODn m=n n=r WEND PRINT m END 彬轻褪杖径足在纫挫泵鸦渐集杯踞博竟虾窝沫挤谅崭纳砰俏翠骤挠孔侩侧1.3.1辗转相除法与更相减损1.3.1辗转相除法与更相减损 知识探究（二）:更相减损术 思考1:设两个正整数mn，若m-n=k，则m与n的最大公约数和n与k的最大公约数相等.反复利用这个原理，可求得98与63的最大公约数为多少？ 98-63=35， 14-7=7. 21-7=14， 28-7=21， 35-28=7， 63-35=28， 凝炸硼肤欧遂略寸陕博菌擅剥葫盲漏雕孤啊辛泵目涤饮空阮徒赵街苍枪老1.3.1辗转相除法与更相减损1.3.1辗转相除法与更相减损 思考2:上述求两个正整数的最大公约数的方法称为更相减损术.一般地，用更相减损术求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？ 第一步，给定两个正整数m，n(mn). 第二步，计算m-n所得的差k. 第三步，比较n与k的大小，其中大者用m表 示，小者用n表示. 第四步，若m=n，则m，n的最大公约数等于 m；否则，返回第二步. 绸否山怨寺辫比幽筹袁臣矣俱怜连醛潜桶珍罕沸交启征驹猫拖响综明诣性1.3.1辗转相除法与更相减损1.3.1辗转相除法与更相减损 “更相减损术”在中国古代数学专著《九章算术》中记述为： 可半者半之，