学高中数学算法初步算法案例新人教A版必修.pptx
《学高中数学算法初步算法案例新人教A版必修.pptx》由会员分享,可在线阅读,更多相关《学高中数学算法初步算法案例新人教A版必修.pptx(73页珍藏版)》请在咨信网上搜索。
1、1.3算法案例【自主预习自主预习】主题主题1:1:辗转相除法辗转相除法如何求如何求4 5574 557和和1 9531 953的最大公约数的最大公约数?1.1.注意到注意到4 557=1 9532+651,4 557=1 9532+651,那么那么4 5574 557和和1 9531 953的公的公约数和约数和1 9531 953与与651651的公约数有什么关系的公约数有什么关系?提示提示:显然显然4 5574 557与与1 9531 953的最大公约数也是的最大公约数也是651651的约数的约数同样同样1 9531 953与与651651的公约数也是的公约数也是4 5574 557的约数的
2、约数.2.2.又又1 953=3651+0,1 953=3651+0,因此因此1 9531 953和和651651的最大公约数为的最大公约数为651.651.由此可得出由此可得出4 5574 557和和1 9531 953的最大公约数是多少的最大公约数是多少?提示提示:4 5574 557和和1 9531 953的最大公约数为的最大公约数为651.651.结合以上的探究总结对辗转相除法的认识结合以上的探究总结对辗转相除法的认识辗转相除法的算法步骤辗转相除法的算法步骤第一步第一步,给定两个给定两个_._.第二步第二步,计算计算_._.第三步第三步,_.,_.第四步第四步,_,_,则则m,nm,n
3、的最大公约数等于的最大公约数等于_;_;否则否则,返回返回_._.正整数正整数m,nm,nm m除以除以n n所得的余数所得的余数r rm=n,n=rm=n,n=r若若r=0r=0m m第二步第二步主题主题2:2:更相减损术更相减损术1.1.设两个正整数设两个正整数mn,mn,若若m-n=k,m-n=k,则则m m与与n n的最大公约数和的最大公约数和n n与与k k的最大公约数相等吗的最大公约数相等吗?提示提示:相等相等.2.2.反复利用上述原理如何求反复利用上述原理如何求396396与与216216的最大公约数的最大公约数?提示提示:由由396-216=180,396-216=180,21
4、6-180=36,216-180=36,180-36=144,180-36=144,144-36=108,144-36=108,108-36=72,108-36=72,72-36=36,72-36=36,故故3636是是396396与与216216的最大公约数的最大公约数.总结以上探究归纳对更相减损术的理解总结以上探究归纳对更相减损术的理解:更相减损术更相减损术第一步第一步,任意给定两个任意给定两个_,_,判断它们是否都是判断它们是否都是_._.若是若是,_;,_;若不是若不是,执行执行_._.正整数正整数偶数偶数用用2 2约简约简第二步第二步第二步第二步,以以_减去减去_,_,接着把所得的接
5、着把所得的差与较小的数比较差与较小的数比较,并以并以_,_,继续这个操作继续这个操作,直到直到_为止为止,则这个数则这个数(等数等数)或这个数或这个数与约简的数的与约简的数的_就是所求的最大公约数就是所求的最大公约数.较大的数较大的数较小的数较小的数大数减小数大数减小数所得的数相等所得的数相等乘积乘积主题主题3:3:秦九韶算法秦九韶算法1.1.如何计算多项式如何计算多项式f(x)=xf(x)=x5 5+x+x4 4+x+x3 3+x+x2 2+x+1+x+1当当x=5x=5时的值时的值呢呢?统计所做的计算的种类及计算次数分别是什么统计所做的计算的种类及计算次数分别是什么?提示提示:f(5)=5
6、f(5)=55 5+5+54 4+5+53 3+5+52 2+5+1=3 906.+5+1=3 906.由计算统计可得出由计算统计可得出共需做共需做1010次乘法运算次乘法运算,5,5次加法运算次加法运算.2.2.若将多项式变形为若将多项式变形为f(x)=(x+1)x+1)x+1)x+1)x+1f(x)=(x+1)x+1)x+1)x+1)x+1统计计算统计计算x=5x=5时的计算的种类及计算次数分别是什么时的计算的种类及计算次数分别是什么?提示提示:从里往外计算仅需从里往外计算仅需4 4次乘法和次乘法和5 5次加法运算即可得次加法运算即可得出结果出结果.总结以上探究归纳秦九韶算法总结以上探究归
7、纳秦九韶算法:秦九韶算法的步骤秦九韶算法的步骤把一个把一个n n次多项式次多项式f(x)=af(x)=an nx xn n+a+an-1n-1x xn-1n-1+a+a1 1x+ax+a0 0改写改写成如下形式成如下形式:f(x)=_f(x)=_(a(an nx+ax+an-1n-1)x+a)x+an-2n-2)x+)x+a+a1 1)x+a)x+a0 0,求多项式的值时求多项式的值时,首先计算首先计算_,_,即即v v1 1=_,=_,然后然后_逐层计算一次多逐层计算一次多项式的值项式的值,即即v v2 2=_,v=_,v3 3=_,=_,v,vn n=_,=_,这样这样,求求n n次多项式
8、次多项式f(x)f(x)的值就转化为求的值就转化为求n n个一次多项个一次多项式的值式的值.最内层括号内一次多项式最内层括号内一次多项式的值的值a an nx+ax+an-1n-1由内向外由内向外v v1 1x+ax+an-2n-2v v2 2x+ax+an-3n-3v vn-1n-1x+ax+a0 0主题主题4:4:进位制进位制1.1.常见的进位制有常见的进位制有:二进制二进制,七进制七进制,十进制十进制,十二进制十二进制,六十进制六十进制,它们的基数分别是什么它们的基数分别是什么?提示提示:它们的基数分别是它们的基数分别是:2,7,10,12,60.:2,7,10,12,60.2.k2.k
9、进制数的组成数字有哪些进制数的组成数字有哪些?如果如果k=8,k=8,那么在八进制那么在八进制中中,组成的数字有哪些组成的数字有哪些?组成规律是什么组成规律是什么?提示提示:k k进制数组成的数字有进制数组成的数字有0,1,2,0,1,2,k-1,k-1共共k k个数个数.在在八进制中八进制中:基数是基数是8,8,一共有一共有0,1,2,3,4,5,6,70,1,2,3,4,5,6,7这八个不这八个不同的数字同的数字;组成规律是组成规律是:“满八进一满八进一”,如如:7+1=10:7+1=10(8)(8).通过以上探究概括你对进位制的理解通过以上探究概括你对进位制的理解:(1)(1)进位制的概
10、念及其表示进位制的概念及其表示.概念概念:人们为了计数和运算方便而约定的记数系统人们为了计数和运算方便而约定的记数系统.满二进一满二进一,就是二进制就是二进制,满十进一满十进一,就是十进制就是十进制,满满k k进进一一,就是就是_,k_,k进制的基数是进制的基数是k,k,因此因此k k进制需要使用进制需要使用_数字数字.k k进制进制k k个个表示表示:一般地一般地,若若k k是一个大于是一个大于1 1的整数的整数,那么以那么以k k为基为基数的数的k k进制数可以表示为一串数字连写在一起的形式进制数可以表示为一串数字连写在一起的形式_(a_(an n,a,an-1n-1,a,a1 1,a,a
11、0 0N,0aN,0an nk,0ak,0an-1n-1,a,a1 1,a,a0 0k).nin第五步第五步,输出输出b b的值的值.将十进制化为将十进制化为k k进制进制,用用_,_,用用k k连续去除连续去除十进制数所得的商十进制数所得的商,直到商为零为止直到商为零为止,然后将所得的然后将所得的余数余数_,_,即为相应的即为相应的k k进制数进制数.除除k k取余法取余法倒序写出倒序写出【深度思考深度思考】1.1.结合教材结合教材P36P36例例1,1,你认为更相减损术的一般步骤是什你认为更相减损术的一般步骤是什么么?第一步第一步,_.,_.第二步第二步,_,_._.给定两个正整数给定两个
12、正整数m,n,m,n,不妨设不妨设mnmn若若m,nm,n都是偶数都是偶数,则不断用则不断用2 2约简约简,使它们不使它们不同时是偶数同时是偶数,约简后的两个数仍记为约简后的两个数仍记为m,nm,n第三步第三步,_.,_.第四步第四步,_,_._.d=m-nd=m-n判断判断“dndn”是否成立是否成立,若是若是,则将则将n,dn,d中的中的较大者记为较大者记为m,m,较小者记为较小者记为n,n,返回第三步返回第三步;否则否则,2,2k kd d(k(k是约简整数是约简整数2 2的个数的个数)为所求的最大公约数为所求的最大公约数2.2.结合教材结合教材P38P38例例2,2,你认为利用秦九韶算
13、法求值的一般你认为利用秦九韶算法求值的一般步骤是什么步骤是什么?设设P Pn n(x)=a(x)=an nx xn n+a+an-1n-1x xn-1n-1+a+a1 1x+ax+a0 0,将其改写为将其改写为P Pn n(x)=(a(x)=(an nx xn-1n-1+a+an-1n-1x xn-2n-2+a+a1 1)x+a)x+a0 0=(a=(an nx xn-2n-2+a+an-1n-1x xn-3n-3+a+a2 2)x+a)x+a1 1)x+a)x+a0 0)=)=(=(a(an nx+ax+an-1n-1)x+a)x+an-2n-2)x+)x+a+a1 1)x+a)x+a0 0
14、.第一步第一步,_.,_.第二步第二步,_.,_.第三步第三步,_.,_.第四步第四步,_.,_.第五步第五步,_,_._.输入多项式次数输入多项式次数n n、最高次项的系数、最高次项的系数a an n和和x x的值的值将将v v的值初始化为的值初始化为a an n,将将i i的值初始化为的值初始化为n-1n-1输入输入i i次项的系数次项的系数a ai iv=vx+av=vx+ai i,i=i-1,i=i-1判断判断i i是否大于或等于是否大于或等于0.0.若是若是,则返回第三步则返回第三步;否则否则,输出多项式的值输出多项式的值v v【预习小测预习小测】1.1.用更相减损术可求得用更相减损
15、术可求得7878与与3636的最大公约数是的最大公约数是()A.24A.24B.18B.18C.12C.12D.6D.6【解析解析】选选D.D.先用先用2 2约简得约简得39,18;39,18;然后辗转相减得然后辗转相减得39-39-18=21,21-18=3,18-3=15,15-3=12,12-3=9,9-3=6,6-18=21,21-18=3,18-3=15,15-3=12,12-3=9,9-3=6,6-3=3.3=3.所以所求的最大公约数为所以所求的最大公约数为3 32=6.2=6.2.2.用辗转相除法求用辗转相除法求294294和和8484的最大公约数时的最大公约数时,需要做除需要做
16、除法的次数是法的次数是()A.1A.1 B.2 B.2 C.3 C.3 D.4 D.4【解析解析】选选B.B.因为因为294=84294=843+42,84=423+42,84=422,2,所以选所以选B.B.3.3.以下各数中有可能是五进制数的是以下各数中有可能是五进制数的是()A.55A.55 B.106 B.106 C.732 C.732 D.2134 D.2134【解析解析】选选D.D.在在5 5进制数中进制数中,所组成的数字为所组成的数字为0,1,2,3,4,0,1,2,3,4,因此因此A,B,CA,B,C不可能是不可能是5 5进制数进制数.4.4.用秦九韶算法求多项式用秦九韶算法求
17、多项式f(x)=xf(x)=x5 5+5x+5x4 4+10 x+10 x3 3+10 x+10 x2 2+5x+1.+5x+1.当当x=-2x=-2时的值为时的值为_.【解析解析】f(x)=xf(x)=x5 5+5x+5x4 4+10 x+10 x3 3+10 x+10 x2 2+5x+1+5x+1=(x+5)x+10)x+10)x+5)x+1,=(x+5)x+10)x+10)x+5)x+1,而而x=-2,x=-2,所以有所以有v v0 0=1,v=1,v1 1=v=v0 0 x+ax+a4 4=1(-2)+5=3,=1(-2)+5=3,v v2 2=v=v1 1x+ax+a3 3=3(-2
18、)+10=4,=3(-2)+10=4,v v3 3=v=v2 2x+ax+a2 2=4(-2)+10=2,=4(-2)+10=2,v v4 4=v=v3 3x+ax+a1 1=2(-2)+5=1,=2(-2)+5=1,v v5 5=v=v4 4x+ax+a0 0=1(-2)+1=-1.=1(-2)+1=-1.故故f(-2)=-1.f(-2)=-1.答案答案:-1-15.5.将十进制数将十进制数3030化为二进制数为化为二进制数为_._.【解析解析】故故3030(10)(10)=11110=11110(2)(2).答案答案:1111011110(2)(2)6.6.用秦九韶算法计算多项式用秦九韶算
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 高中数学 算法 初步 案例 新人 必修
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【人****来】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【人****来】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。