《2018-2019学年高中数学人教a版必修3课件：1.3算法案例 》由会员分享，可在线阅读，更多相关《2018-2019学年高中数学人教a版必修3课件：1.3算法案例 （74页珍藏版）》请在金锄头文库上搜索。
1、1.3 算 法 案 例,1.辗转相除法与更相减损术 （1）辗转相除法： 辗转相除法：又叫_算法，是一种求两个 正整数的_的古老有效的算法.,欧几里得,最大公约数,程序,m MOD n,(2)更相减损术： 我国古代数学专著九章算术中介绍的一种求 两个正整数的_的算法.,最大公约数,运算过程 第一步，任意给定两个正整数，判断它们是否都是 偶数，若是，_；若不是，执行第二步. 第二步，以较大的数减去较小的数，接着把所得的 差与_比较，并以大数减小数.继续这个操作， 直到所得的数_为止，则这个数（等数）或这个数 与约简的数的乘积就是所求的最大公约数.,用2约简,较小的数,相等,2.秦九韶算法,n个一,
2、次多项式,3.进位制及进位制之间的互化 (1)进位制： 概念：进位制是为了_而约定的 记数系统，“满几进一”就是几进制. 基数：几进制的基数就是_.,计数和运算方便,几,(2)不同进位制之间的互化： k进制化为十进制的方法: anan-1a1a0(k)=_ （an，an-1，,a1，a0N,0ank，0an-1， a1，a0k). 十进制化为k进制的方法_.,ankn+an-1kn-1+a1k+a0,除k取余法,【点拨】 （1）辗转相除法的原理 设m，n是两个正整数(不妨设mn)， 用m除以n，若商为q1，余数为r1(0r1n)，则mnq1r1，显然若x是m和n的公约数，即x能整除m和n，则x
3、也必然能整除r1，这样x也是n和r1的公约数，故求m和n的公约数就是求n和r1的公约数;,用n除以r1，得nr1q2r2(0r2r1)，所以n和 r1的公约数就是r1和r2的公约数，依次下去，由于 mnr1r2，所以到某一步必然有riri1 qi2，即ri恰能被ri1整除，这时ri1是ri和ri1的公 约数，它也必然是ri1和ri，ri2和ri1，r1与 r2，n和r1，m和n的最大公约数.,（2）秦九韶算法的计数原理 秦九韶算法是按照从内到外的顺序依次计算求值的.,则该算法先计算v1anxan1，再计算 v2v1xan2，最后计算vnvn1xa0.,【自我检测】 1.下列有关辗转相除法的说法
4、正确的是（ ） A它和更相减损术一样是求多项式值的一种方法 B基本步骤是用较大的数m除以较小的数n得到除式mnqr，直至rn为止,C基本步骤是用较大的数m除以较小的数n得到除式mqnr(0rn)反复进行，直到r0为止 D以上说法均不正确,【解析】选C.根据辗转相除法求最大公约数的方法可知C正确.,2.用更相减损术可求得78与36的最大公约数是( ) A.3 B.4 C.6 D.12,【解析】选C.78=392,36=182, 39-18=21,21-18=3, 18-3=15,15-3=12, 12-3=9,9-3=6, 6-3=3, 因此最大公约数为23=6.,3.用秦九韶算法求多项式f（x
5、）=x4-5x2+9x+150在 x=-1时，v2的值为（ ） A-4 B1 C17 D22 【解析】选A.f（x）=x4-5x2+9x+150 =（x+0)x-5)x+9)x+150, v0=1，v1=-1，v2=（-1）2-5=-4,4将二进制数1 101(2)化为十进制数为. 【解析】本题考查二进制与十进制的相互转化. 1 101(2)123122021113. 答案：13,类型一 求最大公约数 【典例】1.用更相减损术求48和132的最大公约数时，需做减法的次数是（ ） A2 B3 C4 D5,2.（2018太原高一检测）执行如图所示的程序，若输入的m=98，n=63，则输出的m=_,
6、3.(2018阳泉高一检测)分别用辗转相除法、更相减损术求204与85的最大公约数.,【审题路线图】1.利用更相减损术求出最大公约数时的次数逐步运行计算次数. 2.UNTIL语句编写的程序程序运行后是用辗转相除法求输入的m，n的最大公约数的问题，从而求出输出的m值 3.用两种方法求最大公约数按两种方法分别求最大公约数.,【解析】1.选D.因为48和132都是偶数，所以先同时除以4，即取12与33的最大公约数再乘以4为所求，需要做以下减法 33-12=21, 21-12=9,12-9=3, 9-3=6, 6-3=3, 共5次.,2.执行程序，是用辗转相除法求输入的m，n的最大公约数的应用问题，当
7、m=98，n=63时，输出m=7 答案：7,3.(1)用辗转相除法求204与85的最大公约数. 204852+34， 85342+17， 34172， 因此，204与85的最大公约数是17.,(2)用更相减损术求204与85的最大公约数. 由于204和85不都是偶数，所以 204-85119， 119-8534， 85-3451，,51-3417， 34-1717， 因此，204与85的最大公约数是17.,【方法技巧】 1.辗转相除法的算法步骤 第一步，输入两个正整数m,n(mn). 第二步，计算m除以n所得的余数r. 第三步，m=n,n=r.,第四步，若r0,则m,n的最大公约数等于m. 否
8、则，返回第二步. 第五步，输出最大公约数m.,2.更相减损术的算法步骤 第一步，给定两个正整数m，n(mn且m，n不全是偶数). 第二步，计算m-n所得的差k.,第三步，比较n与k的大小，其中大者用m表示，小者用n表示. 第四步，若m=n，则m，n的最大公约数等于m；否则，返回第二步.,【拓展提升】更相减损术与辗转相除法的区别与联系,【变式训练】1.（2018衡水高一检测）用辗转相 除法求480和288的最大公约数时，需要做除法的次 数是（ ） A.2 B.3 C.4 D.5,【解析】选B.用辗转相除法求最大公约数 480=2881+192， 288=1921+96， 192=962， 此时相
9、除余数为0，得到最大公约数为96，共进行了三次除法,2.（2018石家庄高一检测）用辗转相除法或更相减损术求得459与357的最大公约数是_.,【解析】辗转相除法: 因为459=3571+102,357=1023+51,102=512,故459和357的最大公约数是51. 答案：51,【补偿训练】用更相减损术求612与468的最大公 约数.,【解析】首先612和468都是偶数，所以用2约简：得到306和234.因此需要再用2约简，得到153和117，最后用更相减损术计算得： 153-11736， 117-3681，,81-3645， 45-369， 36-927， 27-918， 18-99，
10、 所以612和468的最大公约数是92236.,类型二 秦九韶算法的应用 【典例】1.（2018南充高一检测）秦九韶是我国古 代数学家的杰出代表之一，他的数学九章概括了 宋元时期中国传统数学的主要成就由他提出的一种 多项式简化算法称为秦九韶算法：它是一种将n次多项 式的求值问题转化为n个一次式的算法即使在现代，,利用计算机解决多项式的求值问题时，秦九韶算法依然是最优的算法用秦九韶算法求多项式f（x）=4x5-x2+2，当x=3时的值时，需要进行的乘法运算和加法运算的次数分别为（ ） A4，2 B5，2 C5，3 D6，2,2.(2018衡水高一检测)利用秦九韶算法分别计算 f(x)8x7+5x
11、6+3x4+2x+1在x2与x-1时的值， 并判断f(x)在区间-1,2有没有零点.,【审题路线图】1.用秦九韶算法求值先改写多项式的形式，再逐步计算. 2.判断f(x)在区间-1,2有没有零点分别计算f(2)和f(-1)验证f(2)f(-1)是否小于0.,【解析】1.选B.因为f（x）=（4x）x）x-1）x）x +2，所以乘法要运算5次，加法要运算2次,2.因为f(x)8x7+5x6+3x4+2x+1 (8x+5)x+0)x+3)x+0)x+0)x+2)x+1， 且x2， 所以v08， v182+521， v2212+042，,v3422+387， v4872+0174， v51742+0
12、348， v63482+2698， v76982+11 397.,所以当x2时，f(x)1 397. 同理可求当x-1时，f(x)-1， 又因为f(-1)f(2)-1 3970，则f(x)在区间-1,2上有零点.,【延伸探究】将本例1中的多项式改为f(x)3x62x54x45x37x28x1，需做乘法和加法的次数分别是多少？ 【解析】将多项式改写为f(x)(3x2)x4)x5)x7)x8)x1，化为6个一次因式求解，故只做了6次乘法和6次加法,【方法技巧】秦九韶算法的步骤 提醒：判断算法是否先进的一个重要标志就是运算的次数越少越好.,【补偿训练】用秦九韶算法计算f(x)2x43x35x 4在x
13、2时的值,【解析】f(x)改写为f(x)(2x3)x0)x5)x4， 所以v02， v12237， v272014， v3142533， v4332462，所以f(2)62.,类型三 进位制及其转化 【典例】1.已知一个k进制的数123与十进制的数38相等，那么k等于（ ） A7或5 B7 C5 D都不对 2.三进制数2 022(3)化为六进制数为abc(6)， 则abc_.,3.（2018周口高一检测）十六进制是逢16进1的计数制，采用数字09和字母AF共16个计数符号，这些符号与十进制数的对应关系如表：,例如，用十六进制表示：E+D1B(16)，则AE用十六 进制表示为_.,【审题路线图】
14、多种进位制之间的换算k进制的定义和除k取余法的应用.,【解析】1.选C.(123)(k)1k22k3 k22k3， 所以k22k338，即k22k350. 解得k5或k7(舍去),2.2 022(3)23303223123062. 三进制数2 022(3)化为六进制数为142(6)， 所以abc7. 答案：7,3.AE用十进制可以表示为1014140， 而14016812，所以用十六进制表示为8C(16). 答案：8C（16）,【延伸探究】 1.在本例3条件下，计算 (2F1)4. 【解析】(2F1)4用十进制可以表示为(2151)4124，而12416712，所以用十六进制表示为7C(16).,2.将本例3中对应关系表的后四列去掉，即十二进制，试在十二进制中运算AB. 【解析】AB用十进制可以表示为1011110，而1101292，所以用十二进制表示为92（12）.,【方法技巧】十进制数转化为其他进制数的方法步骤,【补偿训练】1.将51化为二进制数得 【解析】 答案：110 011(2),2.（2018平顶山高一检测）进制转换：2 017（8）= _（9）. 【解题指南】先将八进制的数转换为十进制， 再将十进制的数转化为九进制的数.,【解析】2 017（8）=283+082+18+780=1 039， 因为 所以1 039=1 3
