2019_2020学年高中数学第一章算法初步1.3算法案例课件新人教A版必修3.pptx

1、1.3算法案例,1辗转相除法与更相减损术,除法,减法,循环结构,2秦九韶算法 概念：求多项式f(x)anxnan1xn1a1xa0的值时，常用秦九韶算法，这种算法的运算次数较少，是多项式求值比较先进的算法，其实质是转化为求n个_多项式的值，共进行_次乘法运算和_次加法运算 3进位制 人们为了计数和运算方便而约定的计数系统，“满k进一”就是_进制，k是基数(其中k是大于1的整数),一次,n1,n,k,1怎样用短除法求最大公约数？ 【解析】短除法求两个正整数的最大公约数的步骤：先用两个数公有的质因数连续去除，一直除到所得的商是两个互质数为止，然后把所有的除数连乘起来,2用辗转相除法求36与134的

2、最大公约数，第一步是() A1343698 B13436326 C先除以2，得到18与67 D3626110 【答案】B 【解析】求36与134的最大公约数，第一步是13436326，第二步是3626110，故选B,3用辗转相除法求294和84的最大公约数时，需要做除法的次数是() A1B2 C3D4 【答案】B 【解析】本题考查辗转相除法的过程.29484342,84422，故选B,4以下各数有可能是五进制数的是() A15B106 C731D21 340 【答案】D 【解析】五进制数中各个数字均是小于5的自然数，则仅有21 340满足,辗转相除法和更相减损术的应用,【例1】用辗转相除法或者

3、更相减损术求三个数324,243, 135的最大公约数 【解析】辗转相除法 324243181,2438130， 则324与243的最大公约数为81. 又13581154,8154127， 542720，,则81与135的最大公约数为27. 所以，三个数324,243,135的最大公约数为27. 更相减损术 32424381,24381162,1628181，则324与243的最大公约数为81. 1358154,815427,542727，则81与135的最大公约数为27. 所以，三个数324,243,135的最大公约数为27.,更相减损术与辗转相除法的比较：尽管两种算法分别来源于东、西方古代

4、数学名著，但是二者的算理却是相似的，有异曲同工之妙主要区别在于辗转相除法进行的是除法运算，即辗转相除；而更相减损术进行的是减法运算，即辗转相减，但是实质都是一个不断的递归过程,1分别用辗转相除法和更相减损术求1 734和816的最大公约数 【解析】辗转相除法 1 7348162102,8161028(余0)， 1 734与816的最大公约数是102.,更相减损术 因为两数皆为偶数，首先除以2得到867,408，再求867与408的最大公约数 867408459,45940851,40851357， 35751306,30651255,25551204， 20451153,15351102,10

5、25151. 1 734与816的最大公约数是512102.,用秦九韶算法求多项式的值,【例2】用秦九韶算法求多项式f(x)7x76x65x54x43x32x2x当x3时的值 【解题探究】解决本题首先需要将原多项式化成f(x)(7x6)x5)x4)x3)x2)x1)x的形式，其次再弄清v0，v1，v2，v7分别是多少，再针对这些式子进行计算 【解析】f(x)(7x6)x5)x4)x3)x2)x1)x，所以有 v07； v173627；,v2273586； v38634262； v426233789； v5789322 369； v62 369317 108； v77 108321 324. 故

6、当x3时，多项式f(x)7x76x65x54x43x32x2x的值为21 324.,用秦九韶算法时要正确将多项式的形式进行改写，然后由内向外依次计算当多项式函数中间出现空项时，要以系数为零的齐次项补充,2已知n次多项式Pn(x)a0 xna1xn1an1xan，如果在一种算法中，计算x(k2,3,4，n)的值需要k1次乘法，计算P3(x0)的值共需要9次运算(6次乘法，3次加法)，那么计算P10(x0)的值共需要_次运算下面给出一种减少运算次数的算法：P0(x)a0，Pk1(x)xPk(x)ak1(k0,1，2，n1)利用该算法，计算P3(x0)的值共需要6次运算(3次乘法，3次加法)，计算P

7、10(x0)的值共需要_次运算,【答案】6520,把k进制数化为十进制数,【例3】(1)把七进制数123化成十进制数为_ (2)下列各数85(9)，301(5)，1 000(4)中最小的数是_ 【解题探究】1.七进制数从右边数第二位的数字若是k(k0,1,2,3,4,5,6)，其在十进制中表示的数是多少？ 2相同进制中，位数越多的数越大对吗？不同进制中的数如何比较大小？,【答案】(1)66(2)1 000(4) 【解析】(1)123(7)1722713704914366. (2)85(9)89159072577. 301(5)35205115075176. 1000(4/p>

8、064. 所以1 000(4)最小,1k进制数化为十进制数的步骤 (1)把k进制数写成不同数位上的数字与k的幂的乘积之和的形式 (2)按十进制数的运算规则运算出结果,2进位制的性质 (1)在k进制中，具有k个数字符号，它们是0,1,2，(k1) (2)在k进制中，由低位向高位是按“满k进一”的规则进行计数 (3)不同进位制都是按位置原则计数的,3(1)101(2)转化为十进制数是() A2B5 C20D101 (2)下列最大数是() A110(2)B18 C16(8)D20(5),【答案】(1)B(2)B 【解析】(1)101(2)1220211205. (2)110(2)1221210206

9、；16(8)18168014；20(5)25105010，则最大数是18.,把十进制数化为k进制数,【例4】把89化为二进制数 【解析】根据二进制数“满二进一”的原则，可以用2连续去除89或所得商，然后取余数具体计算方法如下： 因为892441,442220， 222110,11251， 5221,2210， 1201，,所以 892(2(2(2(221)1)0)0)1 2(2(2(2(221)1)0)0)1 126025124123022021120 1 011 001(2) 这种算法叫做除2取余法，还可以用下面的除法算式表示：,把上式中各步所得的余数从下到上排列，得到891 011 001

10、(2) 上述方法也可以推广为把十进制数化为k进制数的算法，称为除k取余法,十进制数化为k进制数(除k取余法)的步骤,4(1)(2015年黑龙江哈尔滨高一检测)把十进制数15化为二进制数为() A1011B1001(2) C1111(2)D1111 (2)把四进制数13 022化为六进制数为_ 【答案】(1)C(2)2 042(6),【解析】(1)因为 所以151 111(2)，故C正确 (2)先把四进制数13 022化为十进制数 13 022(4)144343042241240256192082458.,【示例】下列结论正确的是() A88(9)210(6)B62124(5) C110(2)1

11、0(3)D32(4)23(6) 【错解】A或B,不同进位制之间数的大小比较时忽略转化致误,【错因】对于选项A没有进行转化，而直接由210(6)是三位数，88(9)是两位数，三位数大于两位数，从而误选A；对于选项B省略了转化，因为10是5的2倍，从而误以为五进制数是十进制数的2倍，从而误选B,对于B：因为124(5)1522514503962，所以B错误 对于C：因为110(2)1221210206， 10(3)1310303,63，所以C正确 对于D：因为32(4)34124014， 23(6)26136015,1415. 所以D错误故选C,【警示】1.对于非十进制数之间的互化，通常是把这个数

12、先转化为十进制数，然后再利用除k取余法，把十进制数转化为k进制数而在使用除k取余法时要注意以下两点：(1)必须除到所得的商是0为止；(2)各步所得的余数必须从下到上排列；(3)切记在所求数的右下角标明基数 2注意进位制成倍数关系的两数的区别 k进制数并不是2k进制数的2倍，如十进制数化为五进制数时，并不是该十进制数的2倍，如本例中62124(5),1求最大公约数的方法要熟练使用，但一般不要求会编写相应的程序 2三个数的最大公约数求法一般是只求第一与第二个数的最大公约数，然后求这个最大公约数与第三个数的最大公约数 3秦九韶算法的优点是能减少计算量，对相应的程序框图不作具体要求 4进位制是十分重要的知识点，要求掌握不同进位制的转换,1下列有关辗转相除法的说法正确的是() A它和更相减损术一样是求多项式值的一种方法 B基本步骤是用较大的数m除以较小的数n得到除式mnqr，直至rn为止 C基本步骤是用较大的数m除以较小的数n得到除式mqnr(0rn)反复进行，直到r0为止 D以上说法均不正确 【答案】C,2k进制数32 501(k)，则k不可能是() A5B6 C7D8 【答案】A 【解析】k进制数中各个数字均小于k，则k5.,3按照秦九韶算法求多项式f(x)1.5x53.5x44.1x33.6x6当x0.5时的值的过程中，令v0a5，v1v0 xa4，v5v4xa0，