资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,算 法 案 例,(,第一课时,),辗转相除法,与,更相减损术,求以下几组正整数的最大公约数。,（1）（18，30）（2）（24，16）,（3）（63，63）（4）（72，8）,（5）（301,，,133）,解：,2,1 8 2 4 用公有质因数,2,除，,3,9 1 2 用公有质因数,3,除，,3 4 3和4互质不除了。,得：18,和,24,最大公约数是：,2,3,6,想一想，如何求,8251,与,6105,的最大公约数？,例、求18与24的最大公约数：,6；,8；,63；,8；,7；,短除法,辗转相除法（欧几里得算法）,观察用辗转相除法求,8251,和,6105,的最大公约数的过程,第一步,用两数中较大的数除以较小的数，求得商和余数,8251=61051+2146,结论：,8251,和,6105,的公约数就是,6105,和,2146,的公约数，求,8251,和,6105,的最大公约数，只要求出,6105,和,2146,的公约数就可以了。,第二步,对,6105,和,2146,重复第一步的做法,6105=21462+1813,同理,6105,和,2146,的最大公约数也是,2146,和,1813,的最大公约数。,为什么呢？,思考：从上述的过程你体会到了什么？,完整的过程,8251=61051+2146,6105=21462+1813,2146=18131+333,1813=3335+148,333=1482+37,148=374+0,例,2,用辗转相除法求,225,和,135,的最大公约数,225=1351+90,135=901+45,90=452,显然,37,是,148,和,37,的最大公约数，也就是,8251,和,6105,的最大公约数,显然,45,是,90,和,45,的最大公约数，也就是,225,和,135,的最大公约数,思考,1,：从上面的两个例子可以看出计算的规律是什么？,S1,：用大数除以小数,S2,：除数变成被除数，余数变成除数,S3,：重复,S1,，直到余数为,0,解：,练习：用辗转相除法求下列两数的最大公约数：,（1）（225，135）（2）（98，196）,（3）（72，168）（4）（153，119）,45,98,24,17,辗转相除法求两个数的最大公约数，其算法可以描述如下：,辗转相除法是一个反复执行直到余数等于,0,停止的步骤，,这实际上是一个循环结构,思考：辗转相除法直到何时结束？主要运用的是哪种算法结构？,给定两个正整数,m,和,n,；,计算,m,除以,n,的余数,r,；,m=,n，n,=r。,若,r,=,0,则,m,n,的最大公约数等于,m;,否则返回第二步,.,辗转相除除法的程序框图与程序,开始,输入,m,n,r=,mMODn,m=n,n=r,r=0,？,输出,m,结束,否,是,INPUT m,n,DO,r=,mMODn,m=n,n=r,LOOP UNTIL r=0,PRINT m,END,九章算术,更相减损术,算理：,可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。,第一步：,任意给定两个正整数；判断他们是否,都是偶数,。若是，则用,2,约简；若不是则执行第二步。,第二步：,以,较大,的数减,较小,的数，接着把,所得的差,与,较小的数,比较，并以大数减小数。继续这个操作，,直到所得的减数和差相等为止,，则这个等数或这个等数与约简的数的乘积就是所求的最大公约数。,例、用更相减损术求,98,与,63,的最大公约数,解：由于,63,不是偶数，把,98,和,63,以大数减小数，并辗转相减,。,=,7,所以，,98,和,63,的最大公约数等于,7,。,（98，63）,=（63，35）,98-63=35,63-35=28,=（35，28）,35-28=7,=（28，7）,28-7=21,=（21，7）,21-7=14,=（14，7）,14-7=7,=（7，7）,练习：用更相减损术求下列两数的最大公约数：,（1）（225，135）（2）（98，196）,（3）（72，168）（4）（153，119）,45,98,24,17,更相减损是一个反复执行直到减数等于差时停止的步骤，,这实际也是一个循环结构,把更相减损术与辗转相除法比较,你有什么发现,?,你能根据更相减损术设计程序,求两个正整数的最大公约数吗,?,思考,?,辗转相除法是一个反复执行直到余数等于,0,停止的步骤，,这实际上是一个循环结构,程序：,INPUT“,a,b”;a,b,i=0,WHILE a MOD 2=0 AND b MOD 2=0,a=a/2,b=b/2,i=i+1,WEND,DO,IF ba THEN,t=a,a=b,b=t,END IF,a=a-b,LOOP UNTIL a=b,PRINT a*2i,END,开始,输入：,a,b,输出：,a2,i,结束,a=b?,a=a/2,b=b/2,是,a=a-b,t=,a,a,=,b,b,=t,ba?,a MOD 2=0,且,b MOD 2=0?,是,否,否,否,是,i=0,i=i+1,辗转相除法与更相减损术的区别：,小 结,（,1,）,都是求最大公约数的方法，计算上辗转相除法以除法,为主，更相减损术以减法为主，计算次数上辗转相除法计算,次数相对较少，特别当两个数字大小区别较大时计算次数的,区别较明显。,（,2,）从结果体现形式来看，辗转相除法体现结果是以相除,余数为,0,而得到，而更相减损术则以减数与差相等而得到的。,作业：,P48,习题：1.3,A,组 第,1,题,及练习册作业。,
展开阅读全文