1.3 算法案例辗转相除法与更相减损术[提出问题]问题 1：如何求 18 与 54 的最大公约数？提示：短除法．问题 2：要求 6 750 与 3 492 的最大公约数，上述法还好用吗？提示：数值太大，短除法不方便用．问题 3：还有没有其他方法，可用来解决“问题 2”中的问题？提示：有．[导入新知]1．辗转相除法(1)辗转相除法，又叫欧几里得算法，是一种求两个正整数的最大公约数的古老而有效的算法．(2)辗转相除法的算法步骤：第一步，给定两个正整数 m ， n .第二步，计算 m 除以 n 所得的余数 r .第三步，m ＝ n ， n ＝ r .第四步，若 r＝0，则 m，n 的最大公约数等于 m；否则返回第二步．2．更相减损术(1)更相减损术是我国古代数学专著《九章算术》中介绍的一种求两个正整数的最大公约数的算法．(2)其基本过程是：第一步，任意给定两个正整数，判断它们是否都是偶数．若是，用 2 约简 ；若不是，执行第二步．第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数．[化解疑难]辗转相除法与更相减损术的比较两种方法辗转相除法更相减损术计算法则除法减法终止条件余数为 0减数与差相等最大公约数的选取最后一步中的除数最后一步中的减数计算次数步骤较少，运算复杂步骤较多，运算简单相同点同为求两个正整数最大公约数的方法，都是递归过程秦九韶算法[提出问题]已知多项式 f(x)＝x5＋3x4－3x3＋4x2－x－1.问题 1：求 f(1)．提示：f(1)＝1＋3－3＋4－1－1＝3.问题 2：若求 f(39)，再代入运算出现什么情况？提示：运算量太大，不易运算．问题 3：当 x 的值较大时，有没有更好的方法求函数值呢？提示：有．可将 f(x)转化为求一次多项式的值．[导入新知]秦九韶算法的算法原理把一个 n 次多项式 f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0改写成如下形式：f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0＝(anxn－1＋an－1xn－2＋…＋a1)x＋a0＝((anxn－2＋an－1xn－3＋…＋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 个一次多项式的值．[化解疑难]秦九...
