(共32张PPT)
第11章 算法初步
第11章 算法初步
较大数
较小数
余数和较小数
较小数
×
√
本部分内容讲解结束
按ESC键退出全屏播放
A
预习案,自生学习
研读·思考·尝试11.4 算法案例
1.理解辗转相除法与秦九韶算法的含义，了解其执行过程. 2.掌握用算法解决实际问题.
1.辗转相除法
所谓辗转相除法，就是对于给定的两个正整数，用较大数除以较小数Ｗ.若余数不为零，则将余数和较小数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小数就是原来两个数的最大公约数.
伪代码如下：
INPUT a，bDO
r＝a
MOD
b
a＝b
b＝rLOOP
UNTIL r＝0PRINT aEND
2.秦九韶算法
秦九韶算法其实质是通过一次式的反复计算，逐步得出高次多项式的值，对于一个n次多项式，最多只需做n次乘法和n次加法即可.
伪代码如下：
INPUT “n＝”；nINPUT “an＝”；aINPUT “x＝”；xv＝ak＝n－1WHILE k>＝0
PRINT “k＝”；k
INPUT “ak＝”；a
v＝v
x＋a
k＝k－1WENDPRINT vEND
1.判断正误.(对的打“√”，错的打“×”)
(1)求两个正整数的最大公约数可以用辗转相除法.( )
(2)利用秦九韶算法计算时，乘法运算与加法运算次数相等.( )
答案：(1)√ (2)×
2.用秦九韶算法计算多项式f(x)＝3x6＋4x5＋5x4＋6x3＋7x2＋8x＋1当x＝0.4时的值时，需要做乘法和加法的次数分别是( )
A.6，6
B.5，6
C.5，5
D.6，5
答案：A
3.“辗转相除法”与“更相减损术”有何区别？
解：辗转相除法的操作过程是先用两个数中较大的数除以较小的数，得商和余数；再用除数除以余数，重复操作，直到出现余数为零，则这个最小除数就是两个数的最大公约数；而更相减损术是用较大数减去较小数，再把差与较小数作为一对相减直至差相等为止，则这个等数就是所求的最大公约数.
辗转相除法[学生用书P22]
利用辗转相除法求46，115和276的最大公约数.
【解】 求三个数的最大公约数，可以先求两个数的最大公约数，然后求第三个数与前两个数的最大公约数.
276＝2×115＋46，115＝2×46＋23，46＝23×2，
所以276与115的最大公约数为23.
又46与23的最大公约数为23，
所以46、115和276的最大公约数为23.
利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数.
1.378与90的最大公约数为 Ｗ.
解析：辗转相除法：
378＝90×4＋18，
90＝18×5＋0，
所以378与90的最大公约数是18.
答案：18
二分法[学生用书P22]
写出用二分法求方程x3－2x－3＝0在区间[1，2]内的一个近似解(误差不超过0.001)的一个算法.
【解】 算法如下：
S1：令f(x)＝x3－2x－3，a＝1，b＝2，c＝0.001；
S2：取x0＝；
S3：若|a－b|≥c，则进入S4；否则输出x0结束算法；
S4：若f(x0)≠0，则进入S5；否则x＝x0就是方程的根，输出x0，结束算法；
S5：若f(x0)f(a)>0，则解在[x0，b]中，用x0替换a；
若f(x0)f(a)<0，则解在[a，x0]中，用x0替换b，返回S2.
用二分法求方程的近似解的步骤
(1)画草图探索解所在的区间；
(2)用二分法求符合限制条件的解；
(3)编制伪代码用计算机完成.
2.写出用二分法求方程x2－2＝0的一个正的近似解(误差不超过0.005)的算法.
解：算法如下：
S1：令f(x)＝x2－2，因为f(1)<0，f(2)>0，
所以令a＝1，b＝2，c＝0.005；
S2：取x0＝；
S3：若|a－b|≥c，则进入S4；否则输出x0结束算法；
S4：若f(x0)≠0，则进入S5；否则x＝x0就是方程的根，输出x0，结束算法；
S5：若f(a)·f(x0)>0，则解在[x0，b]，用x0替换a；若f(x0)f(a)<0，则解在[a，x0]，用x0替换b；返回S2.
秦九韶算法[学生用书P23]
用秦九韶算法计算多项式f(x)＝x6－12x5＋60x4－160x3＋240x2－192x＋64当x＝2时的值.
【解】 将f(x)改写为
f(x)＝(((((x－12)x＋60)x－160)x＋240)x－192)x＋64.
由内向外依次计算一次多项式当x＝2时的值，
v0＝1，
v1＝1×2－12＝－10，
v2＝－10×2＋60＝40，
v3＝40×2－160＝－80，
v4＝－80×2＋240＝80，
v5＝80×2－192＝－32，
v6＝－32×2＋64＝0，
所以f(2)＝0，
即x＝2时，
原多项式的值为0.
秦九韶算法的步骤
3.已知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.选D.
1.辗转相除法是当大数被小数除尽时，结束除法运算，较小的数就是最大公约数.
2.用秦九韶算法可大大降低乘法的运算次数，提高了运算速度.用此方法求值，关键是正确地将所给多项式改写，然后由内向外计算，由于后项计算需用到前项结果，故应认真、细心，确保结果的准确性.
(1)求两个正数的公约数，当两数差别较大时，用辗转相除法，当两数差别不大时，用更相减损术较快.
(2)利用秦九韶算法计算多项式值的关键是能准确地将多项式改写，然后由内向外逐次计算.由于后项计算用到前项的结果，故应认真、细心，确保每项计算结果的准确性.
1.用辗转相除法求36与134的最大公约数，第一步是( )
A.134－36＝98
B．134＝3×36＋26
C.先除以2，得到18与67
D．134÷36＝3(余26)
解析：选B.用辗转相除法求36与134的最大公约数的第一步是计算较大数134除以较小数36的余数.
2.用秦九韶算法求多项式f(x)＝4x5－x2＋2当x＝3时的值时，需要进行的乘法运算和加减运算的次数分别为( )
A.4，2
B．5，3
C.5，2
D．6，2
解析：选C.f(x)＝4x5－x2＋2＝((((4x)x)x－1)x)x＋2，所以需要5次乘法运算和2次加减运算.
3.已知多项式p(x)＝3x5＋9x4＋x3＋kx2＋4x＋11，当x＝3时值为1
616，则k＝ Ｗ.
解析：由秦九韶算法，得
p(x)＝((((3x＋9)x＋1)x＋k)x＋4)x＋11.
则当x＝3时，p(3)＝(((54＋1)×3＋k)×3＋4)×3＋11
＝(495＋3k＋4)×3＋11
＝9k＋1
508
＝1
616，
所以k＝12.
答案：12
4.运行下面的伪代码：
INPUT m，nDO r＝m
MOD
n m＝n n＝rLOOP
UNTIL r＝0PRINT mEND
当输入168，72时，输出的结果是 Ｗ.
解析：这个伪代码的作用是求m，n的最大公约数.
故168＝72×2＋24，
72＝24×3.
所以，168与72的最大公约数是24.
答案：24
5.已知一个一元五次多项式为f(x)＝5x5＋2x4＋3.5x3－2.6x2＋1.7x－0.8，用秦九韶算法求这个多项式当x＝5时的值.
解：f(x)＝5x5＋2x4＋3.5x3－2.6x2＋1.7x－0.8
＝((((5x＋2)x＋3.5)x－2.6)x＋1.7)x－0.8，
v1＝5×5＋2＝27，
v2＝27×5＋3.5＝138.5，
v3＝138.5×5－2.6＝689.9，
v4＝689.9×5＋1.7＝3
451.2，
v5＝3
451.2×5－0.8＝17
255.2.
所以，当x＝5时，
多项式的值等于17
255.2.
[A 基础达标]
1.4
830与3
289的最大公约数为( )
A.23
B．35
C.11
D．13
解析：选A.4
830＝1×3
289＋1
541；
3
289＝2×1
541＋207；
1
541＝7×207＋92；
207＝2×92＋23；92＝4×23；
所以23是4
830与3
289的最大公约数.
2.有关辗转相除法下列说法正确的是( )
A.它和更相减损之术一样是求多项式值的一种方法
B.基本步骤是用较大的数m除以较小的数n得到除式m＝nq＋r，直至r＜n为止
C.基本步骤是用较大的数m除以较小的数n得到除式m＝qn＋r(0≤r＜n)，反复进行，直到r＝0为止
D.以上说法皆错
答案：C
3.用秦九韶算法求多项式f(x)＝7x6＋6x5＋3x2＋2，当x＝4时，先算的是( )
A.4×4＝16
B．7×4＝28
C.4×4×4＝64
D．7×4＋6＝34
解析：选D.因为f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0＝(…((anx＋an－1)x＋an－2)x＋…＋a1)x＋a0，所以用秦九韶算法求多项式f(x)＝7x6＋6x5＋3x2＋2当x＝4的值时，先算的是7×4＋6＝34.
4.45和150的最大公约数和最小公倍数分别是( )
A.5，150
B．15，450
C.450，15
D．15，150
解析：选B.利用辗转相除法求45和150的最大公约数：150＝45×3＋15，45＝15×3，所以45和150的最大公约数为15.所以45和150的最小公倍数为15×(45÷15)×(150÷15)＝450，故选B.
5.用秦九韶算法计算f(x)＝6x5－4x4＋x3－2x2－9x时，需要做加法(或减法)与乘法运算的次数分别为( )
A.5，4
B．5，5
C.4，4
D．4，5
解析：选D.n次多项式需进行n次乘法运算；若各项的系数均不为零，则需进行n次加法(或减法)运算，缺一项就减少一次加法(或减法)运算.f(x)中无常数项，故加法(或减法)运算要减少一次，为5－1＝4(次)，乘法运算的次数为5.故选D.
6.用辗转相除法求得375和85的最大公约数为 Ｗ.
解析：375＝85×4＋35，
85＝35×2＋15，
35＝15×2＋5，
15＝5×3＋0.
所以375与85的最大公约数为5.
答案：5
7.按秦九韶算法，多项式f(x)＝4x6＋2x5＋3.5x4＋3x3－2.5x2＋2x－750，当x＝3时的值为 Ｗ.
解析：v0＝4，
v1＝4×3＋2＝14，
v2＝14×3＋3.5＝45.5，
v3＝45.5×3＋3＝139.5，
v4＝139.5×3－2.5＝416，
v5＝416×3＋2＝1
250，
v6＝1
250×3－750＝3
000.
答案：3
000
8.已知函数f(x)＝x3－2x2－5x＋6，用秦九韶算法，则f(10)＝ Ｗ.
解析：f(x)＝x3－2x2－5x＋6
＝(x2－2x－5)x＋6
＝((x－2)x－5)x＋6.
当x＝10时，f(10)＝((10－2)×10－5)×10＋6
＝(8×10－5)×10＋6
＝75×10＋6＝756.
答案：756
9.现有长度为2.4米和5.6米两种规格的钢筋若干，要焊接一批正方体模型，问怎样设计才能保证正方体的体积最大且不浪费材料？
解：用辗转相除法步骤如下：
5.6＝2.4×2＋0.8，
2.4＝0.8×3，
所以5.6与2.4的最大公约数为0.8，
因此将正方体的棱长设为0.8米时，正方体的体积最大且不浪费材料.
10.古时候，当边境有敌人来犯时，守边的官兵通过在烽火台上点火向境内报告来犯敌人数，如图所示，烽火台上点火表示数字1，未点火表示数字0，约定二进制数对应的十进制数的单位是1
000，请你计算一下，这组烽火台表示有多少敌人入侵？
解：由题图可知这组烽火台表示的二进制数为11011(2)，它表示的十进制数为11011(2)＝1×24＋1×23＋0×22＋1×21＋1×20＝27，由于约定二进制数对应的十进制数的单位是1
000，所以入侵的敌人的数目为27×1
000＝27
000(人).
[B 能力提升]
11.下面一段伪代码的功能是( )
INPUT m，nWHILE m<>n
IF m>n THEN m＝m－n
ELSE
n＝n－m
END IFWENDPRINT mEND
A.求m，n的最小公倍数
B.求m，n的最大公约数
C.求m被n除的商
D.求n除以m的余数
解析：选B.本伪代码当m，n不相等时，总是用较大的数减去较小的数，直到相等时跳出循环，显然是“更相减损术”.故选B.
12.用秦九韶算法计算多项式f(x)＝12＋35x－8x2＋79x3＋6x4＋5x5＋3x6在x＝－4时的值时，v3的值为 Ｗ.
解析：首先，将多项式按降幂排列得f(x)＝3x6＋5x5＋6x4＋79x3－8x2＋35x＋12，所以v0＝3，v1＝v0x＋5，v2＝v1x＋6，v3＝v2x＋79，逐层代入可得v3＝－57.
答案：－57
13.用辗转相除法求459和357的最大公约数.
解：459＝357×1＋102，
357＝102×3＋51，
102＝51×2，
所以最大公约数为51.
14.（选做题）利用秦九韶算法分别计算f(x)＝8x7＋5x6＋3x4＋2x＋1在x＝2与x＝－1时的值，并判断多项式f(x)在区间[－1，2]有没有零点.
解：因为f(x)＝8x7＋5x6＋3x4＋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＝1
397.
所以当x＝2时，f(x)＝1
397.
同理可求当x＝－1时，f(x)＝－1，
又因为f(－1)f(2)＝－1
397<0，
则多项式f(x)在区间[－1，2]上有零点.
PAGE
1(共19张PPT)
本部分内容讲解结束
按ESC键退出全屏播放
A
