2015高中数学1.3 算法案例

1.3算法案例

第1课时辗转相除法与更相减损术、秦九韶算法

敖苧教法分析明谋标分条解读观"效法”安

•三维目标

1.知识与技能

(1)理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进

行算法分析.

(2)基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法

程序.

(3)了解秦九韶算法的计算过程，并理解利用秦九韶算法可以减少计算次数

提高计算效率的实质.

2.过程与方法

(1)在辗转相除法与更相减损术求最大公约数的学习过程中对比我们常见的

约分求公因式的方法，比较它们在算法上的区别，并从程序的学习中体会数学的

严谨，领会数学算法计算机处理的结合方式，初步掌握把数学算法转化成计算机

语言的一般步骤.

(2)模仿秦九韶算法，体会古人计算构思的巧妙.

(3)通过对秦九韶算法的学习，了解中国古代数学家对数学的贡献，充分认

识到我国文化历史的悠久.通过对排序法的学习，领会数学计算与计算机计算的

区别，充分认识信息技术对数学的促进.

3.情感、态度与价值观

(1)通过阅读中国古代数学中的算法案例，体会中国古代数学对世界数学发

展的贡献.

(2)在学习古代数学家解决数学问题的方法的过程中培养严谨的逻辑思维能

力，在利用算法解决数学问题的过程中培养理性的精神和动手实践的能力.

・重点难点

重点：理解辗转相除法与更相减损术求最大公约数的方法及秦九韶算法的特

点.

难点：把辗转相除法与更相减损术的方法转换成程序框图与程序语言.

褓希自主持学理数材自查自测画"基础”n上学

习区i

1.通过案例，进一步体会算法的思想.

2.理解辗转相除法、更相减损术、秦九韶算法的原

课标解读

理.（重点）

3.三种算法的框图及程序应用.（难点）

知识”辗转相除法

【问题导思】

1.36与60的最大公约数是多少？你是如何得到的？

【提示】先用两个数公有的质因数连续去除，一直除到所得的商是互质数

23660

2|1830

31915

为止，然后把所有的除数连乘起来即为最大公约数.由于35,

故36与60的最大公约数为2X2X3=12.

2.观察下列等式8251=6105X1+2146,那么8251与6105这两个数的

公约数和6105与2146的公约数有什么关系？

【提示】8251的最大约数是2146的约数，同样6105与2146的公约数

也是8251的约数，故8251与6105的最大公约数也是6105与2146的最大公

约数.

辗转相除法的算法步骤

第一步，给定两个正整数〃八〃.

第二步，计算〃?除以〃所得的余数匚

第三步，m=n,n=r.

第四步，若r=。，则加、”的最大公约数等于如否则返回第三步.

--2|更相减损术

【问题导思】

设两个正整数”?>〃(/">〃)，若m—n=k,则加与"的最大公约数和〃与k的

最大公约数相等，反复利用这个原理，可求得98与63的最大公约数是多少？

【提示198-63=35,63-35=28,35-28=7,28-7=21,21-7=14,14-7

=7,98与63的最大公约数为7.

更相减损术的算法步骤

第一步，任意给定两个正整数，判断它们是否都是偶数.若是,用复约简；

若不是，执行第二步.

第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以

大数减小数.继续这个操作，直到所得的差与减数相等为止,则这个数(等数)或

这个数与约简的数的乘积就是所求的最大公约数.

3j秦九韶算法

将/(x)改写成如下形式：/(x)=(-"((a„x+a„-i)x+a„-2)xH---\-a^x+ao.

具体算法如下：

⑴计算最内层括号内一次多项式的值，即初=。/内斯T.

(2)由内向外逐层计算多项式的值，即

=

V2ViX~t~dn-2)

。3=。2》+即-3，

作专互动探究合作探

破城雄师生互动提“知然"

究区I

用辗转相除法求最大公约数

》例用辗转相除法求228与1995的最大公约数.

【思路探究】使用辗转相除法可根据m=nq+r,反复相除直到r=0为止.

【自主解答】1995=8X228+171,

228=1X171+57,

171=3X57,

•••228与1995的最大公约数为57.

I规律方法I

利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中

较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再

利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公

约数.

〉变武训练

用辗转相除法求779和209的最大公约数.

【解】•“乡:209X3+152,

209=152X1+57,

152=57X2+38,

57=38X1+19,

38=19X2,

••.779与209的最大公约数为19.

：＜用更相减损术求最大公约数

，例用更相减损术求154,484的最大公约数.

【思路探究】解答本题可先将两数约简然后按更相减损术的步骤反复相减

直至得出结果.

【自主解答】154+2=77,484+2=242,下面用更相减损术，求77与242

的最大公约数.

242-77=165,165-77=88,88-77=11,77-11=66,66-11=55,55-11=

44,44-11=33,33-11=22,22-11=11,

故77与242的最大公约数为11,则154与484的最大公约数为11X2=22.

I规律方法I

1.更相减损术进行的是减法运算，即辗转相减，其步骤为若两数同为偶数,

则可用2约简后求最大公约数，也可不用2约简直接求最大公约数.

2.由辗转相除法求最大公约数的步骤较少，而更相减损术使用的是递减运

算，运算简易，便于操作，但步骤较多，两种算法各有所长.

＞变直训练

用更相减损术求576与246的最大公约数.

【解】用2约简576和246得288与123.

288-123=165,165-123=42,

123-42=81,81-42=39,

42-39=3,39-3=36,36-3=33,

33-3=30,30-3=27,

27-3=24,24-3=21,

21-3=18,18-3=15,

15-3=12,12-3=9,

9-3=6,6-3=3.

.'.576与246的最大公约数为3X2=6.

秦九韶算法的应用

，例用秦九韶算法求多项式f(x)=lx1—6x6+4x4+3x3—2X2+X—

5,当x=3时的值.

【思路探究】解答本题首先要将原多项式化成

f(x)=((((((7x-6)x+0)x+4)x+3)x-2)x+l)x-5的形式.其次再弄清v。，V\,

。2,…，。7分别是多少，最后进行计算.

【自主解答】/(x)=((((((7x-6)x+0)x+4)x+3)x-2)x+l)x-5,

伙)=7,01=7X3-6=15;15X3+0=45;03=45X3+4=139;%=

139X3+3=420；05=420X3-2=1258；v6=1258X3+1=3775；07=3775X3

-5=11320.

当x=3时，多项式的值为11320.

I规律方法I

利用秦九韶算法计算多项式的值的关键是能正确地将所给多项式改写，然后

由内向外逐次计算，由于后项计算用到前项的结果，故应认真、细心，确保中间

结果的准确性，若在多项式中有几项不存在，可将这些项的系数看成0,即把这

些项看成0.Z.

＞变式训练

用秦九韶算法计算多项式

f(x)=x6-12?+60x4-160?+240x2-192x+64,当x=2时的值.

【解】将«r)改写为

f(x)=(((((x-12)x+60)x-160)x+240)x-192)x+64,

由内向外依次计算一次多项式当x=2时的值，

00=1，

0=1X2-12=-10,

6=-10X2+60=40,

v3=40X2-160=-80,

。4=-80X2+240=80,

05=80X2-192=-32,

-32X2+64=0.

.\/(2)=0,即x=2时，原多项式的值为0.

易辨易设辨析技能提

巧分辨解找辨误图“P3阱

升区I

对秦九韶算法中的运算次数理解错误

上典例

已知/(X)=X5+2X4+3X3+4X2+5X+6,用秦九韶算法求这个

多项式当x=2时的值时，做了儿次乘法？儿次加法?

【错解】根据秦九韶算法，把多项式改写成如下形式式x)=((((x+2)x+3)x

+4)x+5)x+6.

按照从内到外的顺序，依次计算一次多项式当x=2时的值：01=2+2=4;

。2=20+3=11；03=2勿+4=26；。4=2力+5=57;0=204+6=120.

显然，在V\中未做乘法，只做了1次加法；在火，。3，。4，中各做了1

次加法，1次乘法.因此，共做了4次乘法，5次加法.

【错因分析】在⑦中虽然“0=2+2=4"，而计算机还是做了1次乘法

"2Xl+2=4”.因为用秦九韶算法计算多项式外)=©£'+即一似…+

“ix+“0当x=xo时的值时，首先将多项式改写成/(x)=(…(4"X+a”-i)x+…+a\)x

+ao,然后再计算V\=anx+an-\,v^=v\x+an-2,V3=V2x+an-3,…，vn=vn-\x

+3无论“是不是1，这次的乘法都是要进行的.

【防范措施】1.将多项式写成一次多项式的形式时，如果多项式中〃次项

不存在，可将"次项看作0.Z.

2.直接法乘法运算的次数最多可达(〃；1〃,加法最多〃次,秦九韶算法通

过转化把乘法运算的次数减少到最多n次，加法最多n次.

【正解】由以上分析，共做了5次乘法，5次加法.

c

c

c

c

^

^

c

c

c

c

c

^

€

1.辗转相除法与更相减损术都是求两数最大公约数的方法.

辗转相除法计算次数少，步骤简捷，更相减损术计算次数多，步骤复杂，但

是更相减损术每一步的计算都是减法，比做除法运算要简单一些，一般当数较小

时可以考虑用更相减损术，当数较大时可以考虑用辗转相除法.

2.用秦九韶算法可大大降低乘法的运算次数，提高了运算速度.用此方法

求值，关键是正确地将所给多项式改写，然后由内向外计算，由于后项计算需用

到前项结果，故应认真、细心，确保结果的准确性.

当《双基达标陵堂练生生互动达"双标"uj/[

1.490和910的最大公约数为()

A.2B.10

C.30D.70

【解析】910=490X1+420,490=420X1+70,420=70X6,故最大公约数

为70.

【答案】D

2.用更相减损术求294和84的最大公约数时，需做减法的次数是()

A.2B.3

C.4D.5

【解析】294-84=210,210-84=126,126-84=42,84-42=42.

【答案】C

3.用秦九韶算法求/(X)=2/+X—3当x=3时的值必=.

【解析】/(x)=((2x+0)x+l)x-3,

=2;

0=2X3+0=6;

02=6X3+1=19.

【答案】19

4.用更相减损术求288与153的最大公约数.

【解】288-153=135,153-135=18,135-18=117,117-18=99,99-18

=81,81-18=63,63-18=45,45-18=27,27-18=9,18-9=9.

•••288与153的最大公约数为9.

彳史后知能检测部下测自我评估提“考舷,,整整个

一、选择题

1.下列说法中正确的有()

①辗转相除法也叫欧几里得算法；

②辗转相除法的基本步骤是用较大的数除以较小的数；

③求最大公约数的方法，除辗转相除法之外，没有其他方法；

④编写辗转相除法的程序，要用到循环语句.

A.1个B.2个

C.3个D.4个

【解析】本题考查对辗转相除法和更相减损术的理解与认识.③不正确，

因为除了辗转相除法，还有其他方法，如更相减损术.

【答案】C

2.设计程序框图，用秦九韶算法求多项式的值，主要用哪种结构实现

（）

A.顺序结构B.条件结构

C.循环结构D.条件、顺序结构

【解析】该种算法主要是由内到外计算

Vo=a,

<lt

?«=以-「即+斯-《伙=1,2,…

故在求值时用到循环结构.

【答案】C

3.用秦九韶算法求多项式式幻=4/一?+2当x=3时的值时，需要进行的

乘法运算和加法运算的次数分别为（）

A.4,2B.5,3

C.5,2D.6,2

【解析】儿丫）=4/-f+2=（（（（4x）x）x-l）x）x+2,需5次乘法运算和2次

加法运算.

【答案】C

4.225与135的最大公约数是（）

A.5B.9

C.15D.45

【解析】••,225=135X1+90,135=90X1+45,90=45X2,，45是225与

135的最大公约数.

【答案】D

5.下面一段程序的目的是（）

INPUTm,n

WHILFm<>n

IFm>nTHEN

m=m-n

ELSE

n=n-m

ENDIF

WEND

PRINTm

END

A.求m,n的最小公倍数

B.求m,n的最大公约数

C.求m被n除的商

。.求n除以m的余数

【解析】本程序当m,n不相等时，总是用较大的数减去较小的数，直到

相等时跳出循环，显然是“更相减损术”.故选8.

【答案】B

二、填空题

6.464与272的最大公约数为.

【解析】464^16=29,2724-16=17,29-17=12,17-12=5,12-5=7,7-5=

2,5-2=3,3-2=1,2-1=1,最大公约数为1X16=16.

【答案】16

7.用更相减损术求152与92的最大公约数时，需要做减法的次数是

【解析】；152与92都是偶数，.••先两次用2约简得38与23,又38-

23=15,

23-15=8,

15-8=7,

8-7=1,

7-1=6,

6-1=5,

5-1=4,

4-1=3,

3-1=2,

2-1=1,

故要用10次减法.

【答案】10

8.已知多项式函数f(x)=2x5—5x4—4X3+3X2—6X+7,当x=5时由秦九韶

算法v