第一章13算法案例一.docx
《第一章13算法案例一.docx》由会员分享,可在线阅读,更多相关《第一章13算法案例一.docx(12页珍藏版)》请在冰点文库上搜索。
![第一章13算法案例一.docx](https://file1.bingdoc.com/fileroot1/2023-4/29/553b3997-1907-412f-918b-32f559dccf23/553b3997-1907-412f-918b-32f559dccf231.gif)
第一章13算法案例一
学习目标
1.理解辗转相除法与更相减损术中的数学原理,并能根据这些原理进行算法分析;2.了解秦九韶算法及利用它提高计算效率的本质;3.对简单的案例能设计程序框图并写出算法程序.
知识点一 求两个数的最大公约数的算法
思考 注意到8251=6105×1+2146,那么8251与6105这两个数的公约数和6105与2146的公约数有什么关系?
答案 显然8251与6105的公约数也必是2146的约数,同样6105与2146的公约数也必是8251的约数,所以8251与6105的最大公约数也是6105与2146的最大公约数.
梳理 一般地,求两个数的最大公约数有2种算法:
(1)辗转相除法
①辗转相除法,又叫欧几里得算法,是一种求两个正整数的最大公约数的古老而有效的算法.
②辗转相除法的算法步骤
第一步,给定两个正整数m,n.
第二步,计算m除以n所得的余数r.
第三步,m=n,n=r.
第四步,若r=0,则m,n的最大公约数等于m;
否则,返回第二步.
(2)更相减损术的运算步骤
第一步,任意给定两个正整数,判断它们是否都是偶数.若是,用2约简;若不是,执行第二步.
第二步,以较大的数减去较小的数,接着把所得的差与较小的数比较,并以大数减小数,继续这个操作,直到所得的数相等为止,则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.
知识点二 求n次多项式f(x)=anxn+an-1xn-1+…+a1x+a0的值的算法
思考 衡量一个算法是否优秀的重要参数是速度.把多项式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 试用辗转相除法求325、130、270的最大公约数.
解 ∵325=130×2+65,130=65×2,∴325与130的最大公约数是65.∵270=65×4+10,65=10×6+5,10=5×2,∴65与270的最大公约数是5,故325、130、270这三个数的最大公约数为5.
反思与感悟 辗转相除法的实质:
对于给定的两个正整数,用较大的数除以较小的数,若余数不为零,则将余数和较小的数构成一对新数,继续上面的除法,直到大数被小数除尽,则这时的小数就是原来两个正整数的最大公约数.
跟踪训练1 用辗转相除法求204与85的最大公约数时,需要做除法的次数是________.
答案 3
解析 用辗转相除法可得204÷85=2……34,85÷34=2……17,34÷17=2,此时可以判断204与85的最大公约数是17,做了3次除法得出结果.
类型二 更相减损术
例2 试用更相减损术求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的个数)为所求的最大公约数.
跟踪训练2 用更相减损术求261和319的最大公约数.
解 ∵319-261=58,
261-58=203,
203-58=145,
145-58=87,
87-58=29,
58-29=29,
∴319与261的最大公约数为29.
类型三 秦九韶算法的基本思想
例3 已知一个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.
反思与感悟 秦九韶算法之所以优秀,一是其对所有多项式求值都适用,二是充分利用已有计算成果,效率更高.
跟踪训练3 用秦九韶算法求多项式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.下列说法中正确的个数为( )
①辗转相除法也叫欧几里得算法;
②辗转相除法的基本步骤是用较大的数除以较小的数;
③求最大公约数的方法除辗转相除法之外,没有其他方法;
④编写辗转相除法的程序时,要用到循环语句.
A.1B.2C.3D.4
答案 C
解析 依据辗转相除法可知,①②④正确,③错误,故选C.
2.用秦九韶算法计算多项式f(x)=6x6+5x5+4x4+3x3+2x2+x+7在x=0.4时的值时,需做加法和乘法的次数的和为( )
A.10B.9C.12D.8
答案 C
解析 f(x)=(((((6x+5)x+4)x+3)x+2)x+1)x+7,
∴做加法6次,乘法6次,∴6+6=12(次),故选C.
3.已知a=333,b=24,则使得a=bq+r(q,r均为自然数,且0≤r<b)成立的q和r的值分别为________.
答案 13,21
解析 用333除以24,商即为q,余数就是r.333÷24=13……21.
4.187和253的最大公约数是________.
答案 11
解析 ∵253=187×1+66,187=66×2+55,66=55×1+11,55=11×5,
∴253和187的最大公约数为11.
5.分别用辗转相除法和更相减损术求1734和816的最大公约数.
解 辗转相除法:
1734=816×2+102,816=102×8.
所以1734与816的最大公约数是102.
更相减损术:
因为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.更相减损术,就是对于给定的两个正整数,用较大的数减去较小的数,然后将差和较小的数构成新的一对数,继续上面的减法,直到差和较小的数相等,此时相等的两数即为原来两个数的最大公约数.
3.用秦九韶算法求多项式f(x)当x=x0的值的思路为
(1)改写;
(2)计算
(3)结论f(x0)=vn.
40分钟课时作业
一、选择题
1.关于辗转相除法,下列说法正确的是( )
A.它和更相减损术一样是求多项式的值的一种方法
B.基本步骤是用较大的数m除以较小的数n得到除式m=nq+r,直到rC.基本步骤是用较大的数m除以较小的数n得到除式m=nq+r(0≤rD.以上说法皆不正确
答案 C
2.1037和425的最大公约数是( )
A.51B.17C.9D.3
答案 B
解析 ∵1037=425×2+187,
425=187×2+51,
187=51×3+34,
51=34×1+17,
34=17×2,
即1037和425的最大公约数是17.
3.利用秦九韶算法求当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
4.45和150的最大公约数和最小公倍数分别是( )
A.5,150B.15,450
C.450,15D.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.下边程序框图的算法思路源于我国古代数学名著《九章算术》中的“更相减损术”.执行该程序框图,若输入的a,b分别为14,18,则输出的a等于( )
A.0B.2C.4D.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.-4B.-1
C.5D.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.31B.93C.217D.651
答案 B
8.已知f(x)=x5+2x3+3x2+x+1,应用秦九韶算法计算当x=3时的值时,v3的值为( )
A.27B.11C.109D.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.辗转相除法程序中有一空请填上.
INPUT “a,b=”;a,b
DO
r=
a=b
b=r
LOOPUNTIL r=0
PRINT a
END
答案 aMODb
解析 MOD用来表示a除以b的余数.
10.用秦九韶算法求多项式6x3+5x2+4x+3的值时,应先将此多项式变形为________.
答案 x(x(6x+5)+4)+3
解析 6x3+5x2+4x+3=(6x2+5x+4)x+3=((6x+5)x+4)x+3.
11.用秦九韶算法求多项式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
12.用辗转相除法求85与51的最大公约数时,需要做除法的次数为________.
答案 3
解析 85=51×1+34,
51=34×1+17,
34=17×2+0.
三、解答题
13.用辗转相除法求80与36的最大公约数,并用更相减损术检验你的结果.
解 80=36×2+8,
36=8×4+4,8=4×2+0,
即80与36的最大公约数是4.
验证:
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.
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.有甲、乙、丙三种溶液分别重147g,343g,133g,现要将它们分别全部装入小瓶中,每个小瓶装入液体的质量相同,每瓶最多装多少克溶液?
解 每个小瓶装的溶液的质量应是三种溶液质量的最大公约数,先求147和343的最大公约数.343-147=196,196-147=49,147-49=98,98-49=49.
所以147和343的最大公约数为49.
同理可求得49与133的最大公约数为7.
所以每瓶最多装7克.