《2017-2018学年高中数学 第一章 算法初步 1.3 算法案例课件 新人教A版必修3.ppt》由会员分享，可在线阅读，更多相关《2017-2018学年高中数学 第一章 算法初步 1.3 算法案例课件 新人教A版必修3.ppt（73页珍藏版）》请在三一文库上搜索。
1、1.3 算法案例,【自主预习】 主题1:辗转相除法 如何求4 557和1 953的最大公约数? 1.注意到4 557=1 9532+651,那么4 557和1 953的公约数和1 953与651的公约数有什么关系?,提示:显然4 557与1 953的最大公约数也是651的约数同样1 953与651的公约数也是4 557的约数.,2.又1 953=3651+0,因此1 953和651的最大公约数为651.由此可得出4 557和1 953的最大公约数是多少? 提示:4 557和1 953的最大公约数为651.,结合以上的探究总结对辗转相除法的认识 辗转相除法的算法步骤 第一步,给定两个_. 第二步
2、,计算_. 第三步,_. 第四步,_,则m,n的最大公约数等于_; 否则,返回_.,正整数m,n,m除以n所得的余数r,m=n,n=r,若r=0,m,第二步,主题2:更相减损术 1.设两个正整数mn,若m-n=k,则m与n的最大公约数和n与k的最大公约数相等吗? 提示:相等.,2.反复利用上述原理如何求396与216的最大公约数?,提示:由396-216=180, 216-180=36, 180-36=144, 144-36=108, 108-36=72, 72-36=36, 故36是396与216的最大公约数.,总结以上探究归纳对更相减损术的理解: 更相减损术 第一步,任意给定两个_,判断它
3、们是否都是 _.若是,_;若不是,执行_.,正整数,偶数,用2约简,第二步,第二步,以_减去_,接着把所得的 差与较小的数比较,并以_,继续这个操作, 直到_为止,则这个数(等数)或这个数 与约简的数的_就是所求的最大公约数.,较大的数,较小的数,大数减小数,所得的数相等,乘积,主题3:秦九韶算法 1.如何计算多项式f(x)=x5+x4+x3+x2+x+1当x=5时的值呢?统计所做的计算的种类及计算次数分别是什么? 提示:f(5)=55+54+53+52+5+1=3 906.由计算统计可得出共需做10次乘法运算,5次加法运算.,2.若将多项式变形为f(x)=(x+1)x+1)x+1)x+1)x
4、+1统计计算x=5时的计算的种类及计算次数分别是什么? 提示:从里往外计算仅需4次乘法和5次加法运算即可得出结果.,总结以上探究归纳秦九韶算法: 秦九韶算法的步骤 把一个n次多项式f(x)=anxn+an-1xn-1+a1x+a0改写 成如下形式: f(x)=_,(anx+an-1)x+an-2)x+a1)x+a0,求多项式的值时,首先计算_ _,即v1=_,然后_逐层计算一次多 项式的值,即v2=_,v3=_,vn=_, 这样,求n次多项式f(x)的值就转化为求n个一次多项 式的值.,最内层括号内一次多项式,的值,anx+an-1,由内向外,v1x+an-2,v2x+an-3,vn-1x+a
5、0,主题4:进位制 1.常见的进位制有:二进制,七进制,十进制,十二进制,六十进制,它们的基数分别是什么? 提示:它们的基数分别是:2,7,10,12,60.,2.k进制数的组成数字有哪些?如果k=8,那么在八进制中,组成的数字有哪些?组成规律是什么? 提示:k进制数组成的数字有0,1,2,k-1共k个数.在八进制中:基数是8,一共有0,1,2,3,4,5,6,7这八个不同的数字;组成规律是:“满八进一”,如:7+1=10(8).,通过以上探究概括你对进位制的理解: (1)进位制的概念及其表示. 概念:人们为了计数和运算方便而约定的记数系统. 满二进一,就是二进制,满十进一,就是十进制,满k进
6、 一,就是_,k进制的基数是k,因此k进制需要使用 _数字.,k进制,k个,表示:一般地,若k是一个大于1的整数,那么以k为基 数的k进制数可以表示为一串数字连写在一起的形式 _(an,an-1,a1,a0N,0ank,0an-1, ,a1,a0k).,anan-1a1a0(k),(2)进位制之间的转化. k进制的数转化为十进制:若anan-1a1a0(k)表示一个k进制的数,则转化为十进制数为: anan-1a1a0(k)=_.,ankn+an-1kn-1+a1k+a0,非十进制的k进制数a(共有n位)化为十进制数b的算法步骤: 第一步,输入a,k,n的值. 第二步,将b的值初始化为0,i的
7、值初始化为1. 第三步,b=b+aiki-1,i=i+1. 第四步,判断_是否成立,若是,则执行第五步;否则,返回第三步.,in,第五步,输出b的值. 将十进制化为k进制,用_,用k连续去除 十进制数所得的商,直到商为零为止,然后将所得的 余数_,即为相应的k进制数.,除k取余法,倒序写出,【深度思考】 1.结合教材P36例1,你认为更相减损术的一般步骤是什么? 第一步,_. 第二步,_ _.,给定两个正整数m,n,不妨设mn,若m,n都是偶数,则不断用2约简,使它们不,同时是偶数,约简后的两个数仍记为m,n,第三步,_. 第四步,_ _ _.,d=m-n,判断“dn”是否成立,若是,则将n,
8、d中的,较大者记为m,较小者记为n,返回第三步;否则,2kd,(k是约简整数2的个数)为所求的最大公约数,2.结合教材P38例2,你认为利用秦九韶算法求值的一般步骤是什么? 设Pn(x)=anxn+an-1xn-1+a1x+a0,将其改写为 Pn(x)=(anxn-1+an-1xn-2+a1)x+a0=(anxn-2+an-1xn-3+ +a2)x+a1)x+a0)=(anx+an-1)x+an-2)x+ +a1)x+a0.,第一步,_. 第二步,_. 第三步,_. 第四步,_. 第五步,_ _.,输入多项式次数n、最高次项的系数an和x的值,将v的值初始化为an,将i的值初始化为n-1,输入
9、i次项的系数ai,v=vx+ai,i=i-1,判断i是否大于或等于0.若是,则返回第三步;,否则,输出多项式的值v,【预习小测】 1.用更相减损术可求得78与36的最大公约数是( ) A.24 B.18 C.12 D.6 【解析】选D.先用2约简得39,18;然后辗转相减得39-18=21,21-18=3,18-3=15,15-3=12,12-3=9,9-3=6,6-3=3.所以所求的最大公约数为32=6.,2.用辗转相除法求294和84的最大公约数时,需要做除法的次数是 ( ) A.1 B.2 C.3 D.4 【解析】选B.因为294=843+42,84=422,所以选B.,3.以下各数中有
10、可能是五进制数的是 ( ) A.55 B.106 C.732 D.2134 【解析】选D.在5进制数中,所组成的数字为0,1,2,3,4,因此A,B,C不可能是5进制数.,4.用秦九韶算法求多项式f(x)=x5+5x4+10x3+10x2+5x+1. 当x=-2时的值为_ .,【解析】f(x)=x5+5x4+10x3+10x2+5x+1 =(x+5)x+10)x+10)x+5)x+1, 而x=-2,所以有v0=1,v1=v0x+a4=1(-2)+5=3, v2=v1x+a3=3(-2)+10=4,v3=v2x+a2=4(-2)+10=2, v4=v3x+a1=2(-2)+5=1, v5=v4x
11、+a0=1(-2)+1=-1. 故f(-2)=-1. 答案:-1,5.将十进制数30化为二进制数为_. 【解析】 故30(10)=11110(2). 答案:11110(2),6.用秦九韶算法计算多项式f(x)=x6-12x5+60x4-160x3+240x2-192x+64在x=2时的值.(仿照教材P38例2解析过程),【解析】先将多项式f(x)进行改写: f(x)=x6-12x5+60x4-160x3+240x2-192x+64 =(x-12)x+60)x-160)x+240)x-192)x+64. 然后由内向外计算得:,v0=1, v1=v0x+a5=12-12=-10, v2=v1x+a
12、4=-102+60=40, v3=v2x+a3=402-160=-80, v4=v3x+a2=-802+240=80,v5=v4x+a1=802-192=-32, v6=v5x+a0=-322+64=0. 所以当x=2时,多项式的值为0.,【互动探究】 1.在用秦九韶算法计算n次项式在x=x0时的值,至多需要进行几次乘法和加法运算? 提示:n次乘法运算和n次加法运算.,2.7进制中,数3 521中的3,5,2,1各表示什么意思? 提示:3表示3个73,5表示5个72,2表示2个7,1表示1个1.,3.如何进行两个非十进制数之间的转换? 提示:以十进制数作为桥梁,先将一个进制的数转化为十进制数,
13、再将十进制数用除k取余法转化为另一进制的数.,【探究总结】 知识归纳:,注意事项: (1)用更相减损术求两正整数的最大公约数时,若两数为偶数,可先约去2,这时莫忘记求得的相等两数乘以约简的数才是所求最大公约数.,(2)除k取余法的注意点: 要连续除:用k连续去除十进制数及所得的商,直到商为零为止. 倒着写:把各步得到的余数倒写(即从下到上排列)就是相应的k进制数.,【题型探究】 类型一:辗转相除法与更相减损术 【典例1】(1)98,28这两个数的最大公约数为( ) A.17 B.16 C.14 D.8,(2)1 037和425的最大公约数是 ( ) A.51 B.17 C.9 D.3 【解题指
14、南】(1)因两数较小,可采用辗转相除法,也可用更相减损术求解. (2)两数相差较大,用辗转相除法求最大公约数.,【解析】(1)选C.方法一:98=283+14, 28=142,所以98与28的最大公约数为14. 方法二:因为98-28=70,70-28=42, 42-28=14,28-14=14. 所以98与28的最大公约数是14.,(2)选B.因为1 037=4252+187, 425=1872+51, 187=513+34, 51=341+17, 34=172, 即1 037和425的最大公约数是17.,【规律总结】辗转相除法和更相减损术求最大公约数的注意点 (1)辗转相除法是当大数被小数
15、除尽时,结束除法运算,较小的数就是最大公约数. (2)更相减损术是当大数减去小数的差等于小数时停止减法,较小的数就是最大公约数.,【巩固训练】1.两个整数490和910的最大公约数 是 ( ) A.2 B.10 C.30 D.70,【解析】选D.910=9110,490=4910, 因为91=491+42, 49=421+7, 42=76. 所以91与49的最大公约数为7. 故910与490的最大公约数为70.,2.求5 280与12 155的最大公约数. 【解析】12 155=5 2802+1 595, 5 280=1 5953+495, 1 595=4953+110, 495=1104+5
16、5, 110=552. 故12 155与5 280的最大公约数为55.,类型二:秦九韶算法 【典例2】(1)用秦九韶算法计算f(x)=6x5-4x4+x3-2x2-9x,需要加法与乘法的运算次数分别为 ( ) A.5,4 B.5,5 C.4,4 D.4,5 (2)用秦九韶算法计算当x=5时,多项式f(x)=2x4-6x3-5x2+4x-6的值时,v3的值等于_.,【解题指南】(1)利用秦九韶算法写出多项式f(x),可知加法,乘法的次数. (2)利用秦九韶算法由内到外依次计算即可得答案.,【解析】(1)选D.f(x)=(6x-4)x+1)x-2)x-9)x, 所以加法4次,乘法5次. (2)将多
17、项式化成如下形式 f(x)=(2x-6)x-5)x+4)x-6, 由内向外计算:,v0=2, v1=25-6=4, v2=45-5=15, v3=155+4=79. 答案:79,【延伸探究】 1.(改变问法)典例2(2)中条件不变,求f(5). 【解析】v0=2, v1=25-6=4, v2=54-5=15, v3=155+4=79, v4=795-6=389.即f(5)=389.,2.(改变问法)典例2(2)中,求f(5)的过程中有多少次加法,乘法运算? 【解析】由f(x)=(2x-6)x-5)x+4)x-6, 所以有4次乘法运算;4次加法运算.,【规律总结】利用秦九韶算法计算多项式的值的策
18、略 (1)正确地将多项式改写,若在多项式中有几项不存在,可将这些项的系数看成0,即把这些项看成0xn. (2)由内向外逐次计算. (3)每一步计算结果准确,由于下一次计算用到上一次计算的结果,应认真、细致地计算每一步.,【巩固训练】用秦九韶算法计算多项式f(x)=12 +35x-8x2+11x3+6x4+5x5+3x6当x=-4时的值时,v2的值 为_.,【解析】将f(x)变形为f(x)=(3x+5)x+6)x+11)x-8)x+35)x+12, 所以v0=3, v1=3(-4)+5=-7, v2=-7(-4)+6=34. 答案:34,类型三:进位制 【典例3】(1)(2016郑州高二检测)将
19、五进制数444(5)化为四进制数应表示为_. (2)把87化为二进制数,应表示为_.,【解题指南】(1)先将五进制数444(5)转化为十进制,再化为四进制. (2)利用除2取余法求解.,【解析】(1)444(5)=452+451+450=124, 再将十进制数124化为四进制数:,所以124=1330(4),所以444(5)=1330(4). 答案:1330(4),(2) 所以87=1010111(2). 答案:1010111(2),【规律总结】 1.将k进制转化为十进制的方法技巧 (1)先将这个k进制数写成各位上的数字与k的幂的乘积之和的形式,再按照十进制数的运算规则计算出结果.如:anan
20、-1a1a0(k)=ankn+an-1kn-1+a1k1+a0k0.,(2)k的幂的最高次数是该k进制数的位数减去1,然后逐个减少1,最后是零次幂,我们称这种方法为方幂法. 2.将十进制化为k进制的步骤 (1)用k连续去除十进制数及所得的商,直到商为零为止. (2)把各步得到的余数倒写就是相应的k进制数.,【巩固训练】1.(1)把67化为二进制数为 ( ) A.1100001(2) B.1000011(2) C.110000(2) D.1000111(2) (2)将八进制数3726(8),化成十进制数为_ .,【解题指南】(1)利用除2取余法求解. (2)利用八进制数中各个数字的含义求解.,【解析】(1)选B. 所以67=1000011(2).,(2)因为3726(8)=383+782+28+6 =2 006, 所以3726(8)=2 006. 答案:2 006,2.把五进制数1 234(5)转化为十进制数,再把它转化为八进制数.,【解析】1234(5)=153+252+351+450=194(10). 因为 所以1234(5)=194(10)=302(8).,