资料简介
第一章 算法初步
§1.3 算法案例（一）
1.理解辗转相除法与更相减损术中的数学原理，并能根据这些原理进行算
法分析；
2.了解秦九韶算法及利用它提高计算效率的本质；
3.对简单的案例能设计程序框图并写出算法程序.
问题导学 题型探究 达标检测
学习目标
知识点一 求两个数的最大公约数的算法
答案
问题导学 新知探究 点点落实
思考 注意到8 251＝6 105×1＋2 146，那么8 251与6 105这两个数的公约
数和6 105与2 146的公约数有什么关系？
答案 显然8 251与6 105的公约数也必是2 146的约数，同样6 105与2 146
的公约数也必是8 251的约数，所以8 251与6 105的最大公约数也是6 105与
2 146的最大公约数.
一般地，求两个数的最大公约数有2种算法：
1.辗转相除法
(1)辗转相除法，又叫欧几里得算法，是一种求两个正整数的 的
古老而有效的算法.
(2)辗转相除法的算法步骤
第一步，给定 .
第二步，计算 .
第三步， .
第四步，若r＝0，则m，n的最大公约数等于 ；
否则，返回 .
答案
最大公约数
两个正整数m，n(m>n)
m除以n所得的余数r
m＝n，n＝r
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＝ ，
v3＝ ，
…
vn＝ ，
这样，求n次多项式f(x)的值就转化为求 的值.
答案 返回
v1x＋an－2
v2x＋an－3
vn－1x＋a0
n个一次多项式
类型一 辗转相除法的现代实现
解析答案反思与感悟
例1 试设计用辗转相除法可以求两个正整数m，n的最大公约数的程序框
图和程序.
题型探究 重点难点 个个击破
解析答案
解 (1)算法：
第一步，给定两个正整数m，n(m>n).
第二步，计算m除以n所得的余数r.
第三步，m＝n，n＝r.
第四步，若r＝0，则m，n的最大公约数等于m；
否则，返回第二步.
(2)程序框图：
反思与感悟
(3)程序：
INPUT m，n
DO
r＝m MOD n
m＝n
n＝r
LOOP UNTIL r＝0
PRINT m
END
反思与感悟
利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对
中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的
数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来
两个数的最大公约数.
反思与感悟
跟踪训练1 用辗转相除法求261和319的最大公约数.
解析答案
解 辗转相除法：
319÷261＝1(余58)，
261÷58＝4(余29)，
58÷29＝2(余0)，
所以319与261的最大公约数为29.
类型二 更相减损术
解析答案反思与感悟
例2 试用程序框图和程序表述更相减损术.
解 程序框图：
程序：
INPUT m，n
WHILE mn
k＝m－n
IF n>k THEN
m＝n
n＝k
ELSE
m＝k
END IF
WEND
PRINT m
END
反思与感悟
利用更相减损术求两个正整数的最大公约数的一般步骤是首先判断两个
正整数是否都是偶数.若是，用2约简，也可以不除以2，直接求最大公约
数，这样不影响最后结果.
跟踪训练2 用更相减损术求261和319的最大公约数.
解 319－261＝58,261－58＝203，
203－58＝145,145－58＝87，
87－58＝29,58－29＝29，
29－29＝0，
所以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＝2 826.2；
v5＝2 826.2×5－0.8＝14 130.2.
∴当x＝5时，多项式的值等于14 130.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＝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.下列说法中正确的个数为( )
①辗转相除法也叫欧几里得算法；
②辗转相除法的基本步骤是用较大的数除以较小的数；
③求最大公约数的方法，除辗转相除法之外，没有其他方法；
④编写辗转相除法的程序时，要用到循环语句.
A.1 B.2 C.3 D.4
C
达标检测 1 2 3 4 5
解析 ①、②、④正确，③错误.
解析答案
2.关于利用更相减损术求156和72的最大公约数，下列说法正确的是( )
A.都是偶数必须约简
B.可以约简，也可以不约简
C.第一步作差为156－72＝84，第二步作差为72－84＝－12
D.以上皆不正确
1 2 3 4 5
B
答案
3.用辗转相除法求210与98的最大公约数需作除法的次数为( )
A.1 B.2 C.3 D.4
1 2 3 4 5
B
答案
4.用更相减损术求147和42的最大公约数是( )
A.6 B.7 C.21 D.42
C
1 2 3 4 5
答案
1 2 3 4 5
5.用秦九韶算法计算多项式f(x)＝6x6＋5x5＋4x4＋3x3＋2x2＋x＋7在x＝0.4
时的值时，需做加法和乘法的次数的和为( )
A.10 B.9 C.12 D.8
C
解析 f(x)＝(((((6x＋5)x＋4)x＋3)x＋2)x＋1)x＋7，
∴加法6次，乘法6次，
∴6＋6＝12次，故选C.
解析答案
规律与方法
1.辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，
若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除
法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最
大公约数.
2.更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，
然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较
小的数相等，此时相等的两数即为原来两个数的最大公约数.
返回
查看更多
Copyright 2004-2019 ttzyw.com All Rights Reserved 闽ICP备18023965号-4
天天资源网声明：本站点发布的文章作品均来自用户投稿或网络整理，部分作品未联系到知识产权人或未发现有相关的知识产权登记