13算法案例课件（人教A必修3）

1、【课标要求课标要求】1理解辗转相除法与更相减损术的含义，了解其执行过程理解辗转相除法与更相减损术的含义，了解其执行过程2理解秦九韶算法的计算过程，并了解它提高计算效率的实质理解秦九韶算法的计算过程，并了解它提高计算效率的实质3理解进位制的概念，能进行不同进位制间的转化理解进位制的概念，能进行不同进位制间的转化4了解进位制的程序框图和程序了解进位制的程序框图和程序【核心扫描核心扫描】1三种算法的原理及应用三种算法的原理及应用(重难点重难点)2三种算法的框图表示及程序三种算法的框图表示及程序(难点难点)3不同进位制之间的相互转化不同进位制之间的相互转化(重点重点)4秦九韶算法中多项式的改写秦九韶算

2、法中多项式的改写(易错点易错点)1.3算法案例算法案例辗转相除法辗转相除法(1)辗转相除法，又叫欧几里得算法，是一种求两个正整数辗转相除法，又叫欧几里得算法，是一种求两个正整数的的_的古老而有效的算法的古老而有效的算法(2)辗转相除法的算法步骤辗转相除法的算法步骤第一步，给定第一步，给定_.第二步，计算第二步，计算_.第三步，第三步， _.第四步，若第四步，若r0，则，则m、n的最大公约数等于的最大公约数等于_；否则，；否则，返回返回_.自学导引自学导引1最大公约数最大公约数两个正整数两个正整数m，nm除以除以n所得的余数所得的余数rmn，nrm第二步第二步更相减损术更相减损术第一步，任意给定

3、两个正整数，判断它们是否都是第一步，任意给定两个正整数，判断它们是否都是_若若是，用是，用_；若不是，执行；若不是，执行_ 第二步，以第二步，以_的数减去的数减去_的数，接着把所得的差与的数，接着把所得的差与_的数比较，并以大数减小数，继续这个操作，直到所得的数比较，并以大数减小数，继续这个操作，直到所得的数的数_为止，则这个数为止，则这个数(等数等数)或这个数与约简的数的乘积或这个数与约简的数的乘积就是所求的最大公约数就是所求的最大公约数 任意给定两个正整数，用辗转相除法和更相减损术是否任意给定两个正整数，用辗转相除法和更相减损术是否都可以求它们的最大公约数？都可以求它们的最大公约数？提示提

4、示是更相减损术与辗转相除法都能在有限步内结束，是更相减损术与辗转相除法都能在有限步内结束，故均可以用来求两个正整数的最大公约数故均可以用来求两个正整数的最大公约数2偶数偶数2约简约简第二步第二步较小较小较小较小相等相等较大较大秦九韶算法秦九韶算法把一个把一个n次多项式次多项式f(x)anxnan1xn1a1xa0改写成如改写成如下形式：下形式：(anxan1)xan2)xa1)xa0，求多项式的值时，首先计算求多项式的值时，首先计算_一次多项式的值，一次多项式的值，即即v1_，然后由内向外逐层计算一次多项式的值，然后由内向外逐层计算一次多项式的值，即即v2_，v3_，vn_.这样，求这样，求n

5、次多项式次多项式f(x)的值就转化为求的值就转化为求_的的值值3最内层括号内最内层括号内anxan1v1xan2v2xan3vn1xa0n个一次多项式个一次多项式进位制进位制进位制是人们为了进位制是人们为了_和和_而约定的记数系统，而约定的记数系统，“满满k进一进一”就是就是k进制，进制，k进制的基数是进制的基数是k.把十进制转化为把十进制转化为k进制数时，通常用除进制数时，通常用除k取余法取余法 不同进制间的数不能比较大小，对吗？不同进制间的数不能比较大小，对吗？提示提示不对不同的进位制是人们为了计数和运算方便而不对不同的进位制是人们为了计数和运算方便而约定的记数系统，不同进位制的数照样可比

6、较大小，不过约定的记数系统，不同进位制的数照样可比较大小，不过一般要转化到十进制下比较大小更方便一些一般要转化到十进制下比较大小更方便一些4计数计数运算方便运算方便1辗转相除法与更相减损术的区别和联系辗转相除法与更相减损术的区别和联系名师点睛名师点睛名称名称辗转相除法辗转相除法更相减损术更相减损术区别区别以除法为主以除法为主两个整数差值较大两个整数差值较大时运算次数较少时运算次数较少相除余数为零时得相除余数为零时得结果结果以减法为主以减法为主两个整数的差值较大两个整数的差值较大时，运算次数较多时，运算次数较多相减，两数相等得结相减，两数相等得结果果相减前要做是否都是相减前要做是否都是偶数的判断

7、偶数的判断联系联系都是求两个正整数的最大公约数的方法都是求两个正整数的最大公约数的方法二者的实质都是递推的过程二者的实质都是递推的过程二者都要用循环结构来实现二者都要用循环结构来实现秦九韶算法秦九韶算法(1)特点：通过一次式的反复计算，逐步得出高次多项式的特点：通过一次式的反复计算，逐步得出高次多项式的值，对于一个值，对于一个n次多项式，只需做次多项式，只需做n次乘法和次乘法和n次加法即次加法即可可(2)算法步骤：算法步骤：设设Pn(x)anxnan1xn1a1xa0，将其改写为，将其改写为Pn(x)(anxn1an1xn2a1)xa0(anxn2an1xn3a2)xa1)xa0(anxan1

8、)xan2)xa1)xa0.第一步：计算最内层第一步：计算最内层anxan1的值，将的值，将anxan1的值赋给的值赋给一个变量一个变量v1(为方便将为方便将an赋予变量赋予变量v0)；第二步：计算第二步：计算(anxan1)xan2的值，可以改写为的值，可以改写为v1xan2，将，将v1xan2的值赋给一个变量的值赋给一个变量v2；2.依次类推，即每一步的计算之后都赋予一个新值依次类推，即每一步的计算之后都赋予一个新值vk，即从，即从最内层的括号到最外层最内层的括号到最外层括号的值依次赋予变量括号的值依次赋予变量v1，v2，vk，vn，第，第n步所步所求值求值vnvn1xa0即为所求多项式的

9、值即为所求多项式的值(3)秦九韶算法有以下几个优点：秦九韶算法有以下几个优点：大大减少了乘法的次数，使计算量减小在计算机上做大大减少了乘法的次数，使计算量减小在计算机上做一次乘法所需要的时间是做加法、减法的几倍到十几倍，一次乘法所需要的时间是做加法、减法的几倍到十几倍，减少做乘法的次数也就加快了计算的速度；减少做乘法的次数也就加快了计算的速度；规律性强，便于利用循环语句来实现算法；规律性强，便于利用循环语句来实现算法；避免了对自变量避免了对自变量x单独做幂的计算，每次都是计算一个单独做幂的计算，每次都是计算一个一次多项式的值，从而可以提高计算的精度一次多项式的值，从而可以提高计算的精度关于进位

10、制应注意的问题关于进位制应注意的问题(1)十进制的原理是满十进一一个十进制正整数十进制的原理是满十进一一个十进制正整数N可以写可以写成成an10nan110n1a1101a0100的形式，的形式，其中其中an，an1，a1，a0都是都是0至至9中的数字，且中的数字，且an0.例例如如36531026105.(2)一般地，一般地，k进制数的原理是满进制数的原理是满k进一，进一，k进制数一般在右进制数一般在右下角处标注下角处标注(k)，以示区别例如，以示区别例如270(8)表示表示270是一个是一个8进进制数但十进制一般省略不写制数但十进制一般省略不写(3)在在k进制中，有：进制中，有：有有k个不

11、同的数字符号，即个不同的数字符号，即0,1,2,3，(k1)；“逢逢k进一进一”，即每位数计满，即每位数计满k后向高位进一后向高位进一一个一个k进位制的正整数就是各位数码与进位制的正整数就是各位数码与k的方幂的乘积的的方幂的乘积的和，其中幂指数等于相应数码所在位数和，其中幂指数等于相应数码所在位数(从右往左数从右往左数)减减1.例如例如230 451(k)2k53k40k34k25k1.3题型一题型一求两个正整数的最大公约数求两个正整数的最大公约数 分别用辗转相除法和更相减损术求分别用辗转相除法和更相减损术求261和和319的最大公的最大公约数约数思路探索思路探索 使用辗转相除法可依据使用辗转

12、相除法可依据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)利用辗转相除法求给定的两个数的最大公约利用辗转相

13、除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数原来两个数的最大公约数(2)利用更相减损术求两个正整数的最大公约数的一般步骤利用更相减损术求两个正整数的最大公约数的一般步骤是：首先判断两个正整数是否都是偶数若是，用是：首先判断两个正整数是否都是偶数若是，用2约约简也可以不除以简也可以不除以2，直接

14、求最大公约数，这样不影响最，直接求最大公约数，这样不影响最后结果后结果 用辗转相除法求用辗转相除法求80与与36的最大公约数，并用更相减的最大公约数，并用更相减损术检验你的结果损术检验你的结果解解803628，36844,8420，即即80与与36的最大公约数是的最大公约数是4.验证：验证：80240362184022018292091111929277255233212111224所以所以80与与36的最大公约数为的最大公约数为4.【变式变式1】 将七进制数将七进制数235(7)转化为八进制转化为八进制解解235(7)2723715124，利用除，利用除8取余法取余法(如图所示如图所示)，所

15、以，所以124174(8)所以所以235(7)转化为八进制数为转化为八进制数为174(8)题型题型二二进位制之间的转化进位制之间的转化【例例2】规律方法规律方法对于非十进制数之间的互化，通常是把这个数对于非十进制数之间的互化，通常是把这个数先转化为十进制数，然后再利用除先转化为十进制数，然后再利用除k取余法，把十进制数取余法，把十进制数转化为转化为k进制数而在使用除进制数而在使用除k取余法时要注意以下几点：取余法时要注意以下几点：(1)必须除到所得的商是必须除到所得的商是0为止；为止；(2)各步所得的余数必须从各步所得的余数必须从下到上排列；下到上排列；(3)切记在所求数的右下角标明基数切记在

16、所求数的右下角标明基数 把下列各数转换成十进制数把下列各数转换成十进制数(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)x

17、5)x12)x6，按照从内到外的顺，按照从内到外的顺序，依次计算一次多项式当序，依次计算一次多项式当x2时的值时的值 (2分分)v03，v1v02832814， (4分分)v2v123142325， (6分分)v3v225252555， (8分分)v4v321255212122，v5v42612226238， (10分分)所以当所以当x2时，多项式的值为时，多项式的值为238. (12分分)【题后反思题后反思】 (1)先将多项式写成一次多项式的形式，然先将多项式写成一次多项式的形式，然后运算时从里到外，一步一步地做乘法和加法即可这样后运算时从里到外，一步一步地做乘法和加法即可这样比直接将比直接

18、将x2代入原式大大减少了计算量若用计算机计代入原式大大减少了计算量若用计算机计算，则可提高运算效率算，则可提高运算效率(2)注意：当多项式中注意：当多项式中n次项不存在时，可将第次项不存在时，可将第n次项看作次项看作0 xn. 用秦九韶算法计算用秦九韶算法计算f(x)6x54x4x32x29x，需，需要加法要加法(或减法或减法)与乘法运算的次数分别为与乘法运算的次数分别为 ()A5,4 B5,5 C4,4 D4,5解析解析n次多项式需进行次多项式需进行n次乘法；若各项均不为零，则需次乘法；若各项均不为零，则需进行进行n次加法，缺一项就减少一次加法运算次加法，缺一项就减少一次加法运算f(x)中无常数中无常数项，故加法次数要减少一次，为项，故加法次数要减少一次，为514.故选故选D.答案答案D【变式变式3】 已知已知f(x)x52x43x34x25x6，用秦九韶算法，用秦九韶算法求这个多项式当求这个多项式当x2时的