1.3.1算法案例(第一课时)市公开课一等奖省赛课微课金奖PPT课件.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,算 法 案 例,(第一课时),1/18,案例1 辗转相除法与更相减损术,2/18,1.回顾算法三种表述：,自然语言,程序框图,程序语言,（三种逻辑结构）,（五种基本语句）,3/18,2.思索：,小学学过求两个数最大条约数方法？,先用两个公有质因数连续去除，一直除到所得商是互质数为止，然后把全部除数连乘起来.,4/18,1、求两个正整数最大条约数,（1）求25和35最大条约数,（2）求49和63最大条约数,25,（1）,5,5,35,7,49,（2）,7,7,63,9,所以，25和35最大条约数为5,所以，49和63最大条约数为7,2、除了用这种方法外还有没有其它方法？,算出,8256,和,6105,最大条约数.,5/18,辗转相除法（欧几里得算法）,观察用辗转相除法求8251和6105最大条约数过程,第一步,用两数中较大数除以较小数，求得商和余数 8251=61051+2146,结论：,8251和6105条约数就是6105和2146条约数，求8251和6105最大条约数，只要求出6105和2146条约数就能够了。,第二步,对6105和2146重复第一步做法6105=21462+1813同理6105和2146最大条约数也是2146和1813最大条约数。,为什么呢？,思考：从上述的过程你体会到了什么？,6/18,完整过程,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,7/18,辗转相除法是一个重复执行直到余数等于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/18,1、辗转相除法（欧几里得算法）,（1）算理：所谓辗转相除法，就是对于给定两个数，用较大数除以较小数。若余数不为零，则将余数和较小数组成新一对数，继续上面除法，直到大数被小数除尽，则这时较小数就是原来两个数最大条约数。,9/18,（2）算法步骤,第一步：输入两个正整数m,n(mn).,第二步：计算m除以n所得余数r.,第三步：m=n,n=r.,第四步：若r0,则m,n最大条约数等于m；,不然转到第二步.,第五步：输出最大条约数m.,10/18,（3）程序框图,（4）程序,INPUT “m,n=“;m,n,DO,r=m MOD n,m=n,n=r,LOOP UNTIL r=0,PRINT m,END,开始,输入m,n,r=m MOD n,m=n,r=0?,是,否,n=r,输出m,结束,11/18,九章算术更相减损术,算理：,可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。,第一步：,任意给定两个正整数；判断他们是否都是偶数。若是，则用2约简；若不是则执行第二步。,第二步：,以较大数减较小数，接着把所得差与较小数比较，并以大数减小数。继续这个操作，直到所得减数和差相等为止，则这个等数就是所求最大条约数。,12/18,2、更相减损术,（1）算理,：所谓更相减损术，就是对于给定两个数，用较大数减去较小数，然后将差和较小数组成新一对数，再用较大数减去较小数，重复执行此步骤直到差数和较小数相等，此时相等两数便为原来两个数最大条约数。,13/18,（2）算法步骤,第一步：输入两个正整数a,b(ab);,第二步：若a不等于b,则执行第三步；不然转到第五步；,第三步：把a-b差赋予r;,第四步：假如br,那么把b赋给a,把r赋给b;不然把r赋给a，执行第二步；,第五步：输出最大条约数b.,14/18,（3）程序框图,（4）程序,INPUT “a,b=“;a,b,WHILE ab,r=a-b,IF br THEN,a=b,b=r,ELSE,a=r,END IF,WEND,PRINT b,END,开始,输入a,b,a,b?,是,否,输出b,结束,b=r,a=b,r=a-b,r,b?,a=r,否,是,15/18,例3 用更相减损术求98与63最大条约数,解：因为63不是偶数，把98和63以大数减小数，并辗转相减,9863356335283528728721,21721,1477,所以，98和63最大条约数等于7,用更相减损术求两个正数84与72最大条约数,练习：,先约简，再求21与18最大条约数,然后乘以两次约简质因数4,16/18,例3、求324、243、135这三个数最大条约数。,思绪分析：求三个数最大条约数能够先求出两个数最大条约数，第三个数与前两个数最大条约数最大条约数即为所求。,17/18,比较辗转相除法与更相减损术区分,（1）都是求最大条约数方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，尤其当两个数字大小区分较大时计算次数区分较显著。,（2）从结果表达形式来看，辗转相除法表达结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到,小结,18/18,