资源简介

算法案例（知识讲解）
课程要求：
1.掌握辗转相除法和更相减损术的原理
2.掌握秦九韶算法的原理，体会它的优越之处
3.了解进位制的原理，能够进行进位制的转化，
辗转相除法
对于给定的两个数，以其中较大的数除以较小的数得到一个余数，将较小的数与余数看成一对新
的数，重复上面的步骤，直到余数为零为止，此时上一步中较小的数即为所求的最大公约数，
例如，求取117和182的最大公约数，按照上述说明得到流程如下：
(117182)→(11765)+(6552)→(5213)→(130)，故13即为所求.
我们将这种求解两个正整数最大公约数的方法称为辗转相除法·
用“辗转相除法"求得459和357的最大公约数是()·
A.3
B.9
C.17
D.51
更相减损术
更相减损术也是求解两个正整数最大公约数的方法.其步骤为：
以两个数中较大的数减去较小的数，以差数和较小的数构成一对新的数，对这一对数再用大数减
小数，以同样的操作一直做下去，直到产生一对相等的数，此数就是这两个数的最大公约数
仍以求117和182的最大公约数为例，按照上述说明进行如下流程：
(117182)+(11765)→(6552)+(5213)+(1339)+(1326)→(1313)，
由于每次操作后得到的两个数与前两个数的最大公约数相同，而且逐渐新减少，故总能得到相等的
两个数，即为所求的最大公约数
2
右边程序框图的算法思路源于我国古代数学名著《九章算术》中的“更相减损术”，执行该程序框
图，若输入a,b分别为14,18，则输出的a=（)·
第1页（共4页）
开始
/输入a,b
是
否
否
√输出u
0-b-4
结火
A.0
B.2
C.4
D.14
三、秦九韶算法
秦九韶算法是用于多项式求值的一种比较有效的算法·
1.秦九韶算法的原理
我国南宋时期的数学家秦九韶针对于多项式求值提出了下面的算法：
把一个n次多项式f代x)=anx”+an-1xn-1+…十a1花十a改写成如下形式：
f(c)=(anen-1十a-1x-2+…十a)x十ao
=(anxn-2+an-1xn-3+…十a2)x十a1)x十a0
==（…(ane+an-1)花+an-2)e+…+a1)x+0
求多项式的值时，先计算最内层括号内的一次多项式的值，即，=anx十an-1,
然后由内向外逐层计算一次多项式的值，
即y=U1花十an-2,%=hE十an-3,…,n=n-1e十0·
这样，求次多项式f()的值就转化为求n个一次多项式的值.
到目前为止，此算法仍然是世界上多项式求值的最先进的算法·
2.秦九韶算法的优点
秦九韶算法与其它算法在计算量上面的比较：
f)=anx”十an-1xn-1+…十1十a0,
第2页（共4页）算法案例（知识讲解）
课程要求：
1.掌握辗转相除法和更相减损术的原理
2.掌握秦九韶算法的原理，体会它的优越之处
3.了解进位制的原理，能够进行进位制的转化，
辗转相除法
对于给定的两个数，以其中较大的数除以较小的数得到一个余数，将较小的数与余数看成一对新
的数，重复上面的步骤，直到余数为零为止，此时上一步中较小的数即为所求的最大公约数，
例如，求取117和182的最大公约数，按照上述说明得到流程如下：
(117182)→(11765)+(6552)→(5213)→(130)，故13即为所求.
我们将这种求解两个正整数最大公约数的方法称为辗转相除法·
用“辗转相除法"求得459和357的最大公约数是()·
A.3
B.9
C.17
D.51
答案
解析
459=357×1+102,357=102×3+51,102=51×2，
51是102和51的最大公约数，也就是459和357的最大公约数.
二、
更相减损术
更相减损术也是求解两个正整数最大公约数的方法.其步骤为：
以两个数中较大的数减去较小的数，以差数和较小的数构成一对新的数，对这一对数再用大数减
小数，以同样的操作一直做下去，直到产生一对相等的数，此数就是这两个数的最大公约数，
仍以求117和182的最大公约数为例，按照上述说明进行如下流程：
(117182)+(11765)+(6552)+(5213)+(1339)→(1326)→(1313)，
第1页（共5页）
由于每次操作后得到的两个数与前两个数的最大公约数相同，而且逐渐减少，故总能得到相等的
两个数，即为所求的最大公约数
2
右边程序框图的算法思路源于我国古代数学名著《九章算术》中的“更相减损术”.执行该程序框
图，若输入4，分别为14,18，则输出的a=()·
开始
输入a,b
是
不
4乃
是
沓
a=b
输出a,
a a-b
b b-a
结束」
A.0
B.2
C.4
D.14
答案
解析
容易看出这个程序的目的是求和的最大公约数，是2
三、
秦九韶算法
秦九韶算法是用于多项式求值的一种比较有效的算法
1.秦九韶算法的原理
我国南宋时期的数学家秦九韶针对于多项式求值提出了下面的算法：
把一个n次多项式f)=anx”十an-1x-1+…十1花+a改写成如下形式：
fx)=(anx-1+an-1xn-2+…十a1)z十ao
=(ann-8+an-1xn-3+…+a2)z+a1)x+a
==（…(an花+an-1)花+an-2)t+…+a1)z+a0,
第2页（共5页）

展开更多......

收起↑