§1.3　算法案例(一)

学习目标　1.了解辗转相除法与更相减损术中的数学原理，并能根据这些原理进行算法分析.2.了解秦九韶算法及利用它提高计算效率的本质.3.对简单的案例能设计程序框图并写出算法程序.

知识点一　求两个数的最大公约数的算法

思考　注意到8251＝6105×1＋2146，那么8251与6105这两个数的公约数和6105与2146的公约数有什么关系？

答案　显然8251与6105的公约数也必是2146的约数，同样6105与2146的公约数也必是8251的约数，所以8251与6105的最大公约数也是6105与2146的最大公约数.

梳理　求两个数的最大公约数有2种算法：

(1)辗转相除法

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

②辗转相除法的算法步骤

第一步，给定两个正整数m，n.

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

第三步，m＝n，n＝r.

第四步，若r＝0，则m，n的最大公约数等于m；

否则，返回第二步.

(2)更相减损术的运算步骤

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

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

知识点二　求n次多项式f(x)＝anxn＋an－1xn－1＋...＋a1x＋a0的值的算法

求n次多项式的值的算法，有一种比较好的算法叫秦九韶算法.

秦九韶算法的一般步骤：

把一个n次多项式f(x)＝anxn＋an－1xn－1＋...＋a1x＋a0改写成如下形式：

(...((anx＋an－1)x＋an－2)x＋...＋a1)x＋a0，求多项式的值时，首先计算最内层括号内一次多