1140算法案例.ppt
11.4 算算 法法 案案 例例辗转相除法（欧几里得算法）辗转相除法（欧几里得算法）观察求观察求8251和和6105的最大公约数的过程的最大公约数的过程 第一步第一步 用两数中较大的数除以较小的数，求得商和用两数中较大的数除以较小的数，求得商和余数余数 8251=61051+2146结论：结论： 8251和和6105的公约数就是的公约数就是6105和和2146的的公约数，求公约数，求8251和和6105的最大公约数，只要求出的最大公约数，只要求出6105和和2146的公约数就可以了。的公约数就可以了。第二步第二步 对对6105和和2146重复第一步的做法重复第一步的做法6105=21462+1813同理同理6105和和2146的最大公约数也是的最大公约数也是2146和和1813的最大公约数。的最大公约数。 1、求两个正整数的最大公约数、求两个正整数的最大公约数（1）求）求25和和35的最大公约数的最大公约数（2）求）求49和和63的最大公约数的最大公约数2、求、求8251和和6105的最大公约数的最大公约数 25（1） 5535749（2） 77639所以，所以，25和和35的最的最大公约数为大公约数为5所以，所以，49和和63的的最大公约数为最大公约数为7 完整的过程完整的过程8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0显然显然37是是148和和37的最大公约数，也的最大公约数，也就是就是8251和和6105的最大公约数的最大公约数 你能把辗转你能把辗转相除法编成程序相除法编成程序吗？吗？第一步：任意给定两个正整数，大的数记为第一步：任意给定两个正整数，大的数记为m m， 小的记为小的记为n n；第二步：用第二步：用m m除以除以n n，求得余数，求得余数r r；第三步：判断第三步：判断r r是否为是否为0 0，若，若r=0r=0，则输出，则输出n n， 若若r r0 0，则令，则令m=nm=n，n=rn=r，再返回第二步，再返回第二步. . 算法算法 辗转相除法是一个反复执行直到余数等于辗转相除法是一个反复执行直到余数等于0停止的步骤，停止的步骤，这实际上是一个循环结构。这实际上是一个循环结构。程序框图：程序框图：开始开始输入输入m,nr=m MOD nm=nn=rr=0?否否是是输出输出m结束结束程序伪代码：程序伪代码： INUPU m , nDO r=m MOD n m=n n=rLOOP UNTIL r=0PRINT mEND利用辗转相除法求最大公约数的步骤利用辗转相除法求最大公约数的步骤 （1）用较大的数）用较大的数m除以较小的数除以较小的数n得到一个商得到一个商 S0和一个余数和一个余数 R0； （2）若）若 R00，则，则n为为m , n的最大公约数；若的最大公约数；若R00 ,则用除数则用除数n除以余数除以余数R0得到一个商得到一个商S1和一和一个余数个余数 R1 ； （3）若）若 R10,则则 R1为为m,n的最大公约数；若的最大公约数；若 R10，则用除数，则用除数R0除以余数除以余数R1得到一个商得到一个商S2 和和一个余数一个余数R2； 依次计算直至依次计算直至Rn0，此时所得到的，此时所得到的Rn-1即为所求的最大公约数。即为所求的最大公约数。 二分法二分法 用二分法求方程的近似解或函数的零点可以设计用二分法求方程的近似解或函数的零点可以设计程序用计算机来完成程序用计算机来完成例例: 写出用二分法求方程写出用二分法求方程x220的一个正的近似的一个正的近似解解 (误差不超过误差不超过0.005)的算法的算法 【思路点拨思路点拨】令令f(x)x22，确定有解区间，确定有解区间1,2，用二分，用二分法确定符合限制条件的解即可法确定符合限制条件的解即可 解解 : :算法如下：算法如下： S1：令：令f(x)x22，因为，因为 f(1)0，所以令所以令a1，b2，c0.005； S2：取：取x0(a+b)/2； S3：若：若|ab|c，则进入，则进入S4；否则输出；否则输出x0,结结束算法；束算法； S4：若：若f(x0)0，则进入，则进入S5；否则；否则xx0就是就是方程的根，输出方程的根，输出x0，结束算法；，结束算法； S5：若：若f(a)f(x0)0，则解在，则解在x0，b，用，用x0替替换换a；若；若f(x0)f(a)0)0，则解在，则解在 x0 x0，b b ，用，用x0 x0替换替换a a；若；若 f f( (x0 x0) )f f( (a a)0)0，则解在，则解在 a a，x0 x0 ，用，用x0 x0替换替换b b，返回，返回S2S2. . 变式训练变式训练计算多项式计算多项式 f( (x）= =x5 5x4 4x3 3x2 2x当当x = 5的值的值算法算法1：因为因为f(x) =xxxxx所以所以(5)=55555=3125625125255= 3906算法算法2： 先计算的先计算的x2值，然后依次计算值，然后依次计算x2x， （x2x）x，（，（x2x）x）x的值，这样每的值，这样每次都可以利用上一次计算的结果次都可以利用上一次计算的结果. 能否探索更好的算法能否探索更好的算法,来解决任意多来解决任意多项式的求值问题项式的求值问题? 我国南宋时期的数学家我国南宋时期的数学家秦九韶秦九韶（约（约1202126112021261）在他的著作）在他的著作数数书九章书九章中提出了下面的算法：中提出了下面的算法： f(x)=anxn+an-1xn-1+an-2xn-2+a1x+a0.我们可以改写成如下形式我们可以改写成如下形式:f(x)=(anx+an-1)x+an-2)x+a1)x+a0.求多项式的值时求多项式的值时,首先计算最内层括号内一首先计算最内层括号内一次多项式的值次多项式的值,即即 v1=anx+an-1,然后由内向外逐层计算一次多项式的值然后由内向外逐层计算一次多项式的值,即即一般地一般地,对于一个对于一个n次多项式次多项式v2=v1x+an-2, v3=v2x+an-3, ,vn=vn-1x+a0.这样这样,求求n次多项式次多项式f(x)的值就转化为求的值就转化为求n个个一次多项式的值一次多项式的值.这种算法称为这种算法称为秦九韶算法秦九韶算法.应用示例应用示例例例:已知一个已知一个5次多项式为次多项式为 f(x)=5x5+2x4 +3.5x3-2.6x2 +1.7x -0.8, 用秦九韶算法求这个多项式当用秦九韶算法求这个多项式当x=5时时的值的值. 解：根据秦九韶算法，把多项式改写成如下形式：解：根据秦九韶算法，把多项式改写成如下形式： f(x)=(5x+2)x+3.5)x-2.6)x+1.7)x-0.8, 按照从内到外的顺序，依次计算一次多项式当按照从内到外的顺序，依次计算一次多项式当 x=5时的值：时的值： v0=5； v1=55+2=27; v2=275+3.5=138.5; v3=138.55-2.6=689.9; v3=138.55-2.6=689.9; v4=689.95+1.7=3 451.2; v5=3 415.25-0.8=17 255.2; 所以，当所以，当x=5x=5时时, ,多项式的值等于多项式的值等于17255.2.17255.2.v1=anx+an-1,v2=v1x+an-2,v3=v2x+an-3, ,vn=vn-1x+a0.观察上述秦九韶算法中的观察上述秦九韶算法中的n个一次式个一次式,可见可见vk的计算要用到的计算要用到vk-1的值的值. 若令若令v0=an,得得v0=an,vK=vK-1x+an-k(k=1,2,n这是一个在秦九韶算法中反复执行的步这是一个在秦九韶算法中反复执行的步骤骤,因此可用循环结构来实现因此可用循环结构来实现.算法步骤如下：算法步骤如下： 第一步，输入多项式次数第一步，输入多项式次数n n、最高次的系数、最高次的系数a an n和的和的x x的值的值. . 第二步，将第二步，将v v的值初始化为的值初始化为a an n，将，将i i的值初始的值初始化为化为n-1n-1. . 第三步，输入第三步，输入i i次项的系数次项的系数a ai.i. 第四步，第四步，v=vx+av=vx+ai,i,i=i-1.i=i-1. 第五步，判断第五步，判断i i是否大于或等于是否大于或等于0.0.若是，则若是，则返回第三步；否则，输出多项式的值返回第三步；否则，输出多项式的值v. v. 程序框图如下图：程序框图如下图： 程序：程序： INPUT “n=”;n INPUT “an=”;a INPUT “x=”;x v= a i =n-1 WHILE i=0PRINT “i=”; i INPUT “ai=”;a v=v x+a i=i-1WENDPRINT VEND 问题：问题： 画出程序框图画出程序框图,表示用秦九韶算法求表示用秦九韶算法求5次次多项式多项式f(x)=a5x5+a4x4+a3x3+a2x2+a1x+a0,当当x=x0 (x0是任意实数是任意实数)时的值的过程时的值的过程,然后写然后写出程序出程序.否否程序框图程序框图开始开始输入输入a0,a1,a2,a3,a4,a5输入输入x0n5?n=1v=a5v=vx0+a5-nn=n+1输出输出v结束结束是是INPUT a0,a1,a2,a3,a4,a5INPUT x0n=1v=a5WHILE n=5 v=vx0+a5-n n=n+1WENDPRINT vEND程序程序(伪代码伪代码)方法感悟方法感悟 1 1辗转相除法是当大数被小数除尽时，结辗转相除法是当大数被小数除尽时，结束除法运算，较小的数就是最大公约数束除法运算，较小的数就是最大公约数 2 2用秦九韶算法可大大降低乘法的运算次用秦九韶算法可大大降低乘法的运算次数，提高了运算速度用此方法求值，关数，提高了运算速度用此方法求值，关键是正确地将所给多项式改写，然后由内键是正确地将所给多项式改写，然后由内向外计算，由于后项计算需用到前项结果，向外计算，由于后项计算需用到前项结果，故应认真、细心，确保结果的准确性故应认真、细心，确保结果的准确性 三类解题步骤三类解题步骤 辗转相除法辗转相除法 （1）用较大的数）用较大的数m除以较小的数除以较小的数n得到一个商得到一个商 S0和一个余数和一个余数 R0； （2）若）若 R00，则，则n为为m , n的最大公约数；若的最大公约数；若R00 ,则用除数则用除数n除以余数除以余数R0得到一个商得到一个商S1和一和一个余数个余数 R1 ； （3）若）若 R10,则则 R1为为m,n的最大公约数；若的最大公约数；若 R10，则用除数，则用除数R0除以余数除以余数R1得到一个商得到一个商S2 和和一个余数一个余数R2； 依次计算直至依次计算直至Rn0，此时所得到的，此时所得到的Rn-1即为所求的最大公约数。即为所求的最大公约数。 二分法二分法 (1)画草图探索解所在的区间；画草图探索解所在的区间； (2)用二分法求符合限制条件的解；用二分法求符合限制条件的解； (3)编制程序用计算机完成编制程序用计算机完成秦九韶算法秦九韶算法 (1)输入多项式次数输入多项式次数n n、最高次的系数、最高次的系数a an n和的和的x x的值的值. . (2)将将v v的值初始化为的值初始化为a an n，将，将i i的值初始化为的值初始化为n-1n-1. . (3)输入输入i i次项的系数次项的系数a ai.i. (4)v=vx+v=vx+a ai i, ,i i= =i i-1.-1. (5)判断判断i i是否大于或等于是否大于或等于0.0.若是，则返回第三步；若是，则返回第三步；否则，输出多项式的值否则，输出多项式的值v. v.
