资源描述
,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,算法案例,辗转相除法与更相减损术,算法案例辗转相除法与更相减损术,知识回顾,1,回顾算法的三种表述：,自然语言,程序框图,程序语言,.,程序框图有三种逻辑结构,:,顺序结构,条件结构,循环结构,.,程序语言有五种基本算法语句,:,输入语句,输出语句,赋值语句,条件语句,循环语句,.,知识回顾1 回顾算法的三种表述：自然语言,程序框图,程序,2,回顾求两个数的最大公约数的法,先用两个公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来,.,3.,求,24,与,30,的最大公约数,求,210,与,462,的最大公约数,2回顾求两个数的最大公约数的法 先用两个公有的质因数连,如何求,8251,和,6105,的最大公约数？,所以，,24,和,30,的最大公约数为,6,210,和,462,的最大公约数为,42,24,（,1,）,2,12,30,15,4,3,5,210,（,2,）,2,105,462,231,3,35,7,5,77,11,如何求8251和6105的最大公约数？所以，24和30的最,1,、辗转相除法（欧几里得算法）,所谓辗转相除法,就是对于给定的两个数,用较大的数除以较小的数,.,若余数不为零,则将余数和较小的数构成新的一对数,继续上面的除法,直到大数被小数除尽,则这时较小的数就是原来两个数的最大公约数,.,例,1.,用辗转相除法求,98,与,63,的最大公约数,.,98=163,35,63=1 35,28,35=1 28,7,28=4 7,0,所以，,98,与,63,的最大公约数为,7,新 课,1、辗转相除法（欧几里得算法）所谓辗转相除法,就是对,探究,1,。用辗转相除法求,225,和,135,的最大,公约数,完整的过程,8251=61051+2146,6105=21462+1813,2146=18131+333,1813=3335+148,333=1482+37,148=374+0,显然,37,是,148,和,37,的最大公约数，也就是,8251,和,6105,的最大公约数,显然,45,是,90,和,45,的最大公约数，也就是,225,和,135,的最大公约数,探究,2,：辗转相除法的解题步骤如何？其蕴含的数学原理是什么？,225=1351+90,135=901+45,90=452,探究1。用辗转相除法求225和135的最大完整的过程825,辗转相除法是一个反复执行直到余数等于,0,停止的步骤,这实际上是一个循环结构,m=nq,r,思考：辗转相除法中的关键步骤是哪种逻辑结构？,算法步骤,第一步：输入两个正整数,m,n(mn).,第二步：计算,m,除以,n,所得的余数,r.,第三步：,m=n,n=r.,第四步：若,r,0,则,m,n,的最大公约数等于,m;,否则转到第二步,.,第五步：输出最大公约数,m.,辗转相除法是一个反复执行直到余数等于0停止的步骤,这,程序框图,程 序,r=m MOD n,m=n,是,否,n=r,开始,输入,m,n,r=0?,输出,m,结束,INPUT“m,n=“;m,n,DO,LOOP UNTIL,r=m MOD n,m=n,n=r,r=0,PRINT m,END,程序框图程 序r=m MOD nm=n是否n=r开始输入m,程序框图,程 序,INPUT“m,n=“;m,n,WHILE,WEND,r=m MOD n,m=n,n=r,r0,PRINT m,END,r=1,求,m,除以,n,的余数,r,m=n,是,否,n=r,开始,输入,m,n,r0?,输出,m,结束,r=1,程序框图程 序INPUT“m,n=“;m,nWHILE W,4,问题提出：除了用上述算法求两个数的最 大公约数之外还有没有别的算法？,5,点拨：用“更相减损术”：,更相减损术，是我国数学家刘徽的专著,九章算术,中记载的更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母分子之数，以少减 多，更相减损，求其等也,.,，以等数约之,4问题提出：除了用上述算法求两个数的最 大公约数之外,翻译出来为：,第一步：任意给出两个正数；判断它们是否都是偶数若是，用,2,约简；若不是，执行第二步,第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数,例,2,用更相减损术求,91,与,49,的最大公约数，并用,辗转相除法检验结果,翻译出来为：例2 用更相减损术求91与49的最大公约数，并,解法,1,：,（,更相减损术）由于,49,不是偶数，把,91,和,49,以大数减小数，并辗转相减，,即：,91,49,42 49,42,7 42,7,35 35,7,28,28,7,21 21,7,14 14,7,7,91,与,49,的最大公约数是,7,。,解法,2,（,辗转相除法）,91,491,42 49,421,7,42,76,91,与,49,的最大公约数是,7,。,解法1：（更相减损术）由于49不是偶数，把91和49以大数减,探究,3:,怎样用更相减损术求,182,与,98,的最大公约数,?,方法：由于,182,与,98,都是偶数，故将它们同除以,2,，得,91,与,49,，再用上面的方法求得,91,与,49,的最大公约数为,7,，则,72=14,为,182,与,98,的最大公约数,.,探究3:怎样用更相减损术求182与98的最大公约数?方法,INPUT“m,n=”;m,n,WHILE mn,IF mn THEN,m=m-n,ELSE,n=n-m,END IF,WEND,PRINT n,END,程序框图,输入,m,n,开始,mn,？,mn,？,m=m-n,n=n-m,输出,n,结束,N,Y,Y,N,算法步骤,(1),输入两个整数,m,，,n,(2),若,mn,转到,(3),否则转到,(4),(3),若,mn,则,m=m-n,否则,n=n-m,转到,(2),(4),输出最大公约数,n,INPUT“m,n=”;m,n程序框图输入m,n开始mn,探究,4:,用更相减损术求,80,与,36,的最大公约数，并用辗转相除法检验结果,用更相减损术,:,用辗转相除法检验,:,80-36=44 80=362,8,44-36=8,36=84,4,36-8=28 8=42,0,28-8=20,20-8=12 80,与,36,的最大公约数是,4,12-8=4,8-4=4,80,与,36,的最大公约数是,4,探究4:用更相减损术求80与36的最大公约数，并用辗转相除法,思考,:,“,辗转相除法”与“更相减损术”的区别是什么？,都是求最大公约数的方法，辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显,结果上，辗转相除法体现结果是以相除余数为,0,得到，而更相减损术则以减数与差相等而得到,.,思考:“辗转相除法”与“更相减损术”的区别是什么？都是,板块三：知识拓展,问题提出：如何求三个正整数的最大公约数？,分析：可以先求出其中两个数的最大公约数，用这两个数的最大公约数再与第三个数求最大公约数，所得结果就是这三个数的最大公约数。,板块三：知识拓展问题提出：如何求三个正整数的最大公约数？,例,3,求三个数,175,、,100,、,75,的最大公约数,解：先求,175,与,100,的最大公约数：,175=1001+75,100=751+25,75=253,175,与,100,的最大公约数是,25.,再求,75,与,25,的最大公约数,:,由,75=253,或,75,25,50,，,50,25,25,，,得,75,与,25,的最大公约数是,25,，,三个数,175,、,100,、,75,的最大公约数是,25,例3求三个数175、100、75的最大公约数解：先求175,探究,6:,如何求,4,个正整数的最大公约数,？,方法,1:,可以先求其中两个数的最大公约数,a,，再求,a,与第三个数的公约数,b,，再求,b,与第四个数的公约数,c,，则,c,为这,4,个数的最大公约数。,方法,2:,将,4,个数分两组，每组两个数，先求,每组两个数的最大公约数,a,与,b,，再求,a,与,b,的,最大公约数,c,则,c,就是这,4,个数的最大公约数。,探究6:如何求4个正整数的最大公约数？方法1:可以先求其中两,板块五：课堂总结,1,“,辗转相除法,”,与,“,更相减损术,”,都是求最大公约数有的效方法；,2,计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显；从结果体现形式来看，辗转相除法体现结果是以相除余数为,0,则得到，而更相减损术则以减数与差相等而得到,3,求三个以上,(,含三个数,),的数的最大公约数时，可依次通过求两个数的最大公约数与第三数的最大公约数来求得,板块五：课堂总结1“辗转相除法”与“更相减损术”都是求最大,
展开阅读全文