§1.3 算法案例
第一课时
辗转相除法与更相减损术､秦九韶算法
自 学 导 引
1.理解辗转相除法与更相减损术的含义,了解执行过程.
2.掌握秦九韶算法的计算过程,了解它在数学计算中的应用.
3.进一步体会算法的基本思想.
课 前 热 身
1.辗转相除法是用于求_____________________的一种方法,这种算法由欧几里得在公元前300年左右首先提出,因而又叫________.
2.所谓辗转相除法,就是对于给定的两个数,用________除以________,若余数不为零,则将___________构成新的一对数,继续上面的除法,直到大数被小数除尽,则这时________就是原来两个数的最大公约数.
两个正整数的最大公约数
欧几里得算法
较大的数
较小的数
除数与余数
除数
3.更相减损术是我国古代数学专著__________中介绍的一种求两数最大公约数的方法.其基本过程是:对于给定的两数,用___________,接着把所得的________与________比较,并以大数减小数,继续这个操作,直到所得的数________为止,则这个数就是所求的最大公约数.
4.秦九韶算法是我国南宋数学家________在他的代表作___________中提出的一种用于计算一元n次多项式的值的方法.
《九章算术》
大数减小数
差
减数
相等
秦九韶
《数书九章》
名 师 讲 解
1.辗转相除法
(1)辗转相除的原理.
设m,n是两个整数(不妨设m>n),用m除以n,若商为q1,余数为r1(0≤r1n>r1>r2>…,所以到某一步必然有ri=ri+1·qi+2,即ri恰能被ri+1整除,这时ri+1是ri和ri+1的公约数,它也必然是ri-1和ri,ri-2和ri-1,…,r1与r2,n和r1,m和n的最大公约数.
(2)辗转相除法的算法分析.
由以上辗转相除法的原理可
以发现,辗转相除法的基本步
骤是用较大的数除以较小的
数,考虑到算法中的赋值语句
可以对同一变量多次赋值,我们可以把较大的数用变量m表示,把较小的数用变量n表示,这样式子m=n·q+r(0≤r(3)任何两个数,用辗转相除法求其最大公约数的程序框图.
由于辗转相除法总是用较大的数去除以较小的数,所以首先要对一开始给定的两数的大小进行判断,并将大数赋给m,小数赋给n,然后再执行下面的过程.程序框图如下图所示:
(4)辗转相除法求两个数的最大公约数的程序设计.
2.更相减损术
(1)更相减损术求两数最大公约数的过程与算法设计:
对于给定的两个数,用较大的数减去较小的数,接着把得到的差与较小的数比较,用这时两个数中的较大的数减去较小的数,继续这样的操作(大数减小数),直到所得的数相等为止,那么这个数(等数)就是所求的最大公约数.
显然,上述过程中大数减去小数是一个重复执行的过程,因此只需将大数赋给变量m,小数赋给变量n,那么m-n就可以通过循环结构实现算法.
(2)更相减损术求最大公约数的程序设计:
3.秦九韶算法
(1)秦九韶算法过程分析:
设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
令vk=(…((anx+an-1)x+an-2)x+…+an-(k-1))x+an-k,
这样我们便可由a0依次求出v1,v2,…,vn:
v1=v0x+an-1,v2=v1x+an-2,v3=v2x+an-3,…,
vn=vn-1x+a0.
显然,用秦九韶算法求n次多项式的值时只需做n次乘法和n次加法运算.
(2)秦九韶算法程序框图:
以5次多项式f(x)=a5x5+a4x4+a3x3+a2x2+a1x+a0当x=x0时为例,如下图:
典 例 剖 析
题型一 求两个数的最大公约数
例1:分别用辗转相除法和更相减损术逐步列出求(1)98和63;(2)8251和6105的最大公约数的步骤,你有什么发现?对优劣作出评判.
分析:辗转相除法是做两个数的带余除法,更相减损术是做两个数的减法.
解:(1)98和63
辗转相除法
S1 98=63 ×1+35,
S2 63=35 ×1+28,
S3 35=28×1+7,
S4 28=4 ×7,
最大公约数为7.
更相减损术
S1 98-63=35,
S2 63-35=28,
S3 35-28=7,
S4 28-7=21,
S5 21-7=14,
S6 14-7=7,
故98和63的最大公约数为7.
(2)8251和6105
辗转相除法
S1 8251=6105×1+2146,
S2 6105=2146×2+1813,
S3 2146=1813×1+333,
S4 1813=333×5+148,
S5 333=148×2+37,
S6 148=37×4,
最大公约数为37.
辗转相除法和更相减损术本质是一致的,除法运算若用加法与减法运算定义,x(x≥0)除以y(y>0)就是从x中一次又一次地减去y,直至x更相减损术
S1 8251-6105=2146,
S2 6105-2146=3959,
S3 3959-2146=1813,
S4 2146-1813=333,
S5 1813-333=1480,
S6 1480-333=1147,
S7 1147-333=814,
S8 814-333=481,
S9 481-333=148,
S10 333-148=185,
S11 185-148=37,
S12 148-37=111,
S13 111-37=74,
S14 74-37=37,
最大公约数为37.
因此(1)中 S4 28=4×7 可作四次减法,即28中可减4次7.
(2)中 S4 1813=333×5+148 在1813中可减5次333.
从形式上看更相减损术比辗转相除法复杂,但计算机更“喜欢”做加减法.加减法比乘除法快几百倍.
变式训练1:用辗转相除法求80和36的最大公约数,并用更相减损术检验所得结果.
分析:将80作为大数,36作为小数,执行辗转相除法和更相减损术的步骤即可.
解:用辗转相除法: 80=36×2+8,
36=8×4+4,
8=4×2+0.
故80和36的最大公约数是4.
用更相减损术检验:80-36=44,
44-36=8,
36-8=28,
28-8=20,
20-8=12,
12-8=4,
8-4=4.
∴80和36的最大公约数是4.
题型二 求三个数的最大公约数
例2:求三个数175､100､75的最大公约数.
分析:求三个数的最大公约数时,可以先求出其中两个数的最大公约数,用这个最大公约数再与第三个数求最大公约数,所得结果就是这三个数的最大公约数.
解:解法1(辗转相除法):先求175与100的最大公约数:
175=100×1+75,
100=75×1+25,
75=25×3.
∴175与100的最大公约数是25.
以下再求25与75的最大公约数:
75=25×3
∴25和75的最大公约数是25.
故25是75和25的最大公约数,也就是175､100､75的最大公约数.
解法2(更相减损术):
第一步:先从较大数中减去较小的数:
175-100=75,100-75=25,得75,25,75;
第二步:重复上面的算法:75-25×2=25,75-2×25=25,得25,25,25.
∵25,25,25的最大公约数为25.
∴三个数175,100,75的最大公约数为25.
注:解法2的过程可简记为
(175,100,75)
=(175-100,100-75,75)
=(75,25,75)
=(75-2×25,25,75-25×2)
=(25,25,25)
∴三个数175,100,25的最大公约数为25.
规律技巧:本题的解法可以推广到求多个数的最大公约数,只需依次计算即可.
变式训练2:求三个数324,243,108的最大公约数.
解:解法1:先求324与243的最大公约数,
324=243×1+81,
243=81×3,
∴324与243的最大公约数为81.
下面再求108与81的最大公约数:
108=81+27,
81=27×3.
∴108与81的最大公约数是27.
故324,243,108的最大公约数为27.
解法2:(324,243,108)
=(324-243,243-108,108)
=(81,135,108)
=(81,135-108,108-81)
=(81,27,27)=(81-2×27,27,27)
=(27,27,27).
∴三个数324,243,108的最大公约数为27.
题型三 秦九韶算法的应用
例3:用秦九韶算法求多项式f(x)=1+x+0.5x2+0.16667x3+0.04167x4+0.00833x5在x=-0.2的值.
分析:可根据秦九韶算法原理,将所给多项式改写,然后由内到外逐次计算即可.
解:f(x)=1+x+0.5x2+0.16667x3+0.04167x4+0.00833x5
=((((0.00833x+0.04167)x+0.16667)x+0.5)x+1)x+1.
而x=-0.2,所以有v0=a5=0.00833,v1=v0x+a4=0.04,
v2=v1x+a3=0.15867,v3=v2x+a2=0.46826,
v4=v3x+a1=0.90635,v5=v4x+a0=0.81873.
即f(-0.2)=0.81873.
误区警示:利用秦九韶算法计算多项式值关键是能正确地将所给多项式改写,然后由内向外逐次计算,由于后项计算需用到前项的结果,故应认真､细心,确保中间结果的准确性.
变式训练3:已知f(x)=x5-4x4+2x2-5x+1,求f(3)的值.
解:f(x)=x5-4x4+0\5x3+2x2-5x+1
=(x4-4x3+0\5x2+2x-5)x+1
=((x3-4x2+0\5x+2)x-5)x+1
=(((x2-4x+0)x+2)x-5)x+1
=((((x-4)x+0)x+2)x-5)x+1.
∵x=3,∴v0=a5=1;
v1=1×3-4=-1;
v2=-1×3+0=-3;
v3=-3×3+2=-7;
v4=-7×3-5=-26;
v5=-26×3+1=-77.
∴f(3)=-77.
技 能 演 练
基础强化
1.用辗转相除法求294和84的最大公约数时,需要做除法的次数是( )
A.1 B.2
C.3 D.4
解析:294=84×3+42,84=42×2.
故需做2次除法.
答案:B
2.两个整数490和910的最大公约数是( )
A.2 B.10
C.30 D.70
解析:910=91×10,490=49×10,
∵91=49×1+42,
49=42×1+7,
42=7×6.
∴91与49的最大公约数为7.
故910与490的最大公约数为70.
答案:D
3.用秦九韶算法计算多项式f(x)=3x6+4x5+5x4+6x3+7x2+8x+1当x=0.4时的值时,需要做乘法和加法的次数分别是( )
A.6,6 B.5,6
C.5,5 D.6,5
解析:∵f(x)的最高次项为3x6,共含有7项,∴用秦九韶算法求x=0.4时的值时,需作乘法和加法各6次.
答案:A
4.用更相减损术求459和357的最大公约数,需作减法的次数为( )
A.4 B.5
C.6 D.7
解析:459-357=102;
357-102=255;
255-102=153;
153-102=51;
102-51=51.
共作了5次减法.
答案:B
5.378与90的最大公约数为________.
解析:378=90×4+18;
90=18×5.
∴378与90的最大公约数是18.
答案:18
6.用秦九韶算法求多项式f(x)=x4-2x3+3x2-7x-5当x=4时的值,给出如下数据:
①0 ②2 ③11 ④37 ⑤143
其运算过程中(包括最终结果)会出现的数有________(只填序号).
答案:②③④⑤
解析:将多项式写成f(x)=(((x-2)x+3)x-7)x-5.
其中v0=a4=1;
v1=1×4-2=2;
v2=2×4+3=11;
v3=11×4-7=37;
v4=37×4-5=143.
解析:由秦九韶算法知,应填an-k.在程序中可以用循环语句来实现.
答案:an-k 循环
8.请将以下用“更相减损术”求两个正整数a,b的最大公约数的程序补充完整:
INPUT a
INPUT b
WHILE a<>b
IF a>b THEN
a=a-b
ELSE
___________
END IF
WEND
PRINT a
END
解析:阅读程序知,当a>b时,作减法a-b,当a答案:b=b-a
能力提升
9.用秦九韶算法求多项式f(x)=8x7+5x6+3x4+2x+1当x=2时的值.
分析:注意本题中有几项不存在,此时在计算时,我们应该将这些项加上,比如含x3这一项可看做0·x3.
解:根据秦九韶算法,把多项式改写成如下形式:
f(x)=8x7+5x6+0·x5+3x4+0·x3+0·x2+2x+1
=((((((8x+5)x+0)x+3)x+0)x+0)x+2)x+1.
而x=2,所以有
v0=8
v1=8×2+5=21,
v2=21×2+0=42,
v3=42×2+3=87,
v4=87×2+0=174,
v5=174×2+0=348,
v6=348×2+2=698,
v7=698×2+1=1397.
∴当x=2时,多项式的值为1397.
10.有甲､乙､丙三种溶液,分别为4200毫升,3220毫升和2520毫升,现要将它们分别全部装入小瓶中,每个瓶子装入液体的体积相同.问:要使所有溶液都刚好装满小瓶中且所用瓶子最少.则小瓶的容积应为多少毫升?
解:由题意可知,就是求这三种溶液体积的最大公约数.
先求4200与3220的最大公约数
4200=3220×1+980,
3220=980×3+280,
980=280×3+140,
280=140×2.
∴4200与3220的最大公约数140.
再求140与2520的最大公约数,2520=140×18.
∴140与2520的最大公约数为140.
综上知,4200,3220和2520的最大公约数为140.
∴小瓶的容积应为140毫升.
品味高考
11.(2008·宁夏模拟)用辗转相除法计算60与48的最大公约数时,需要做的除法次数是( )
A.1 B.2
C.3 D.4
解析:∵60=48×1+12,48=12×4+0.
∴仅需要两步运算.
答案:B
12.(2010·山东模拟)利用秦九韶算法计算函数f(x)=x+2x2+3x3+4x4+5x5的值时,需要做加法､乘法的次数分别为________､________.
解析:将函数变形为
f(x)=((((5x+4)x+3)x+2)x+1)x.
由此可知,共需要做4次加法,5次乘法.
4
5