小结PPT专用教学设计内容

§1.3

算法案例(一)

【明目标、知重点】

1．理解辗转相除法与更相减损术中的数学原理，并能根据这些原理进行算法分析．

2．了解秦九韶算法及利用它计算提高计算效率的本质．

3．对简单的案例能设计程序框图并写出算法程序．

【填要点、记疑点】

1．辗转相除法

(1)辗转相除法，又叫欧几里得算法，是一种求两个正整数的最大公约数的古老而有效的算法．

(2)辗转相除法的算法步骤

第一步，给定两个正整数m，n(m>n)．

第二步，计算m除以n所得的余数r. 第三步，m＝n，n＝r. 第四步，若r＝0，则m，n的最大公约数等于m；

否则，返回第二步．

2．更相减损术的运算步骤

第一步，任意给定两个正整数，判断它们是否都是偶数．若是，用2约简；若不是，执行第二步．

第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数．

3．秦九韶算法

把一个n次多项式f(x)＝anxn＋an－1xn1＋…＋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个一次多项式的值．

【探要点、究所然】

[情境导学]

在小学，我们已经学过求最大公约数的知识，利用找公约数的方法来求最大公约数．如果公约数比较大而且根据我们的观察又不能得到一些公约数，我们又应该怎样求它

们的最大公约数？比如求8 251与6 105的最大公约数？这就是我们这一堂课所要探讨的内容．

探究点一

辗转相除法

思考1

18与30的最大公约数是多少？你是怎样得到的？

答

先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来即为最大公约数．

由于，所以，18与30的最大公约数是2×3＝6. 问题

如何求两个正数8 251和6 105的最大公约数？

思考2

对于8 251与6 105这两个数，由于其公有的质因数较大，利用小学的方法求最大公约数就比较困难．注意到8 251＝6 105×1＋2 146，那么8 251与6 105这两个数的公约数和6 105与2 146的公约数有什么关系？

答

显然8 251的最大公约数也必是2 146的约数，同样6 105与2 146的公约数也必是8 251的约数，所以8 251与6 105的最大公约数也是6 105与2 146的最大公约数．

思考3

又6 105＝2 146×2＋1 813，同理，6 105与2 146的公约数和2 146与1 813的公约数相等．重复上述操作，你能得到8 251与6 105这两个数的最大公约数吗？

答

8 251＝6 105×1＋2 146，

6 105＝2 146×2＋1 813，

2 146＝1 813×1＋333，

1 813＝333×5＋148，

333＝148×2＋37，

148＝37×4＋0. 最后的除数37是148和37的最大公约数，也是8 251与6 105的最大公约数．

反思与感悟

上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法．

思考4

(1)用辗转相除法可以求两个正整数m，n的最大公约数，那么用什么逻辑结构来设计算法？其算法步骤如何设计？

(2)该算法的程序框图如何表示？该程序框图对应的程序如何表述？

(3)如果用当型循环结构设计算法，正整数m，n的最大公约数的程序框图和程序分别如何表示？

答

(1)用循环结构设计算法，算法如下：

第一步，给定两个正整数m，n(m>n)．

第二步，计算m除以n所得的余数r.

第三步，m＝n，n＝r. 第四步，若r＝0，则m，n的最大公约数等于m；否则，返回第二步．

(2)

程序框图：

程序：

INPUT m,nDO

r=m MOD nm=nn=r

LOOP UNTIL r=0PRINT mEND

探究点二

更相减损术

思考1

设两个正整数m>n，若m－n＝k，则m与n的最大公约数和n与k的最大公约数相等．反复利用这个原理，可求得98与63的最大公约数为多少？

答

由于63不是偶数，把98和63以大数减小数，并辗转相减，得98－63＝35，

63－35＝28，

35－28＝7，

28－7＝21，

21－7＝14，

14－7＝7. 可知98与63的最大公约数为7. 小结

上述求两个正整数的最大公约数的方法称为更相减损术．

思考2

(1)用更相减损术可以求两个正整数m，n的最大公约数，那么用什么逻辑结构来构造算法？其算法步骤如何设计？

答

(1)用循环结构设计算法，算法如下：

第一步，任意给定两个正整数m，n(m>n)．

第二步，计算m－n所得的差k. 第三步，比较n与k的大小，其中大者用m表示，小者用n表示．

第四步，若m＝n，则m，n的最大公约数等于m；否则，返回第二步．

(2)该算法的程序框图如何表示？该程序框图对应的程序如何表述？

答

程序框图：

程序：

INPUT m,nWHILE m<>nk=m-n

IF n>k THENm=nn=kELSE

m=kEND IFWENDPRINT mEND

例1

分别用辗转相除法和更相减损术求261和319的最大公约数．

解

辗转相除法：

319÷261＝1(余58)，

261÷58＝4(余29)，

58÷29＝2(余0)，

所以319与261的最大公约数为29. 更相减损术：

319－261＝58，

261－58＝203，

203－58＝145，

145－58＝87，

87－58＝29，

58－29＝29，

29－29＝0，

所以319与261的最大公约数是29. 反思与感悟

1.利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数．

2．利用更相减损术求两个正整数的最大公约数的一般步骤是首先判断两个正整数是否都是偶数．若是，用2约简．也可以不除以2，直接求最大公约数，这样不影响最后结果．

跟踪训练1

用辗转相除法求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. 探究点三

秦九韶算法的基本思想

思考1

怎样计算多项式f(x)＝x5＋x4＋x3＋x2＋x＋1当x＝5时的值呢？统计所做的计算的

种类及计算次数分别是什么？

答

f(5)＝55＋54＋53＋52＋5＋1＝3 906.根据我们的计算统计可以得出我们共需要10次乘法运算，5次加法运算．

思考2

我们把多项式变形为f(x)＝((((x＋1)x＋1)x＋1)x＋1)x＋1，再统计一下计算当x＝5时的计算的种类及计算次数分别是什么？

答

从里往外计算仅需4次乘法和5次加法运算即可得出结果．

小结

思考2中的计算比问题1中的计算显然少了6次乘法运算．这种算法就叫秦九韶算法．一般地，

f(x)＝anxn＋an－1xn1＋an－2xn2＋…＋a1x＋a0

－－＝(anxn1＋an－1xn2＋an－2xn3＋…＋a1)x＋a0

－－－＝((anxn2＋an－1xn3＋…＋a2)x＋a1)x＋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个一次多项式的值．

例2

已知一个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＝2 826.2；

v5＝2 826.2×5－0.8＝14 130.2. ∴当x＝5时，多项式的值等于14 130.2. 反思与感悟

秦九韶算法步骤：

跟踪训练2

用秦九韶算法求多项式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＝2 369，

v6＝2 369×3＋1＝7 108，

v7＝7 108×3＝21 324. 故当x＝3时，多项式f(x)＝7x7＋6x6＋5x5＋4x4＋3x3＋2x2＋x的值为21 324. 【当堂测、查疑缺】

1．辗转相除法与更相减损术是求最大公约数的常用方法，从计算结果形式上看，辗转相除法以________________得到结果，更相减损术则以________________而得到结果．

答案

相除余数为零

减数与差相等

2．用辗转相除法求85与51的最大公约数时，需要做除法的次数为________．

答案

3 解析

85＝51×1＋34，

51＝34×1＋17，

34＝17×2＋0. 3．已知f(x)＝2x3＋x－3，用秦九韶算法求当x＝3时v2的值．

解

f(x)＝2x3＋x－3＝2x3＋0·x2＋x－3 ＝((2x＋0)x＋1)x－3，

v0＝2，

v1＝2×3＋0＝6，

v2＝6×3＋1＝19. 【呈重点、现规律】

1．辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约数．

2．更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公约数．

3．用秦九韶算法求多项式f(x)当x＝x0的值的思路为①改写；②计算v0＝an；③结论f(x0)＝vn.vk＝vk－1x0＋an－kk＝1，2，…，n

课