1.3　中国古代数学中的算法案例（人教B必修3）

课件19张PPT。【课标要求】
1．了解割圆术中无限逼近的数学思想．
2．理解更相减损术的含义，了解其执行过程．
3．掌握秦九韶算法的计算过程，并了解它提高计算效率
的实质．
【核心扫描】
1．三种算法的原理及应用．(重难点)
2．三种算法的框图表示及程序．(难点)
3秦九韶算法中多项式的改写．(易错点)
1.3　中国古代数学中的算法案例更相减损术
第一步，任意给定两个正整数，判断它们是否都是____．若是，用______；若不是，执行_______．
第二步，以_____的数减去_____的数，接着把所得的差与_____的数比较，并以大数减小数，继续这个操作，直到所得的数_____为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数．
自学导引1．偶数2约简第二步较大较小较小相等割圆术的算法思想
刘徽从圆内接正六边形开始，让边数逐次加倍，逐个算出这些圆内接正多边形的面积，从而得到一系列逐渐递增的数值，来一步一步逼近圆面积，最后求出圆周率的近似值．用刘徽自己的话概括就是“割之弥细，所失弥少，割之又割，以至于不可割，则与圆合体而无所失矣．”
2．秦九韶算法
把一个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)的值就转化为求______________的值．
3．最内层括号内v0x＋an－1v1x＋an－2v2x＋an－3vn－1x＋a0n个一次多项式 秦九韶算法有哪些优点？
提示　秦九韶算法有以下几个优点：
①大大减少了乘法的次数，使计算量减小．在计算机上做一次乘法所需要的时间是做加法、减法的几倍到十几倍，减少做乘法的次数也就加快了计算的速度；
②规律性强，便于利用循环语句来实现算法；
③避免了对自变量x单独做幂的计算，每次都是计算一个一次多项式的值，从而可以提高计算的精度．
更相减损术的算法步骤：
S1　输入两个正整数a，b.
S2　判断a是否等于b，若a不等于b，执行S3；否则执行S4.
S3　判断a是否大于b，若是将a－b的值赋给a，转回S2；若不是，将b－a的值赋给b，转回S2.
S4　输出a，b的值．
名师点睛1．2．秦九韶算法
(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.
S1　计算最内层anx＋an－1的值，将anx＋an－1的值赋给一?
3．个变量v1(为方便将an赋予变量v0)；
S2　计算(anx＋an－1)x＋an－2的值，可以改写为v1x＋an－2，将v1x＋an－2的值赋给一个变量v2；
依次类推，即每一步的计算之后都赋予一个新值vk，即从最内层的括号到最外层．
括号的值依次赋予变量v1，v2，…，vk，…，vn，第n步所求值vn＝vn－1x＋a0即为所求多项式的值．
题型一　求两个正整数的最大公约数 用更相减损术求261和319的最大公约数．
[思路探索] 使用更相减损术则可根据m－n＝r，反复执行，直到n＝r为止．
解　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，直接求最大公约数，这样不影响最后结果．
用更相减损术求80和36的最大公约数．
解　80÷2＝40　36÷2＝18
40÷2＝20　18÷2＝9
20—9＝11　11－9＝2
9－2＝7　7－2＝5
5－2＝3　3－2＝1
2－1＝1　1×2×2＝4
所以80与36的最大公约数为4.
【变式1】 用秦九韶算法求f(x)＝3x5＋8x4－3x3＋5x2＋12x－6，当x＝2的值．
题型二　秦九韶算法在多项式中的应用【例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次多项式当最高次项的系数不为1时，需进行n次乘法；若各项均不为零，则需进行n次加法，缺一项就减少一次加法运算．f(x)中无常数项，故加法次数要减少一次，为5－1＝4.故选D.
答案　D
【变式2】 已知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次加法．
单击此处进入 活页规范训练