1.3 中国古代数学中的算法案例
学习目标 1.理解更相减损之术中的数学原理,并能根据这些原理进行算法分析.2.理解割圆术中蕴含的数学原理.3.了解秦九韶算法及利用它提高计算效率的本质.4.对简单的案例能设计程序框图并写出算法.
知识点一 更相减损之术
更相减损之术的运算步骤
第一步,任意给定两个正整数,判断它们是否都是偶数.若是,用2约简;若不是,执行第二步.
第二步,以较大的数减去较小的数,接着把所得的差与较小的数比较,并以大数减小数,继续这个操作,直到所得的数相等为止,则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.
知识点二 割圆术
1.割圆术的算法
S1 假设圆的半径为1,面积为S,圆内接正n边形面积为Sn,边长为xn,边心距为hn,先从圆内接正六边形的面积开始算起,即n=6,则正六边形的面积S6=6×;
S2 利用公式S2n=Sn+n··xn(1-hn)重复计算,就可得到正十二边形、正二十四边形…的面积.因为圆的半径为1,所以随着n的增大,S2n的值不断趋近于圆周率,这样不断计算下去,就可以得到越来越精密的圆周率近似值.
2.割圆术的算法思想
刘徽从圆内接正六边形开始,让边数逐次加倍,逐个算出这些圆内接正多边形的面积,从而得到一系列逐渐递增的数值,来一步一步地逼近圆面积,最后求出圆周率的近似值.用刘徽自己的话概括就是“割之弥细,所失弥少,割之又割,以至于不可割,则与圆合体而无所失矣.”
知识点三 秦九韶算法
思考 衡量一个算法是否优秀的重要参数是速度.把多项式f(x)=x5+x4+x3+x2+x+1变形为f(x)=((((x+1)x+1)x+1)x+1)x+1,然后求当x=5时的值,为什么比常规逐项计算省时?
答案 从里往外计算,充分利用已有成果,可减少重复计算.
梳理 秦九韶算法的一般步骤:
把一个n次多项式f(x)=anxn+an-1xn-1+…+a1x+a0改写成如下形式:
(…((anx+an-1)x+an-2)x+…+a1)x+a0,求多项式的值时,首先计算最内层括号内一次多项式的值,即v1=anx+an-1,然后由内向外逐层计算一次多项式的值,即
v2=v1x+an-2,
v3=v2x+an-3,
…
vn=vn-1x+a0,
这样,求n次多项式f(x)的值就转化为求n个一次多项式的值.
1.辗转相除法的基本步骤是用较大的数除以较小的数.( √ )
2.求最大公约数的方法除辗转相除法之外,没有其他方法.( × )
3.编写辗转相除法的程序时,要用到循环语句.( √ )
题型一 更相减损之术
例1 试用更相减损之术求612,396的最大公约数.
解 方法一 612÷2=306,396÷2=198,306÷2=153,198÷2=99,∴153-99=54,99-54=45,54-45=9,45-9=36,36-9=27,27-9=18,18-9=9.所以612,396的最大公约数为9×22=36.
方法二 612-396=216,396-216=180,216-180=36,180-36=144,144-36=108,108-36=72,72-36=36.故36为612,396的最大公约数.
反思与感悟 用更相减损之术的算法步骤:
第一步,给定两个正整数m,n,不妨设m>n.
第二步,若m,n都是偶数,则不断用2约简,使它们不同时是偶数,约简后的两个数仍记为m,n.
第三步,d=m-n.
第四步,判断“d≠n”是否成立,若是,则将n,d中的较大者记为m,较小者记为n,返回第三步;否则,2kd(k是约简整数2的个数)为所求的最大公约数.
跟踪训练1 用更相减损之术求261和319的最大公约数.
解 ∵319-261=58,
261-58=203,
203-58=145,
145-58=87,
87-58=29,
58-29=29,
∴319与261的最大公约数为29.
题型二 秦九韶算法的基本思想
例2 已知一个5次多项式为f(x)=4x5+2x4+3.5x3-2.6x2+1.7x-0.8,用秦九韶算法求这个多项式当x=5时的值.
解 将f(x)改写为
f(x)=((((4x+2)x+3.5)x-2.6)x+1.7)x-0.8,
由内向外依次计算一次多项式当x=5时的值:
v0=4;v1=4×5+2=22;
v2=22×5+3.5=113.5;
v3=113.5×5-2.6=564.9;
v4=564.9×5+1.7=2826.2;
v5=2826.2×5-0.8=14130.2.
∴当x=5时,多项式的值为14130.2.
反思与感悟 秦九韶算法之所以优秀,一是其对所有多项式求值都适用,二是充分利用已有计算成果,效率更高.
跟踪训练2 用秦九韶算法求多项式f(x)=7x7+6x6+5x5+4x4+3x3+2x2+x当x=3时的值.
解 f(x)=((((((7x+6)x+5)x+4)x+3)x+2)x+1)x,
所以有v0=7,
v1=7×3+6=27,
v2=27×3+5=86,
v3=86×3+4=262,
v4=262×3+3=789,
v5=789×3+2=2369,
v6=2369×3+1=7108,
v7=7108×3=21324.
故当x=3时,多项式f(x)=7x7+6x6+5x5+4x4+3x3+2x2+x的值为21324.
1.用秦九韶算法计算多项式f(x)=6x6+5x5+4x4+3x3+2x2+x+7在x=0.4时的值时,需做加法和乘法的次数的和为( )
A.10 B.9 C.12 D.8
答案 C
解析 f(x)=(((((6x+5)x+4)x+3)x+2)x+1)x+7,
∴做加法6次,乘法6次,
∴6+6=12(次),故选C.
2.已知f(x)=2x3+x-3,用秦九韶算法求当x=3时v2的值.
解 f(x)=2x3+x-3=2x3+0·x2+x-3
=((2x+0)x+1)x-3,
v0=2,v1=2×3+0=6,
v2=6×3+1=19.
3.用更相减损之术求1734和816的最大公约数.
解 因为1734和816都是偶数,所以分别除以2得867和408.
867-408=459,459-408=51,408-51=357,
357-51=306,306-51=255,255-51=204,
204-51=153,153-51=102,102-51=51.
所以867和408的最大公约数是51,故1734和816的最大公约数是51×2=102.
1.更相减损之术,就是对于给定的两个正整数,用较大的数减去较小的数,然后将差和较小的数构成新的一对数,继续上面的减法,直到差和较小的数相等,此时相等的两数即为原来两个数的最大公约数.
2.用秦九韶算法求多项式f(x)当x=x0的值的思路为(1)改写;(2)计算
(3)结论f(x0)=vn.
一、选择题
1.1037和425的最大公约数是( )
A.51 B.17 C.9 D.3
答案 B
2.利用秦九韶算法求当x=2时,f(x)=1+2x+3x2+4x3+5x4+6x5的值,下列说法正确的是( )
A.先求1+2×2
B.先求6×2+5,第二步求2×(6×2+5)+4
C.用f(2)=1+2×2+3×22+4×23+5×24+6×25直接运算求解
D.以上都不正确
答案 B
3.45和150的最大公约数和最小公倍数分别是( )
A.5,150 B.15,450
C.450,15 D.15,150
答案 B
4.用秦九韶算法计算f(x)=6x5-4x4+x3-2x2-9x,需要加法(或减法)与乘法运算的次数分别为( )
A.5,4 B.5,5 C.4,4 D.4,5
答案 D
解析 n次多项式,当最高次项的系数不为1时,需进行n次乘法;若各项均不为0,则需进行n次加法(或减法),缺一项就减少一次加法(或减法)运算,而这个5次多项式的5次项系数不为1,缺常数项,因而乘法次数为5,加法(或减法)次数为5-1=4.故选D.
5.下面程序框图的算法思路源于我国古代数学名著《九章算术》中的“更相减损之术”.执行该程序框图,若输入的a,b分别为14,18,则输出的a等于( )
A.0 B.2 C.4 D.14
答案 B
解析 开始:a=14,b=18,
第一次循环:a=14,b=4;第二次循环:a=10,b=4;
第三次循环:a=6,b=4;第四次循环:a=2,b=4;
第五次循环:a=2,b=2.
此时,a=b,退出循环,输出a=2.
6.用秦九韶算法求多项式f(x)=1+2x+x2-3x3+2x4当x=-1时的值时,v2的结果是( )
A.-4 B.-1 C.5 D.6
答案 D
解析 此题的n=4,a4=2,a3=-3,a2=1,a1=2,a0=1,由秦九韶算法的递推关系式
得v1=v0x+a3=2×(-1)-3=-5,
v2=v1x+a2=-5×(-1)+1=6,
故选D.
7.三个数4557,1953,5115的最大公约数是( )
A.31 B.93 C.217 D.651
答案 B
8.已知f(x)=x5+2x3+3x2+x+1,应用秦九韶算法计算当x=3时的值时,v3的值为( )
A.27 B.11 C.109 D.36
答案 D
解析 将函数式化成如下形式,
f(x)=((((x+0)x+2)x+3)x+1)x+1.
由内向外依次计算:
v0=1,
v1=1×3+0=3,
v2=3×3+2=11,
v3=11×3+3=36,
v4=36×3+1=109,
v5=109×3+1=328.
二、填空题
9.自然数8251和6105的最大公约数为________.
答案 37
解析 利用更相减损之术可得它们的最大公约数为37.
10.用秦九韶算法求多项式6x3+5x2+4x+3的值时,应先将此多项式变形为________.
答案 ((6x+5)x+4)x+3
解析 6x3+5x2+4x+3=(6x2+5x+4)x+3
=((6x+5)x+4)x+3.
11.用更相减损之术求459和357的最大公约数,需进行减法的次数为________.
答案 5
解析 利用更相减损之术,有459-357=102,357-102=255,255-102=153,153-102=51,102-51=51,共进行了5次减法.
12.用秦九韶算法求多项式f(x)=2+0.35x+1.8x2-3.66x3+6x4-5.2x5+x6在x=-1.3时的值时,令v0=a6,v1=v0x+a5,…,v6=v5x+a0时,v3的值为________.
答案 -22.445
三、解答题
13.求三个数72,120,168的最大公约数.
解 (更相减损之术):
先求120,168的最大公约数.
168-120=48,120-48=72,72-48=24,48-24=24,
所以120,168的最大公约数为24.
再求72,24的最大公约数.
72-24=48,48-24=24,
所以72,24的最大公约数为24,
即72,120,168的最大公约数为24.
14.用秦九韶算法求多项式f(x)=4x5+3x4+5x3+x2+x当x=2时的值.
解 因为f(x)=((((4x+3)x+5)x+1)x+1)x,
所以v0=4,
v1=4×2+3=11,
v2=11×2+5=27,
v3=27×2+1=55,
v4=55×2+1=111,
v5=111×2=222.
所以当x=2时,多项式f(x)=4x5+3x4+5x3+x2+x的值为222.
四、探究与拓展
15.秦九韶是我国南宋时期的数学家,普州(现四川省安岳县)人,他在所著的《数书九章》中提出的多项式求值的秦九韶算法,至今仍是比较先进的算法.如图所示的程序框图给出了利用秦九韶算法求某多项式值的一个实例,若输入n,x的值分别为3,2,则输出v的值为( )
A.9 B.18
C.20 D.35
答案 B
解析 初始值n=3,x=2,
程序运行过程如下:
v=1
i=2 v=1×2+2=4
i=1 v=4×2+1=9
i=0 v=9×2+0=18
i=-1 跳出循环,输出v=18,故选B.
16.用秦九韶算法求多项式f(x)=x5+0.11x3-0.15x-0.04当x=0.3时的值.
解 将f(x)写为f(x)=((((x+0)·x+0.11)x+0)x-0.15)x-0.04.
按从内到外的顺序,依次计算多项式的值:
v0=1,
v1=1×0.3+0=0.3,
v2=0.3×0.3+0.11=0.2,
v3=0.2×0.3+0=0.06,
v4=0.06×0.3-0.15=-0.132,
v5=-0.132×0.3-0.04=-0.0796.
∴当x=0.3时,f(x)的值为-0.0796.