天添资源网 http://www.ttzyw.com/
1.3 算法案例
第1课时 算法案例(1)
课时目标
1.能用辗转相除法和更相减损术求两个数的最大公约数.
2.能用秦九韶算法求高次多项式的值.
3.掌握古代数学中这两种算法的编程.
识记强化
1.辗转相除法是用于求两个正整数的最大公约数的一种方法,这种算法由欧几里得在公元前300年左右首先提出,因而又叫欧几里得算法.
2.所谓辗转相除法,就是对于给定的两个正整数,用较大数除以较小数.若余数不为零,则将余数和较小数构成新的一对数,继续上面的除法,直到大数被小数除尽,则这时较小数就是原来两个数的最大公约数.
3.更相减损术是我国古代数学专著《九章算术》中介绍的一种求两个正整数最大公约数的方法.其基本过程是:对于给定的两个正整数,判断它们是否都是偶数,若是,用2约简;若不是,用较大数减去较小数,接着把所得的差与较小数比较,并以大数减小数,继续这个操作,直到所得的数相等为止,则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.
4.秦九韶算法是我国南宋数学家秦九韶在他的代表作《数学九章》中提出的一种用于计算一元n次多项式的值的方法.
课时作业
天添资源网 http://www.ttzyw.com/
天添资源网 http://www.ttzyw.com/
一、选择题
1.用更相减损术求36与134的最大公约数,第一步为( )
A.134-36=98
B.134=3×36+26
C.先除以2,得到18与67
D.134÷36=3(余26)
答案:C
解析:利用更相减损术求两个数的最大公约数时,若两个数都是偶数,则首先将两个数都除以2之后再作减法.
2.如果a,b是整数,且a>b>0,r=aMODb,则a与b的最大公约数是( )
A.r B.b
C.b-r D.b与r的最大公约数
答案:D
解析:由题意a=kb+r(k∈N*),即a,b的最大公约数是b与r的最大公约数.
3.98,280的最大公约数为( )
A.7 B.14
C.16 D.8
答案:B
解析:由辗转相除法可得:280=98×2+84,98=84×1+14,84=14×6.故最大公约数为14.也可以使用更相减损术或短除法.
4.用秦九韶算法求n次函数f(x)=anxn+an-1xn-1+…+a1x+a0,在x=x0时的值时,一个反复执行的步骤是( )
A.(k=1,2,…,n)
B.(k=1,2,…,n)
C.(k=1,2,…,n)
D.(k=1,2,…,n)
答案:B
5.用更相减损术求168与360的最大公约数时,需要做的差式运算的次数为( )
A.6 B.7
C.8 D.9
答案:C
6.使用秦九韶算法求P(x)=anxn+an-1xn-1+…+a1x+a0在x=x0时的值可减少运算次数,做加法的次数为( )
天添资源网 http://www.ttzyw.com/
天添资源网 http://www.ttzyw.com/
A.n B.
C.2n+1 D.2n
答案:A
解析:由秦九韶算法的过程可知,做加法的次数为n.
二、填空题
7.三个数30,42,60的最大公约数是________.
答案:6
解析:30=5×6,42=7×6,60=10×6.
8.用秦九韶算法求多项式f(x)=12+35x-8x2+79x3+6x4+5x5+3x6当x=-4时的值时,其中v1的值为________.
答案:-7
9.利用秦九韶算法求P(x)=anxn+an-1xn-1+…+a1x+a0当x=x0时的值可减少运算次数,做乘法的次数为________次.
答案:n
三、解答题
10.用辗转相除法求294与84的最大公约数.
解:用辗转相除法:
294=84×3+42,84=42×2,
即294与84的最大公约数是42.
11.已知函数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=756.
能力提升
12.已知多项式Pn(x)=a0xn+a1xn-1+…+an-1x+an.如果在一种算法中,计算x(k=2,3,4,…,n)的值需要k-1次乘法,计算P3(x0)的值共需要9次运算(6次乘法,3次加法),那么计算Pn(x0)的值共需要________次运算.下面给出一种减少运算次数的算法:P0(x)=a0,Pk+1(x)=xPk(x)+ak+1(k=0,1,2,…,n-1).利用该算法,计算P3(x0)的值共需要6次运算,计算Pn(x0)的值共需要________次运算.
答案:n(n+3) 2n
解析:Pn(x)=a0xn+a1xn-1+…+an-1x+an,共需n
天添资源网 http://www.ttzyw.com/
天添资源网 http://www.ttzyw.com/
次加法运算,每个小因式中所需乘法运算依次为n,n-1,…,1,0.故总运算次数为n+n+(n-1)+…+1=n+=n(n+3).
第二种算法中,P0(x0)=a0不需要运算,P1(x0)=x0P0(x0)+a1,需2次运算,P2(x0)=x0P1(x0)+a2需2+2次运算,依次往下,Pn(x0)需2n次运算.
13.春节快到了,奶奶要给来家里玩的小朋友分糖果,现有大白兔、金丝猴、阿尔卑斯三种糖果,分别重3 600克、4 000克、3 200克.现要将它们分别全部装入小礼品盒中,每个小礼品盒装入的糖果重量相等,问每盒最多装多少克糖果?
解:根据题意求每盒最多装多少克,即求3 600、4 000、3 200的最大公约数,由更相减损术原理即求9、10、8最大公约数与400的积,由更相减损术易求9、10、8最大公约数为1.
所以3 600、4 000、3 200的最大公约数为400,故每盒最多装400克糖果.
天添资源网 http://www.ttzyw.com/