山东省高中数学(新课标人教A版)必修三《1.3算法案例》.ppt

【课标要求】 1理解辗转相除法与更相减损术的含义，了解其执行过程 2理解秦九韶算法的计算过程，并了解它提高计算效率的实质 3理解进位制的概念，能进行不同进位制间的转化 4了解进位制的程序框图和程序 【核心扫描】 1三种算法的原理及应用(重难点) 2三种算法的框图表示及程序(难点) 3不同进位制之间的相互转化(重点) 4秦九韶算法中多项式的改写(易错点),1.3 算法案例,辗转相除法 (1)辗转相除法，又叫欧几里得算法，是一种求两个正整数的_的古老而有效的算法 (2)辗转相除法的算法步骤 第一步，给定_. 第二步，计算_. 第三步， _. 第四步，若r0，则m、n的最大公约数等于_；否则，返回_.,自学导引,1,最大公约数,两个正整数m，n,m除以n所得的余数r,mn，nr,m,第二步,更相减损术 第一步，任意给定两个正整数，判断它们是否都是_若是，用_；若不是，执行_ 第二步，以_的数减去_的数，接着把所得的差与_的数比较，并以大数减小数，继续这个操作，直到所得的数_为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数 任意给定两个正整数，用辗转相除法和更相减损术是否都可以求它们的最大公约数？ 提示 是更相减损术与辗转相除法都能在有限步内结束，故均可以用来求两个正整数的最大公约数,2,偶数,2约简,第二步,较小,较小,相等,较大,秦九韶算法 把一个n次多项式f(x)anxnan1xn1a1xa0改写成如下形式： (anxan1)xan2)xa1)xa0， 求多项式的值时，首先计算_一次多项式的值，即v1_，然后由内向外逐层计算一次多项式的值，即 v2_， v3_， vn_. 这样，求n次多项式f(x)的值就转化为求_的值,3,最内层括号内,anxan1,v1xan2,v2xan3,vn1xa0,n个一次多项式,进位制 进位制是人们为了_和_而约定的记数系统，“满k进一”就是k进制，k进制的基数是k. 把十进制转化为k进制数时，通常用除k取余法 不同进制间的数不能比较大小，对吗？ 提示 不对不同的进位制是人们为了计数和运算方便而约定的记数系统，不同进位制的数照样可比较大小，不过一般要转化到十进制下比较大小更方便一些,4,计数,运算方便,1辗转相除法与更相减损术的区别和联系,名师点睛,秦九韶算法 (1)特点：通过一次式的反复计算，逐步得出高次多项式的值，对于一个n次多项式，只需做n次乘法和n次加法即可 (2)算法步骤： 设Pn(x)anxnan1xn1a1xa0，将其改写为 Pn(x)(anxn1an1xn2a1)xa0 (anxn2an1xn3a2)xa1)xa0 (anxan1)xan2)xa1)xa0. 第一步：计算最内层anxan1的值，将anxan1的值赋给一个变量v1(为方便将an赋予变量v0)； 第二步：计算(anxan1)xan2的值，可以改写为v1xan2，将v1xan2的值赋给一个变量v2；,2.,依次类推，即每一步的计算之后都赋予一个新值vk，即从最内层的括号到最外层 括号的值依次赋予变量v1，v2，vk，vn，第n步所求值vnvn1xa0即为所求多项式的值 (3)秦九韶算法有以下几个优点： 大大减少了乘法的次数，使计算量减小在计算机上做一次乘法所需要的时间是做加法、减法的几倍到十几倍，减少做乘法的次数也就加快了计算的速度； 规律性强，便于利用循环语句来实现算法； 避免了对自变量x单独做幂的计算，每次都是计算一个一次多项式的值，从而可以提高计算的精度,关于进位制应注意的问题 (1)十进制的原理是满十进一一个十进制正整数N可以写成an10nan110n1a1101a0100的形式，其中an，an1，a1，a0都是0至9中的数字，且an0.例如36531026105. (2)一般地，k进制数的原理是满k进一，k进制数一般在右下角处标注(k)，以示区别例如270(8)表示270是一个8进制数但十进制一般省略不写 (3)在k进制中，有： 有k个不同的数字符号，即0,1,2,3，(k1)； “逢k进一”，即每位数计满k后向高位进一 一个k进位制的正整数就是各位数码与k的方幂的乘积的和，其中幂指数等于相应数码所在位数(从右往左数)减1. 例如230 451(k)2k53k40k34k25k1.,3,题型一 求两个正整数的最大公约数,分别用辗转相除法和更相减损术求261和319的最大公约数 思路探索 使用辗转相除法可依据mnqr，反复执行直到余数为0；更相减损术则是根据mnr，反复执行，直到nr为止 解 法一 (辗转相除法) 3192611(余58)， 261584(余29)， 58292(余0)， 所以319与261的最大公约数为29.,【例1】,法二 (更相减损术) 31926158， 26158203， 20358145， 1455887， 875829， 582929， 29290， 所以319与261的最大公约数是29.,规律方法 (1)利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数 (2)利用更相减损术求两个正整数的最大公约数的一般步骤是：首先判断两个正整数是否都是偶数若是，用2约简也可以不除以2，直接求最大公约数，这样不影响最后结果,用辗转相除法求80与36的最大公约数，并用更相减损术检验你的结果 解 803628， 36844,8420， 即80与36的最大公约数是4. 验证： 80240 36218 40220 1829 20911 1192 927 725 523 321 211 1224 所以80与36的最大公约数为4.,【变式1】,将七进制数235(7)转化为八进制 解 235(7)2723715124，利用除8取余法(如图所示)，所以124174(8) 所以235(7)转化为八进制数为174(8),题型二 进位制之间的转化,【例2】,规律方法 对于非十进制数之间的互化，通常是把这个数先转化为十进制数，然后再利用除k取余法，把十进制数转化为k进制数而在使用除k取余法时要注意以下几点：(1)必须除到所得的商是0为止；(2)各步所得的余数必须从下到上排列；(3)切记在所求数的右下角标明基数,把下列各数转换成十进制数 (1)101 101(2)；(2)2 102(3)；(3)4 301(6) 解 (1)101 101(2)12502412312202145. (2)2 102(3)233132265. (3)4 301(6)4633621973.,【变式2】,用秦九韶算法求f(x)3x58x43x35x212x6，当x2的值,题型三 秦九韶算法在多项式中的应用,【例3】,规范解答 根据秦九韶算法，把多项式改写成如下形式： f(x)(3x8)x3)x5)x12)x6，按照从内到外的顺序，依次计算一次多项式当x2时的值 (2分) v03， v1v02832814， (4分) v2v123142325， (6分) v3v225252555， (8分) v4v321255212122， v5v42612226238， (10分) 所以当x2时，多项式的值为238. (12分),【题后反思】 (1)先将多项式写成一次多项式的形式，然后运算时从里到外，一步一步地做乘法和加法即可这样比直接将x2代入原式大大减少了计算量若用计算机计算，则可提高运算效率 (2)注意：当多项式中n次项不存在时，可将第n次项看作0xn.,用秦九韶算法计算f(x)6x54x4x32x29x，需要加法(或减法)与乘法运算的次数分别为 ( ) A5,4 B5,5 C4,4 D4,5 解析 n次多项式需进行n次乘法；若各项均不为零，则需进行n次加法，缺一项就减少一次加法运算f(x)中无常数项，故加法次数要减少一次，为514.故选D. 答案 D,【变式3】,已知f(x)x52x43x34x25x6，用秦九韶算法求这个多项式当x2时的值时，做了几次乘法？几次加法？ 错解 根据秦九韶算法，把多项式改写成如下形式f(x)(x2)x3)x4)x5)x6. 按照从内到外的顺序，依次计算一次多项式当x2时的 值：v1224；v22v1311；v32v2426；v42v3557；v52v46120. 显然，在v1中未做乘法，只做了1次加法；在v2，v3，v4，v5中各做了1次加法，1次乘法因此，共做了4次乘法，5次加法,误区警示 对秦九韶算法中的运算次数理解错误,【示例】,在v1中虽然“v1224”，而