资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。谢谢,1.3.1 案例1、辗转相除法与更相减损术,第1页,回顾算法三种表示方法：,（1）、自然语言,（2）、程序框图,（3）、程序语言,（三种逻辑结构）,（五种基本语句）,复习引入,第2页,思索：,小学学过求两个数最大条约数方法？,先用两个公有质因数连续去除，一直除到所得商是互为质数为止，然后把全部除数连乘起来.,解：,2,1 8 2 4 用公有质因数,2,除，,3,9 1 2 用公有质因数,3,除，,3 4 3和4互质不除了。,得：18,和,24,最大条约数是：,2,3,6,问题：怎样求,8251,与,6105,最大条约数？,(8251 ,6105 )=?,例、求18与24最大条约数：,第3页,用辗转相除法求8251和6105最大条约数过程,第一步,用两数中较大数除以较小数，求得商和余数,8251=61051+2146,结论：8251和6105条约数就是6105和2146条约数，求8251和6105最大条约数，只要求出6105和2146条约数就能够了。,(8251 ,6105)=(6105 ,2146),第二步,对6105和2146重复第一步做法,6105=21462 +1813,辗转相除法（欧几里得算法）,同理6105和2146最大条约数也是2146和1813最大条约数。,(8251 ,6105)=(6105 ,2146)=(2146 ,1813),以这类推,第4页,完整过程,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：从上面两个例子能够看出计算规律是什么？,第一步：用大数除以小数,第二步：,除数,变成,被除数,，,余数,变成,除数,第三步：重复第一步，直到,余数为0,时,除数,即为最大条约数,第5页,辗转相除法（欧几里得算法）,所谓辗转相除法,就是对于给定两个数,用较大数除以较小数.若余数不为零,则将,除数,变成,被除数,，,余数,变成,除数,继续上面除法,直到余数为0,则这时除数就是原来两个数最大条约数.,练习：利用辗转相除法求两数4081与20723最大条约数,（答案：53）,第6页,辗转相除法是一个重复执行直到余数等于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：辗转相除法中的关键步骤是哪种逻辑结构？,第7页,思索3：,你能把辗转相除法编成一个计算机程序吗？,算法步骤：,第一步：输入两个正整数m,n(mn).,第二步：计算m除以n所得余数r.,第三步：m=n,n=r.,第四步：若r0,则m,n最大条约数等于m；,不然转到第二步.,第五步：输出最大条约数m.,r=m MOD n,m=n,是,否,n=r,开始,输入m,n,r=0?,输出m,结束,程序框图：,INPUT m,n,DO,r=m MOD n,m=n,n=r,LOOP UNTIL r=0,PRINT m,END,程序：,第8页,课后必做作业：,请同学们课后阅读教材，了解并掌握辗转相除法程序设计,第9页,更相减损术,我国早期也有处理求最大条约数问题算法，就是,更相减损术,。,更相减损术求最大条约数步骤以下：,可半者半之，不可半者，副置分母、子之数，,以少减多，更相减损，求其等也，以等数约之。,翻译出来为：,第一步：任意给出两个正数；判断它们是否都是偶数。若是，用,2约简；若不是，执行第二步。,第二步：以较大数减去较小数，接着把所,得差与,较小数,比较，并以大数减小数。继续这个操作，直到所得数,相等为止，则,这个数（等数）或这个数与约简数乘,积,就是所求最大条约数。,第10页,更相减损术,第一步,：任意给出两个正数；判断它们是否都是偶数。若是，用2约简；,若不是，执行第二步。,第二步,：以较大数减去较小数，接着把所得差与较小数比较，,并以大数减小数。继续这个操作，直到所得数相等为止，则,这个数,（等数）或这个数与约简数乘积,就是所求最大条约数。,例,用更相减损术求98与63最大条约数,解：因为两个数不都是偶数，把98和63以大数减小数，并辗转相减,1477,所以，98和63最大条约数等于7,练习：用更相减损术求两个正数84与72最大条约数。,（答案：12）,986335,633528,35287,28721,21714,第11页,（,1,）都是求最大条约数方法，计算上辗转相除法以除法,为主，更相减损术以减法为主，计算次数上辗转相除法计算,次数相对较少，尤其当两个数比较大时更适适用辗转相除法。,（,2,）从结果表达形式来看，辗转相除法表达结果是以相除,余数为,0,而得到，而更相减损术则以减数与差相等而得到。,辗转相除法与更相减损术区分,第12页,用更相减损术求两个正整数m，n最大条约数,算法步骤,(1)输入两个整数m，n,(2)若mn,转到(3),不然转到(4),(3)若mn,则m=m-n,不然n=n-m,转到(2),(4)输出最大条约数n,第13页,用更相减损术求两个正整数m，n最大条约数,程序框图,输入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,第14页,更相减损术算法程序：,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,第15页,（,1,）都是求最大条约数方法，计算上辗转相除法以除法,为主，更相减损术以减法为主，计算次数上辗转相除法计算,次数相对较少，尤其当两个数比较大时更适适用辗转相除法。,（,2,）从结果表达形式来看，辗转相除法表达结果是以相除,余数为,0,而得到，而更相减损术则以减数与差相等而得到。,辗转相除法与更相减损术区分,小 结,第16页,
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
