资源描述
1.3,算法案例,第一课时,问题提出,1.,研究一个实际问题的算法，主要从算法步骤、程序框图和编写程序三方面展开,.,在程序框图中算法的基本逻辑结构有哪几种？在程序设计中基本的算法语句有哪几种？,2.,“,求两个正整数的最大公约数,”,是数学中的一个基础性问题，它有各种解决办法，我们以此为案例，对该问题的算法作一些探究,.,辗转相除法与,更相减损术,知识探究（一）,:,辗转相除法,思考,1:,18,与,30,的最大公约数是多少？你是怎样得到的？,先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来即为最大公约数,.,思考,2:,对于,8251,与,6105,这两个数，由于其公有的质因数较大，利用上述方法求最大公约数就比较困难,.,注意到,8251=6105,1+2146,，那么,8251,与,6105,这两个数的公约数和,6105,与,2146,的公约数有什么关系？,思考,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,，,辗转相除法是一个反复执行直到余数等于,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?,是,否,思考,4,：辗转相除法中的关键步骤是哪种逻辑结构？,思考,5:,上述求两个正整数的最大公约数的方法称为,辗转相除法,或,欧几里得算法,.,一般地，用辗转相除法求两个正整数,m,，,n,的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？,第一步，给定两个正整数,m,，,n(m,n).,第二步，计算,m,除以,n,所得的余数,r.,第三步，,m=n,，,n=r.,第四步，若,r=0,，则,m,，,n,的最大公约数等 于,m,；否则，返回第二步,.,思考,5:,该算法的程序框图如何表示？,开始,输入,m,，,n,求,m,除以,n,的余数,r,m=n,n=r,r=0,？,是,输出,m,结束,否,思考,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,结束,否,思考,7:,如果用当型循环结构构造算法，则用辗转相除法求两个正整数,m,，,n,的最大公约数的程序框图和程序分别如何表示？,开始,输入,m,，,n,求,m,除以,n,的余数,r,m=n,n0,？,否,输出,m,结束,是,n=r,INPUT m,，,n,WHILE,n,0,r=m MODn,m=n,n=r,WEND,PRINT m,END,练习,1,：利用辗转相除法求两数,4081,与,20723,的最大公约数,.,(53),20723=40815+318;,4081=31812+265;,318=2651+53;,265=535+0.,知识探究（二）,:,更相减损术,思考,1:,设两个正整数,m,n,，若,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,，,思考,2:,上述求两个正整数的最大公约数的方法称为,更相减损术,.,一般地，用更相减损术求两个正整数,m,，,n,的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？,第一步，给定两个正整数,m,，,n(mn).,第二步，计算,m-n,所得的差,k.,第三步，比较,n,与,k,的大小，其中大者用,m,表 示，小者用,n,表示,.,第四步，若,m=n,，则,m,，,n,的最大公约数等于,m,；否则，返回第二步,.,思考,3:,该算法的程序框图如何表示？,开始,输入,m,，,n,nk,？,m=n,是,输出,m,结束,mn,？,k=m,-,n,是,否,n=k,m=k,否,思考,4:,该程序框图对应的程序如何表述？,INPUT m,，,n,WHILE,m,n,k=m-n,IF n,k THEN,m=n,n=k,ELSE,m=k,END IF,WEND,PRINT m,END,开始,输入,m,，,n,nk,？,m=n,是,输出,m,结束,mn,？,k=m,-,n,是,否,n=k,m=k,否,“,更相减损术,”,在中国古代数学专著,九章算术,中记述为：,可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之,.,INPUT “m,n=“;m,n,IF mn then,m=d,ELSE,m=n,n=d,End if,d=m-n,Wend,d=2k*d,PRINT d,End,理论迁移,例,1,分别用辗转相除法和更相减损术求,168,与,93,的最大公约数,.,辗转相除法：,168=93,1+75,，,93=75,1+18,，,75=18,4+3,，,18=3,6.,更相减损术,:168-93=75,，,93-75=18,，,75-18=57,，,57-18=39,，,39-18=21,，,21-18=3,，,18-3=15,，,15-3=12,，,12-3=9,，,9-3=6,，,6-3=3.,例,2,求,325,，,130,，,270,三个数的最大公约数,.,因为,325=130,2+65,，,130=65,2,，,所以,325,与,130,的最大公约数是,65.,因为,270=65,4+10,，,65=10,6+5,，,10=5,2,，,所以,65,与,270,最大公约数是,5.,故,325,，,130,，,270,三个数的最大公约数是,5.,1.,辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约数,.,小结作业,2.,更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公约数,.,比较辗转相除法与更相减损术的区别,（,1,）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。,（,2,）从结果体现形式来看，辗转相除法体现结果是以相除余数为,0,则得到，而更相减损术则以减数与差相等而得到,小结,作业：,P45,练习：,1.,P48,习题,1.3A,组：,1.,
展开阅读全文