ImageVerifierCode 换一换
格式:PPT , 页数:28 ,大小:448.50KB ,
文档编号:5877063      下载积分:20 文币
快捷下载
登录下载
邮箱/手机:
温馨提示:
系统将以此处填写的邮箱或者手机号生成账号和密码,方便再次下载。 如填写123,账号和密码都是123。
支付方式: 支付宝    微信支付   
验证码:   换一换

优惠套餐
 

温馨提示:若手机下载失败,请复制以下地址【https://www.163wenku.com/d-5877063.html】到电脑浏览器->登陆(账号密码均为手机号或邮箱;不要扫码登陆)->重新下载(不再收费)。

已注册用户请登录:
账号:
密码:
验证码:   换一换
  忘记密码?
三方登录: 微信登录  
下载须知

1: 试题类文档的标题没说有答案,则无答案;主观题也可能无答案。PPT的音视频可能无法播放。 请谨慎下单,一旦售出,概不退换。
2: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。
3: 本文为用户(ziliao2023)主动上传,所有收益归该用户。163文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 本站仅提供交流平台,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

版权提示 | 免责声明

1,本文(算法案例(辗转相除法)课件.ppt)为本站会员(ziliao2023)主动上传,163文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。
2,用户下载本文档,所消耗的文币(积分)将全额增加到上传者的账号。
3, 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(发送邮件至3464097650@qq.com或直接QQ联系客服),我们立即给予删除!

算法案例(辗转相除法)课件.ppt

1、1.3算法案例(第1课时)案例1 辗转相除法最大公约数的定义1、运用的范围:给出两个正整数m,n求它们的最大公约数。2、最大公约数分两种情况:第一种情况:如果这两个数存在倍数关系(即较大数是较小数 的倍数)则较小数就是这两个数的最大公约数。例如:12与6的最大公约数就为6,36与18的最大公约数就是为18第二种情况:这两个数不存在倍数关系则用短除法求之短除法:一般先用这两个数公有的质因数连续去除,一直除到所得的商是互质数为止,然后把所有的除数连乘起来,在除的过程中,有时也可以用两个数的公约数去除。问题2:你又能求出8251与6105的最大公约数吗?问题1:你能求出204与85的最大公约数吗?3

2、0=181+1230与18的最大公约数相当于18与12的最大公约数18=121+618与12的最大公约数相当于12与6的最大公约数12=62+012与6的最大公约数为:6所以,30与18的最大公约数为:6算法1 辗转相除法被除数=除数商+余数所以,17为204与85的最大公约数。20485234853421734172+0问题1、用辗转相除法求两个正数a=204和b=85的最大公约数。204与85的最大公约数相当于85与34的最大公约数85与34的最大公约数相当于34与17的最大公约数34与17的最大公约数为:17解:被除数=除数商+余数解:8251=61051+2146 6105=21462

3、+1813 2146=18131+333 1813=3335+148 333=1482+37 148=374+0所以,8251与6105的最大公约数为:37问题2、用辗转相除法求出8251与6105的最大公约数。运用辗转相除法求下列两个数的最大公约数 例2.求225和135的最大公约数例1.求196和147的最大公约数 例2求225和135的最大公约数 2、解:225=1351+90135=901+45 90=452+0所以,225与135的最大公约数为:45例1求196和147的最大公约数 1、解:196=1471+49147=493+0所以,196与147的最大公约数为:49被除数=除数商

4、+余数第一步:m=nq0+r0第二步:n=r0q1+r1第三步:r0=r1q2+r2第四步:r1=r2q3+r3第五步:r2=r3q4+r4第六步:r3=r4q5+r5第n+1步:rn-2=rn-1qn+rn依次计算直至依次计算直至rn0,此时所得到的除数,此时所得到的除数rn1即为所求的即为所求的最大公约数。最大公约数。辗转相除法的基本步骤:(用qi表示商,ri表示余数)被除数=除数商+余数 8251=61051+2146 6105=21462+1813 2146=18131+333 1813=3335+148 148=374+0所以,8251与6105的最大公约数为:37算法步骤:第一步:

5、给定两个正整数m,n;第二步:计算m除以n所得的余数r;第三步:m=n,n=r;第四步:若r=0,则m,n的最大公约数等于m;否则,返回第二步。程序框图:开始开始输入m,n求m除以n的余数rm=nn=rr=0?结束结束输入m是否程序:INPUT m,nDO r=m MOD n m=n n=rLOOP UNTIL r=0 PRINT mEND欧几里得辗转相除法找出a,b的最大公约数的步骤是:(1)计算ab的余数r,若r=0,则b为a,b的最大公约数;(2)若r0,则把前面的除数b作为新的被除数,把r作为新的除数,继续运算,直到余数为0,此时的除数即为a,b的最大公约数.算算 法法 案案 例例第二

6、课时1、求两个数的最大公约数的两种方法分别是、求两个数的最大公约数的两种方法分别是()和()和()。)。2、两个数、两个数21672,8127的最大公约数是的最大公约数是 ()A、2709 B、2606 C、2703 D、2706复习引入:新课讲解:怎样求多项式怎样求多项式f(x)=xf(x)=x5 5+x+x4 4+x+x3 3+x+x2 2+x+1+x+1当当x=5x=5时的值呢?时的值呢?计算多项式计算多项式()=当当x=5的值的算法:的值的算法:算法算法1:因为因为()=所以所以(5)=55555=3125625125255=3906算法算法2:(5)=55555=5(5555)=5(

7、5(555 )=5(5(5(5+5+)+)+)+=5(5(5(5(5+)+)+)+)+算法算法1:因为因为()=所以所以(5)=55555=3125625125255=3906算法算法2:(5)=55555=5(5555)=5(5(555 )=5(5(5(5+5+)+)+)+=5(5(5(5(5+)+)+)+)+共做了共做了1+2+3+4=10次乘法运算,次乘法运算,5次加法运算。次加法运算。共做了共做了4次乘法运算,次乘法运算,5次加法运算。次加法运算。数书九章数书九章秦九韶算法秦九韶算法0111)(axaxaxaxfnnnn设设)(xf是一个是一个n 次的多项式次的多项式对该多项式按下面的

8、方式进行改写:对该多项式按下面的方式进行改写:0111)(axaxaxaxfnnnn01211)(axaxaxannnn012312)(axaxaxaxannnn0121)(axaxaxaxannn这是怎样的一种改写方式?最后的结果是什么?0121)()(axaxaxaxaxfnnn要求多项式的值,应该先算最内层的一次多项式的值,即要求多项式的值,应该先算最内层的一次多项式的值,即11nnaxav然后,由内到外逐层计算一次多项式的值,即然后,由内到外逐层计算一次多项式的值,即212naxvv323naxvv01axvvnn最后的一最后的一项是什么?项是什么?这种将求一个这种将求一个n次多项式次

9、多项式f(x)的值转化成求的值转化成求n个一个一次多项式的值的方法,称为次多项式的值的方法,称为秦九韶算法秦九韶算法。通过一次式的反复计算,逐步得出高次多通过一次式的反复计算,逐步得出高次多项式的值,对于一个项式的值,对于一个n次多项式,只需做次多项式,只需做n次乘次乘法和法和n次加法即可。次加法即可。秦九韶算法的特点:秦九韶算法的特点:例:例:已知一个五次多项式为已知一个五次多项式为8.07.16.25.325)(2345xxxxxxf用秦九韶算法求这个多项式当用秦九韶算法求这个多项式当x=5的值。的值。解:解:将多项式变形:将多项式变形:8.0)7.1)6.2)5.3)25()(xxxxx

10、xf按由里到外的顺序,依此计算一次多项式当按由里到外的顺序,依此计算一次多项式当x=5时的值:时的值:272551v50v5.1385.35272v9.6896.255.1383v2.34517.159.6894v2.172558.052.34515v所以,当所以,当x=5时,多项式的值等于时,多项式的值等于17255.2你从中看到了怎样的规律?怎么用程序框图来描述呢?程序框图:开始输入f(x)的系数:a0,a1,a2,a3,a4a5输入x0n5?输出v结束v=vx0+a5-nn=n+1YN n=1 v=a5 ),(nkaxvvavknkkn2110这是一个在这是一个在秦九韶算法秦九韶算法中反

11、复执行的步骤,因中反复执行的步骤,因此可用循环结构来实现。此可用循环结构来实现。另解:(秦九韶算法的另一种直观算法)5 2 3.5 -2.6 1.7 -0.8 X5 27 138.5 689.9 3451.2 17255.2+多项式的系数多项式的值25 135 692.5 3449.5 1725605(1)、算法步骤:、算法步骤:第一步:输入多项式次数第一步:输入多项式次数n、最高次项的系数、最高次项的系数an和和x的值的值.第二步:将第二步:将v的值初始化为的值初始化为an,将,将i的值初始化为的值初始化为n-1.第三步:输入第三步:输入i次项的系数次项的系数an.第四步:第四步:v=vx+

12、ai,i=i-1.第五步:判断第五步:判断i是否大于或等于是否大于或等于0,若是,则返回第,若是,则返回第三步;否则,输出多项式的值三步;否则,输出多项式的值v。思考:你能设计程序把“秦九韶算法”表示出来吗?(2)程序框图:)程序框图:输入输入ai开始开始输入输入n,an,xi=0?输出输出v结束结束v=vx+aii=i-1YNi=n-1V=an(3)程序:)程序:INPUT “n=”;nINPUT“an=“;aINPUT“x=“;xv=ai=n-1WHILE i=0 PRINT“i=“;i INPUT“ai=“;a v=v*x+a i=i-1WENDPRINT vEND1、已知多项式、已知多项式f(x)=x5+5x4+10 x3+10 x2+5x+1用用秦九韶算法求这个多项式当秦九韶算法求这个多项式当x=-2时的值。时的值。练习:2、已知多项式、已知多项式f(x)=2x4-6x3-5x2+4x-6用用秦九韶算法求这个多项式当秦九韶算法求这个多项式当x=5时的值。时的值。课堂小结:课堂小结:1、秦九韶算法的方法和步骤、秦九韶算法的方法和步骤2、秦九韶算法的程序框图、秦九韶算法的程序框图

侵权处理QQ:3464097650--上传资料QQ:3464097650

【声明】本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是网络空间服务平台,本站所有原创文档下载所得归上传人所有,如您发现上传作品侵犯了您的版权,请立刻联系我们并提供证据,我们将在3个工作日内予以改正。


163文库-Www.163Wenku.Com |网站地图|