教育专题：6)算法案例3

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,算法案例,算 法 案 例,辗转相除法和更相减损术,1,、求两个正整数的最大公约数,（,1,）求,18,和,30,的最大公约数,18,和,30,的最大公约数为,6,记,: ( 18 , 30 )=6,求公因数的方法,:,先用两个数公有的质因数连续去除,一直除到所得的商是互质数为止,然后把所有的除数连乘起来,.,2,、,求,8251,和,6105,的最大公约数,( 8251 ,6105 )=?,辗转相除法（欧几里得算法）,观察用辗转相除法求,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),思考：从上述的过程你体会到最后的余数是什么？,完整的过程,333=1482+37,148=374+0,8251=61051+2146,6105=21462+1813,2146=18131+333,1813=3335+148,显然,37,是,148,和,37,的最大,公约数，也就是,8251,和,6105,的最大公约数,例,2,用辗转相除法求,225,和,135,的最大公约数,思考,1,：从上面的两个例子可以概括出,计算的规则？,S1,：用大数除以小数,S3,：重复,S1,，直到余数为,0,S2,：,除数,变成,被除数,，,余数,变成,除数,225=1351+90,135=901+45,90=452+0,显然,45,是,90,和,45,的最大公约数，也就是,225,和,135,的最大公约数,辗转相除法是一个反复执行直到余数等于,0,停止的步骤，这实际上是一个循环结构。,m = n q,r,用程序框图表示出右边的过程,否,思考2：辗转相除法中的关键步骤是哪种逻辑结构？,r=m MOD n,m = n,n = r,r=0?,是,S1,：用大数除以小数,S3,：重复,S1,，直到余数为,0,S2,：,除数,变成,被除数,，,余数,变成,除数,辗转相除法的程序框图,开始,输入,m,n,r=m MOD n,m=n,n=r,r=0?,输出,m,结束,是,否,INPUT “,输入,m,n”; m,n,DO,r=m MOD n,m=n,n=r,LOOP UNTIL r=0,PRINT “,最大公约数是：”；,m,END,九章算术,更相减损术,算理：,可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。,第一步：,任意给定两个正整数；判断他们是否都是偶数。若是，则用,2,约简；若不是则执行第二步。,第二步：,以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数就是所求的最大公约数。,例,3,用更相减损术求,98,与,63,的最大公约数,解：由于,63,不是偶数，把,98,和,63,以大数减小数，并辗转相减,98,63,3563,35,2835,28,728,7,21,21,7,14,14,7,7,所以，,98,和,63,的最大公约数等于,7,练习,2,：用更相减损术求两个正数,84,与,72,的最大公约数。,(12),3.,辗转相除法与更相减损术的比较,:,（,1,）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主,;,计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。,（,2,）从结果体现形式来看，辗转相除法体现结果是以相除余数为,0,则得到，而更相减损术则以减数与差相等而得到,.,计算多项式,（）,=,当,x,= 5,的值,算法,1,：,因为（）,=,所以（,5,）,=5,5,5,5,5,=,3125,625,125,25,5,=,3906,算法,2,：,（,5,）,=5,5,5,5,5,10,次的乘法运算,5,次的加法运算,4,次的乘法运算,5,次的加法运算,=,5,（,5,5,5,5,） ,=,5,（,5,（,5,5,5, ） ） ,=,5,（,5,（,5,（,5,5,） ） ） ,=,5,（,5,（,5,（,5,（,5, ） ） ） ） ,分析：两种算法中各用了几次乘法运算？和几次加法运算？,数书九章,秦九韶算法,设,是一个,n,次的多项式,对该多项式按下面的方式进行改写：,思考：当知道了x的值后该如何求多项式的值？,这是怎样的一种改写方式？最后的结果是什么？,要求多项式的值，应该先算最内层的一次多项式的值，即,然后，由内到外逐层计算一次多项式的值，即,最后的一项是什么？,这种将求一个,n,次多项式,f,（,x,）的值转化成求,n,个一次多项式的值的方法，称为,秦九韶算法,。,思考：在求多项式的值上，这是怎样的一个转化？,例,2,已知一个五次多项式为,用秦九韶算法求这个多项式当,x = 5,的值。,解：,将多项式变形：,按由里到外的顺序，依此计算一次多项式当,x = 5,时的值：,所以，当,x = 5,时，多项式的值等于,17255.2,你从中看到了怎样的规律？怎么用程序框图来描述呢？,开始,输入,n,a,n,x,V=,a,n,i=n-1,i=0?,输出,v,结束,输入,a,i,V=,v,*x+,a,i,i=i-1,是,否,例,3,已知一个,4,次多项式为,用秦九韶算法求这个多项式当,x = 5,的值。,解：,将多项式变形：,按由里到外的顺序，依此计算一次多项式当,x = 5,时的值：,练习,画出程序框图,表示用秦九韶算法求,5,次多项式,f(x)=a,5,x,5,+a,4,x,4,+a,3,x,3,+a,2,x,2,+a,1,x+a,0,当,x=x,0,(x,0,是任意实数,),时的值的过程,然后写出程序,.,否,程序框图,开始,输入,a,0,a,1,a,2,a,3,a,4,a,5,输入,x,0,n5?,n=1,v=a,5,v=vx,0,+a,5-n,n=n+1,输出,v,结束,是,INPUT a,0, a,1, a,2, a,3, a,4, a,5,INPUT,x,0,n=1,v= a,5,WHILE n=5,v=vx,0,+a,5-n,n=n+1,WEND,PRINT,v,END,程序,一、进位制,1,、最常见的进位制是什么？,2,、除此之外还有哪些常见的进位制？请举例说明,进位制是人们为了计数和运算方便而约定的记数系统。,1,、我们了解十进制吗？所谓的十进制，它是如何构成的？,十进制由两个部分构成,例如：,3721,其它进位制的数又是如何的呢？,第二、它有,“权位”,，即,从右往左,为个位、十位、百位、千位等等。,表示有：,1,个,1,，,2,个十，,7,个百即,7,个,10,的平方，,3,个千即,3,个,10,的立方,第一、它有,0,、,1,、,2,、,3,、,4,、,5,、,6,、,7,、,8,、,9,十个数字；,(,用,10,个数字来记数，称基数为,10),2,、 二进制,二进制是用,0,、,1,两个数字来描述的。如,11001,等,（）二进制的表示方法,区分的写法：,11001,（,2,）,8,进制呢？,k,进制呢？,a,n,a,n-1,a,n-2,a,2,a,1(k),？,如,7342,(8),二、二进制与十进制的转换,1,、二进制数转化为十进制数,例,1,将二进制数,110011,(2),化成十进制数,解：,根据进位制的定义可知,所以，,110011,（,2,）,=51,。,2,、十进制转换为二进制,解：,根据“逢二进一”的原则，有,5,2,2,1,2,（,2,（,2,（,2,（,2,2,1,）,1,）,0,）,0,）,1,89,12,6,02,5,12,4,12,3,02,2,02,1,12,0,所以：,89=1011001,（,2,）,2,（,2,（,2,（,2,3,2,1,）,0,）,0,）,1,2,（,2,（,2,4,2,2,2,0,）,0,）,1,2,（,2,5,2,3,+2,2,0,0,）,1,2,6,2,4,+2,3,0,0,2,0,89,2,44,1,44,2,22,0,22,2,11,0,11,2,5,1,所以,89,2,（,2,（,2,（,2,（,2 2,1,）,1,）,0,）,0,）,1,例,2,把,89,化为二进制数,2,、十进制转换为二进制,例,2,把,89,化为二进制数,5,2,2,2,1,2,11,22,44,89,2,2,2,2,注意：,1.,最后一步商为,0,，,2.,将上式各步所得的余数,从下到上排列,，得到：,89=1011001,（,2,）,0,1,0,余数,0,1,1,0,1,例,3,把,89,化为五进制数,3,、十进制转换为其它进制,解：,根据,除,k,取余法,以,5,作为除数，相应的除法算式为：,所以，,89=324,（,5,）,。,89,5,17,5,3,5,0,4,2,3,余数,将,k,进制数,a,转换为十进制数,b,的程序,a=a,n,a,n-,1, a,3,a,2,a,1(,k,),=,a,n,k,(,n,-,1),+a,n,-,1,k,(,n,-,2),+ + a,3,k,2,+a,2,k,1,+,a,1,k,0,b=a,1,k,0,b=a,2,k,1,+b,b=a,3,k,2,+,b,b=a,n,k,n-1,+b,a,i,=GET ai,GET,函数用于取出,a,的右数第,i,位数,i=1,i=i+1,b=a,i,k,i-1,+b,INPUT,a,k,n,i=1,b=0,WHILE i=n,t=GET ai,b=t*k,(i-1)+b,i=i+1,WEND,PRINT b,END,例,.,设计一个程序,把任意的十进制,a,转化为,k,进制数,b.,开始,输入,a,k,求,a,除以,k,的商,q,求,a,除以,k,的余数,r,把得到的余数依次从右到左排列,a=q,q=0,输出全部余数排列得到的进制数,结束,是,否,“，”,；,练习：,完成下列进位制之间的转化：,（,1,）,10231,（,4,）,=,（,10,）,；,（,2,）,235,（,7,）,=,（,10,）,；,（,3,）,137,（,10,）,=,（,6,）,；,（,4,）,1231,（,5,）,=,（,7,）,；,（,5,）,213,（,4,）,=,（,3,）,；,（,6,）,1010111,（,2,）,=,（,4,）,。,301,124,345,362,1110,1113,