资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,辗转相除法与更相减损术,算 法 案 例,高二,.,五班,1/23,1.,回顾算法三种表示方法：,（三种逻辑结构）,（,1,）、自然语言,（,2,）、程序框图,（,3,）、程序语言,（五种基本语句）,复习引入,:,2/23,2.,思索：,小学学过求两个数最大条约数方法？,先用两个公有质因数连续去除，,一直除到所得商是互质数为止，然,后把全部除数连乘起来,.,3/23,例：求下面两个正整数最大条约数：,求,22,和,6,最大条约数,22,2,11,6,3,所以，,22,和,6,最大条约数为,2,思索：除了用这种方法外还有没有其它方法？,例：怎样算出,8251,和,6105,最大条约数？,4/23,22,63,4,；,6,41,2,；,4,22,0,6cm,22cm,？,试用数学方法，求得此正方形边长？,5/23,新课讲解：,一、辗转相除法（欧几里得算法）,1,、定义：,所谓辗转相除法，就是对于给定两个数，用较大数除以较小数。若余数不为零，则将余数和较小数组成新一对数，继续上面除法，直到大数被小数除尽，则这时较小数就是原来两个数最大条约数。,6/23,欧几里德,辗转相除法,又名,欧几里德算法,(Euclid,ean algorithm),乃求两,个正整数之最大公因子,算法。它是已知最古,老算法,其可追溯至,3000,年前。,7/23,辗转相除法是一个重复执行直到余数等于,0,才,停顿步骤，这实际上是一个循环结构。,8251=61051+2146,6105=21462+1813,2146=18131+333,1813=3335+148,333=1482+37,148=374+0,m=n q,r,用程序框图表示出右边过程,r=m MOD n,m=n,n=r,r=0?,是,思索,2,：辗转相除法中关键步骤是哪种逻辑结构？,否,8/23,思索：,你能把辗转相除法编成一个计算机程序吗？,(1),、算法步骤：,第一步：输入两个正整数,m,n(mn).,第二步：计算,m,除以,n,所得余数,r.,第三步：,m=n,n=r.,第四步：若,r,0,则,m,n,最大条约数等于,m,；,不然转到第二步,.,第五步：输出最大条约数,m.,9/23,(2),、程序框图：,开始,输入,m,n,r=m MOD n,m=n,r=0?,是,否,n=r,输出,m,结束,10/23,(3),、程序：,INPUT “m,n=“;m,n,DO,r=m MOD n,m=n,n=r,LOOP UNTIL r=0,PRINT m,END,11/23,二、更相减损术,可半者半之，不可半者，副置分母、子之数，,以少减多，更相减损，求其等也，以等数约之。,第一步：,任意给定两个正整数；判断他们是否都是偶数。若是，则用,2,约简；若不是则执行第二步。,第二步：,以较大数减较小数，接着把所得差与较小数比较，并以大数减小数。继续这个操作，直到所得减数和差相等为止，则这个等数就是所求最大条约数。,（,1,）、,九章算术,中更相减损术：,1,、背景介绍：,（,2,）、当代数学中更相减损术：,12/23,2,、定义：,所谓更相减损术，就是对于给定两个数，用较大数减去较小数，然后将差和较小数组成新一对数，再用较大数减去较小数，重复执行此步骤直到差数和较小数相等，此时相等两数便为原来两个数最大条约数。,13/23,例,:,用更相减损术求,98,与,63,最大条约数,.,解：因为,63,不是偶数，把,98,和,63,以大数减小数，并辗转相减,98,63,3563,35,2835,28,728,7,21,21,7,21,14,7,7,所以，,98,和,63,最大条约数等于,7,3,、方法：,14/23,1,、用更相减损术求两个正数,84,与,72,最大条约数,练习：,思绪分析：先约简，再求,21,与,18,最大条约数,然后乘以两次约简质因数,4,。,2,、求,324,、,243,、,135,这三个数最大条约数。,思绪分析：求三个数最大条约数能够先求出两个数最大条约数，第三个数与前两个数最大条约数最大条约数即为所求。,15/23,(1),、算法步骤,第一步：输入两个正整数,a,b(ab);,第二步：若,a,不等于,b,则执行第三步；不然转到第五步；,第三步：把,a-b,差赋予,r;,第四步：假如,br,那么把,b,赋给,a,把,r,赋给,b;,不然把,r,赋给,a,，执行第二步；,第五步：输出最大条约数,b.,*,思索：你能依据更相减损术设计程序，求两个正整数最大条约数吗？,16/23,(2),、程序框图,开始,输入,a,b,a,b?,是,否,输出,b,结束,b=r,a=b,r=a-b,rr THEN,a=b,b=r,ELSE,a=r,END IF,WEND,PRINT b,END,18/23,比较辗转相除法与更相减损术区分,（,1,）都是求最大条约数方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，尤其当两个数字大小区分较大时计算次数区分较显著。,（,2,）从结果表达形式来看，辗转相除法表达结果是以相除余数为,0,则得到，而更相减损术则以减数与差相等而得到。,小结,19/23,学以致用,1.,求解不定方程,326X+78Y=2,一组,整数解,20/23,学以致用,2.,设计一个程序，求两个正整数最小公倍数。,（提醒：最小公倍数,=,两数之积除以最大条约数）,21/23,学以致用,3.,甲，乙，丙三种溶液分别重,147,克，,343,克，,133,克，现要将它们分别全部装入小瓶中，,每个小瓶中装入溶液质量相同，问每瓶,最多装多少？,22/23,作业：,1,、,P47 1,2,、,P50 2,23/23,
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
