算法案例学习过程知识点 1：辗转相除法利用辗转相除法求最大公约数的步骤如下：（1）：用较大的数 m 除以较小的数 n 得到一个商和一个余数；（2）：若＝0，则n 为 m，n 的最大公约数；若≠0，则用除数 n 除以余数得到一个商和一个余数；（3）：若＝0，则为m，n 的最大公约数；若≠0，则用除数除以余数得到一个商和一个余数；…… 依次计 算直至＝0，此时所得到的即为所求的最大公约数。知识点 2：更相减损术 （1）：任意给出两个正数；判断它们是否都是偶数。若是，用 2 约简；若不是，执行第二步。（2）：以较大的数减去较小的数，接着把较 小的数与所得的差比较，并以大数减小数。继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数。知识点 3 ：辗转相除法与更相减损术的区别（1） 都是求最大公约数的方 法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大 小区别较大时计算次数的区别较明显。（2）从结果体现形式来看，辗转相除法 体现结果是以相除余数为 0 则 得到，而更相减损术则以减数与差相等而得到知识点 4：秦九韶计算多项式的方法学习结论（1）辗转相除法与更相减损术的定义、区别（2）秦九韶计算多项式的方法（3）两种排序方法：直接插入排序冒泡排序典型例题例题 1、 例 1 求两个正数 8251 和 6105 的最大公约数。解析：8251＝6105×1＋2146显然 8251 的最 大公约数也必是 2146 的约数，同样 6105 与 2146 的公约数也必是 8251的约数，所以 8251 与 6105 的最大公约数也是 6105 与 2146 的最大公约数。6105＝2146×2＋18132146＝1813×1＋3331813＝333×5＋148333＝148×2＋37148＝37×4＋0则 37 为 8251 与 6105 的最大公约数。例 2、设计利用秦九韶算法计算 5 次多项式当时的值的程序框图。解析：程序框图如下： 是是否否例 3．求满足 1＋2＋3＋…＋n > 500 的最小的自然数 n。（1）画出执行该问题的程序框图；（2）以下是解决该问题的一个程序，但有几处错误，请找出错误并予以更正。解析：（1）程序框图如图所示： 或 者： 8 分 （2）① DO 应改为 WHILE; ②PRINT n+1 应改为 PRINT n；③S=1 应改为 S=0 S＝0i=1S＝S+ii=i+1输出 i －1 S>500 结束S＝0i=1S＝S+ii=i+1输出 i －1 S<=500 结束
