§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－1xn－1＋…＋a1x＋a0改写成如下形式：(…((anx＋an－1)x＋an－2)x＋…＋a1)x＋a0，求多项式的值时，首先计算最内层括号内一次多项式的值，即 v1＝anx ＋ a n－1，然后由内向外逐层计算一次多项式的值，即v2＝v1x ＋ a n－2，v3＝v2x ＋ a n－3，…vn＝vn－1x ＋ a 0这样，求 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 ...
