2014-2015学年高中数学（人教A版）必修三同步课件：1.3 算法案例.ppt

1、高中数学必修3人教A版1.3 算法案例学习目标1理解辗转相除法与更相减损术的含义，了解其执行过程2理解秦九韶算法的计算过程，并了解它提高计算效率的实质3理解进位制的概念，能进行不同进位制间的转化4了解进位制的程序框图和程序知识链接(1)20和30的最大公约数为_(2)在数学运算中，经常采用十进制，即_；在生活中，也有其它进制，如每60分钟为1小时，即_(3)已知函数f(x)x22x1，计算f(1)的值时用了_次乘法和_次加法运算；当函数变为f(x)(x2)x1，求f(1)时，用了1次乘法运算和_次加法运算10满十进一60进制222预习导引1辗转相除法(1)辗转相除法，又叫欧几里得算法，是一种求

2、两个正整数的_的古老而有效的算法(2)辗转相除法的算法步骤第一步，给定_第二步，计算_第三步，_第四步，若r0，则m，n的最大公约数等于_；否则，返回_最大公约数两个正整数m，nm除以n所得的余数rmn，nrm第二步2更相减损术第一步，任意给定两个正整数，判断它们是否都是_若是，用_；若不是，执行_第二步，以_的数减去_的数，接着把所得的差与_的数比较，并以大数减小数，继续这个操作，直到所得的数_为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数偶数2约简第二步较大较小相等较小3秦九韶算法把一个n次多项式f(x)anxnan1xn1a1xa0改写成如下形式：(anxan1)xa

3、n2)xa1)xa0，求多项式的值时，首先计算_一次多项式的值，即v1_，然后由内向外逐层计算一次多项式的值，即v2_，v3_，vn_这样，求n次多项式f(x)的值就转化为求_的值n个一次多项式最内层括号内anxan1v1xan2v2xan3vn1xa04进位制进位制是人们为了_和_而约定的记数系统，“满k进一”就是k进制，k进制的基数是k.把十进制转化为k进制数时，通常用除k取余法计数运算方便要点一 求两个正整数的最大公约数例1 分别用辗转相除法和更相减损术求261和319的最大公约数解法一(辗转相除法)3192611(余58)，261584(余29)，58292(余0)，所以319与261

4、的最大公约数为29.法二(更相减损术)31926158，26158203，20358145，1455887，875829，582929，29290，所以319与261的最大公约数是29.规律方法1.利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数2利用更相减损术求两个正整数的最大公约数的一般步骤是：首先判断两个正整数是否都是偶数若是，用2约简也可以不除以2，直接求最大公约数，这样不影响最后结果跟踪演练1 用辗转相除法求80与36的最大

5、公约数，并用更相减损术检验你的结果解803628，36844，8420，即80与36的最大公约数是4.验证：80240362184022018292091111929277255233212111224所以80与36的最大公约数为4.要点二 秦九韶算法例2 已知一个5次多项式为f(x)4x52x43.5x32.6x21.7x0.8，用秦九韶算法求这个多项式当x5时的值解 将f(x)改写为f(x)(4x2)x3.5)x2.6)x1.7)x0.8，由内向外依次计算一次多项式当x5时的值：v04；v145222；v22253.5113.5；v3113.552.6564.9；v4564.951.72

6、826.2；v52 826.250.814 130.2.当x5时，多项式的值等于14 130.2.规律方法1.先将多项式写成一次多项式的形式，然后运算时从里到外，一步一步地做乘法和加法即可这样比直接将x2代入原式大大减少了计算量若用计算机计算，则可提高运算效率2注意：当多项式中n次项不存在时，可将第n次项看作0 xn.跟踪演练2 用秦九韶算法计算f(x)6x54x4x32x29x，需要加法(或减法)与乘法运算的次数分别为()A5，4 B5，5 C4，4 D4，5答案D解析n次多项式需进行n次乘法；若各项均不为零，则需进行n次加法，缺一项就减少一次加法运算f(x)中无常数项，故加法次数要减少一次

7、，为514.故选D.要点三 进位制例3(1)把二进制数1110011(2)化为十进制数(2)将8进制数314706(8)化为十进制数解(1)1110011(2)1261251240230221211115.(2)314706(8)385184483782081680104902.所以，化为十进制数是104902.规律方法1.将k进制转化为十进制的方法是：先将这个k进制数写成各个数位上的数字与k的幂的乘积之和的形式，再按照十进制的运算规则计算出结果2十进制转化为k进制，采用除k取余法，也就是除基数，倒取余跟踪演练3 将八进制数74化成二进制数解 首先将八进制数74化成十进制数：74(8)7814

8、8060(10)，然后再将十进制数60化成二进制数所以60(10)111 100(2)综上可得74(8)111 100(2)1两个整数490和910的最大公约数是()A2 B10 C30 D70答案D解析9104901420，490420170，420706，490与910的最大公约数是70.2下列有可能是4进制数的是()A5 123 B6 542 C3 103 D4 312答案C解析4进制数每位上的数字一定小于4，故选C.3用秦九韶算法求多项式f(x)7x66x53x22，当x4时的值时，先算的是()A4416 B7428C44464 D74634答案D解析 因为f(x)anxnan1xn1

9、a1xa0(anxan1)xan2)xa1)xa0，所以用秦九韶算法求多项式f(x)7x66x53x22当x4时的值时，先算的是74634.4(2013淮安高一检测)下列二进制数中最大的数是()A111(2)B1001(2)C110(2)D101(2)答案B解析 据k进制数的位置原则知，四位数一定大于三位数，故选B.也可以先把它化为十进制数，再比较5用更相减损术求36与134的最大公约数，第一步应为_答案 先除以2，得到18与67解析36与134都是偶数，第一步应为：先除以2，得到18与67.1求两个正整数的最大公约数的问题，可以用辗转相除法，也可以用更相减损术用辗转相除法，即根据anbr这个式子，反复相除，直到r0为止；用更相减损术，即根据r|ab|这个式子，反复相减，直到r0为止2秦九韶算法的关键在于把n次多项式转化为一次多项式，注意体会递推的实现过程，实施运算时要由内向外，一步一步执行3把一个非十进制数转化为另一种非十进制数，通常是把这个数先转化为十进制数，然后再利用除k取余法，把十进制数转化为k进制数而在使用除k取余法时要注意以下几点：(1)必须除到所得的商是0为止；(2)各步所得的余数必须从下到上排列；(3)切记在所求数的右下角标明基数.再见