人教版新课标B必修31.3 中国古代数学中的算法案例示范课ppt课件

这是一份人教版新课标B必修31.3 中国古代数学中的算法案例示范课ppt课件，共22页。PPT课件主要包含了自学导引，最大公约数，两个正整数mn，m除以n所得的余数r，m＝nn＝r，第二步，最内层括号内，anx＋an－1，v1x＋an－2，v2x＋an－3等内容，欢迎下载使用。
辗转相除法(1)辗转相除法，又叫欧几里得算法，是一种求两个正整数的___________的古老而有效的算法．(2)辗转相除法的算法步骤第一步，给定________________.第二步，计算___________________.第三步， ____________.第四步，若r＝0，则m、n的最大公约数等于___；否则，返回________.
更相减损术第一步，任意给定两个正整数，判断它们是否都是_____．若是，用_______；若不是，执行_______ ．第二步，以_____的数减去_____的数，接着把所得的差与_____的数比较，并以大数减小数，继续这个操作，直到所得的数_____为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数． 任意给定两个正整数，用辗转相除法和更相减损术是否都可以求它们的最大公约数？提示　是．更相减损术与辗转相除法都能在有限步内结束，故均可以用来求两个正整数的最大公约数．
秦九韶算法把一个n次多项式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0改写成如下形式：(…((anx＋an－1)x＋an－2)x＋…＋a1)x＋a0，求多项式的值时，首先计算_____________一次多项式的值，即v1＝__________，然后由内向外逐层计算一次多项式的值，即v2＝__________，v3＝__________，…vn＝__________.这样，求n次多项式f(x)的值就转化为求________________的值．
进位制进位制是人们为了_____和_________而约定的记数系统，“满k进一”就是k进制，k进制的基数是k.把十进制转化为k进制数时，通常用除k取余法． 不同进制间的数不能比较大小，对吗？提示　不对．不同的进位制是人们为了计数和运算方便而约定的记数系统，不同进位制的数照样可比较大小，不过一般要转化到十进制下比较大小更方便一些．
1．辗转相除法与更相减损术的区别和联系
秦九韶算法(1)特点：通过一次式的反复计算，逐步得出高次多项式的值，对于一个n次多项式，只需做n次乘法和n次加法即可．(2)算法步骤：设Pn(x)＝anxn＋an－1xn－1＋…＋a1x＋a0，将其改写为Pn(x)＝(anxn－1＋an－1xn－2＋…＋a1)x＋a0＝((anxn－2＋an－1xn－3＋…＋a2)x＋a1)x＋a0＝(…((anx＋an－1)x＋an－2)x＋…＋a1)x＋a0.第一步：计算最内层anx＋an－1的值，将anx＋an－1的值赋给一个变量v1(为方便将an赋予变量v0)；第二步：计算(anx＋an－1)x＋an－2的值，可以改写为v1x＋an－2，将v1x＋an－2的值赋给一个变量v2；
依次类推，即每一步的计算之后都赋予一个新值vk，即从最内层的括号到最外层．括号的值依次赋予变量v1，v2，…，vk，…，vn，第n步所求值vn＝vn－1x＋a0即为所求多项式的值．(3)秦九韶算法有以下几个优点：①大大减少了乘法的次数，使计算量减小．在计算机上做一次乘法所需要的时间是做加法、减法的几倍到十几倍，减少做乘法的次数也就加快了计算的速度；②规律性强，便于利用循环语句来实现算法；③避免了对自变量x单独做幂的计算，每次都是计算一个一次多项式的值，从而可以提高计算的精度．
关于进位制应注意的问题(1)十进制的原理是满十进一．一个十进制正整数N可以写成an×10n＋an－1×10n－1＋…＋a1×101＋a0×100的形式，其中an，an－1，…，a1，a0都是0至9中的数字，且an≠0.例如365＝3×102＋6×10＋5.(2)一般地，k进制数的原理是满k进一，k进制数一般在右下角处标注(k)，以示区别．例如270(8)表示270是一个8进制数．但十进制一般省略不写．(3)在k进制中，有：①有k个不同的数字符号，即0,1,2,3，…，(k－1)；②“逢k进一”，即每位数计满k后向高位进一．一个k进位制的正整数就是各位数码与k的方幂的乘积的和，其中幂指数等于相应数码所在位数(从右往左数)减1.例如230 451(k)＝2×k5＋3×k4＋0×k3＋4×k2＋5×k＋1.
题型一　求两个正整数的最大公约数
分别用辗转相除法和更相减损术求261和319的最大公约数．[思路探索] 使用辗转相除法可依据m＝nq＋r，反复执行直到余数为0；更相减损术则是根据m－n＝r，反复执行，直到n＝r为止．解　法一　(辗转相除法)319÷261＝1(余58)，261÷58＝4(余29)，58÷29＝2(余0)，所以319与261的最大公约数为29.
法二　(更相减损术)319－261＝58，261－58＝203，203－58＝145，145－58＝87，87－58＝29，58－29＝29，29－29＝0，所以319与261的最大公约数是29.
规律方法　(1)利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数．(2)利用更相减损术求两个正整数的最大公约数的一般步骤是：首先判断两个正整数是否都是偶数．若是，用2约简．也可以不除以2，直接求最大公约数，这样不影响最后结果．
用辗转相除法求80与36的最大公约数，并用更相减损术检验你的结果．解　80＝36×2＋8，36＝8×4＋4,8＝4×2＋0，即80与36的最大公约数是4.验证：80÷2＝40　36÷2＝1840÷2＝20　18÷2＝920—9＝11　11－9＝29－2＝7　7－2＝55－2＝3　3－2＝12－1＝1　1×2×2＝4所以80与36的最大公约数为4.
将七进制数235(7)转化为八进制．解　235(7)＝2×72＋3×71＋5＝124，利用除8取余法(如图所示)，所以124＝174(8)．所以235(7)转化为八进制数为174(8)．
题型二　进位制之间的转化
规律方法　对于非十进制数之间的互化，通常是把这个数先转化为十进制数，然后再利用除k取余法，把十进制数转化为k进制数．而在使用除k取余法时要注意以下几点：(1)必须除到所得的商是0为止；(2)各步所得的余数必须从下到上排列；(3)切记在所求数的右下角标明基数．
把下列各数转换成十进制数．(1)101 101(2)；(2)2 102(3)；(3)4 301(6)．解　(1)101 101(2)＝1×25＋0×24＋1×23＋1×22＋0×2＋1＝45.(2)2 102(3)＝2×33＋1×32＋2＝65.(3)4 301(6)＝4×63＋3×62＋1＝973.
用秦九韶算法求f(x)＝3x5＋8x4－3x3＋5x2＋12x－6，当x＝2的值．
题型三　秦九韶算法在多项式中的应用
[规范解答] 根据秦九韶算法，把多项式改写成如下形式：f(x)＝((((3x＋8)x－3)x＋5)x＋12)x－6，按照从内到外的顺序，依次计算一次多项式当x＝2时的值． (2分)v0＝3，v1＝v0×2＋8＝3×2＋8＝14， (4分)v2＝v1×2－3＝14×2－3＝25， (6分)v3＝v2×2＋5＝25×2＋5＝55， (8分)v4＝v3×2＋12＝55×2＋12＝122，v5＝v4×2－6＝122×2－6＝238， (10分)所以当x＝2时，多项式的值为238. (12分)
【题后反思】 (1)先将多项式写成一次多项式的形式，然后运算时从里到外，一步一步地做乘法和加法即可．这样比直接将x＝2代入原式大大减少了计算量．若用计算机计算，则可提高运算效率．(2)注意：当多项式中n次项不存在时，可将第n次项看作0·xn.
用秦九韶算法计算f(x)＝6x5－4x4＋x3－2x2－9x，需要加法(或减法)与乘法运算的次数分别为 (　　)．A．5,4 B．5,5 C．4,4 D．4,5解析　n次多项式需进行n次乘法；若各项均不为零，则需进行n次加法，缺一项就减少一次加法运算．f(x)中无常数项，故加法次数要减少一次，为5－1＝4.故选D.答案　D
已知f(x)＝x5＋2x4＋3x3＋4x2＋5x＋6，用秦九韶算法求这个多项式当x＝2时的值时，做了几次乘法？几次加法？[错解] 根据秦九韶算法，把多项式改写成如下形式f(x)＝((((x＋2)x＋3)x＋4)x＋5)x＋6.按照从内到外的顺序，依次计算一次多项式当x＝2时的值：v1＝2＋2＝4；v2＝2v1＋3＝11；v3＝2v2＋4＝26；v4＝2v3＋5＝57；v5＝2v4＋6＝120.显然，在v1中未做乘法，只做了1次加法；在v2，v3，v4，v5中各做了1次加法，1次乘法．因此，共做了4次乘法，5次加法．
误区警示　对秦九韶算法中的运算次数理解错误
在v1中虽然“v1＝2＋2＝4”，而计算机还是做了1次乘法“v1＝2×1＋2＝4”．因为用秦九韶算法计算多项式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0当x＝x0时的值时，首先将多项式改写成f(x)＝(…(anx＋an－1)x＋…＋a1)x＋a0，然后再计算v1＝anx＋an－1，v2＝v1x＋an－2，v3＝v2x＋an－3，…，vn＝vn－1x＋a0.无论an是不是1，这次的乘法都是要进行的．[正解] 由上分析可知，共做了5次乘法，5次加法．