6)算法案例3.ppt

1、算法案例,算 法 案 例 辗转相除法和更相减损术,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和61

2、05的最大公约数，只要求出6105和2146的公约数就可以了。 (8251 , 6105 )=(6105 , 2146 ),第二步 对6105和2146重复第一步的做法6105=21462 + 1813同理6105和2146的最大公约数也是2146和1813的最大公约数。 (8251 , 6105 )=(6105 , 2146 ) =(2146 ,1813),思考：从上述的过程你体会到最后的余数是什么？,显然37是148和37的最大 公约数，也就是8251和 6105的最大公约数,例2 用辗转相除法求225和135的最大公约数,思考1：从上面的两个例子可以概括出 计算的规则？,辗转相除法是一个

3、反复执行直到余数等于0停止的步骤，这实际上是一个循环结构。,m = n q r,用程序框图表示出右边的过程,否,思考2：辗转相除法中的关键步骤是哪种逻辑结构？,r=m MOD n,m = n,n = r,r=0?,是,辗转相除法的程序框图,r=m MOD n,是,否,九章算术更相减损术,算理：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。,第一步：任意给定两个正整数；判断他们是否都是偶数。若是，则用2约简；若不是则执行第二步。,第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止，则这个等数就是

4、所求的最大公约数。,例3 用更相减损术求98与63的最大公约数,解：由于63不是偶数，把98和63以大数减小数，并辗转相减,9863356335283528728721 21714 1477,所以，98和63的最大公约数等于7,练习2：用更相减损术求两个正数84与72的最大公约数。,(12),3.辗转相除法与更相减损术的比较:,（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主;计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。 （2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得

5、到.,计算多项式（） =当x = 5的值,算法1：,因为（） =,所以（5）=55555,=3125625125255,= 3906,算法2：,（5）=55555,10次的乘法运算,5次的加法运算,4次的乘法运算,5次的加法运算,=5（5555） ,=5（5（555 ） ） ,=5（5（ 5 （55 ） ） ） ,=5（5（ 5 （5 （5 ） ） ） ） ,分析：两种算法中各用了几次乘法运算？和几次加法运算？,数书九章秦九韶算法,对该多项式按下面的方式进行改写：,思考：当知道了x的值后该如何求多项式的值？,这是怎样的一种改写方式？最后的结果是什么？,要求多项式的值，应该先算最内层的一次多项式

6、的值，即,然后，由内到外逐层计算一次多项式的值，即,最后的一项是什么？,这种将求一个n次多项式f（x）的值转化成求n个一次多项式的值的方法，称为秦九韶算法。,思考：在求多项式的值上，这是怎样的一个转化？,例2 已知一个五次多项式为,用秦九韶算法求这个多项式当x = 5的值。,解：,将多项式变形：,按由里到外的顺序，依此计算一次多项式当x = 5时的值：,所以，当x = 5时，多项式的值等于17255.2,你从中看到了怎样的规律？怎么用程序框图来描述呢？,开始,输入n,an,x,V=an,i=n-1,i=0?,输出v,结束,输入ai,V=v*x+ ai,i=i-1,是,否,例3 已知一个4次多项

7、式为,用秦九韶算法求这个多项式当x = 5的值。,解：,将多项式变形：,按由里到外的顺序，依此计算一次多项式当x = 5时的值：,练习画出程序框图,表示用秦九韶算法求5次多项式f(x)=a5x5+a4x4+a3x3+a2x2+a1x+a0当x=x0 (x0是任意实数)时的值的过程,然后写出程序.,否,程序框图,开始,输入a0,a1,a2,a3,a4,a5,输入x0,n5?,n=1,v=a5,v=vx0+a5-n,n=n+1,输出v,结束,是,程序,一、进位制,1、最常见的进位制是什么？,2、除此之外还有哪些常见的进位制？请举例说明,进位制是人们为了计数和运算方便而约定的记数系统。,1、我们了解

8、十进制吗？所谓的十进制，它是如何构成的？,十进制由两个部分构成,例如：3721,其它进位制的数又是如何的呢？,第二、它有“权位”，即从右往左为个位、十位、百位、千位等等。,表示有：1个1，2个十， 7个百即7个10的平方， 3个千即3个10的立方,2、 二进制,二进制是用0、1两个数字来描述的。如11001等,（）二进制的表示方法,区分的写法：11001（2）,8进制呢？,k进制呢？,anan-1an-2a2a1(k)？,如7342(8),二、二进制与十进制的转换,1、二进制数转化为十进制数,例1 将二进制数110011(2)化成十进制数,解：,根据进位制的定义可知,所以，110011（2）=

9、51。,2、十进制转换为二进制,解：,根据“逢二进一”的原则，有,52 21,2（2（2（2（221）1）0）0）1,89126025124123022021120,所以：89=1011001（2）,2（2（2（2321）0）0）1,2（2（242220）0）1,2（2523+2200）1,2624+230020,892441,442220,222110,112 51,所以892（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