3 算法案例 算法案例 (( 一一 ))第一章 算法初步本节知识目录当堂测、查疑缺探要点、究所然填要点、记疑点明目标、知重点探究点二 更相减损术探究点一 辗转相除法探究点三 秦九韶算法的基本思想算法案例( 一 )1 ．理解辗转相除法与更相减损术中的数学原理，并能根据这些 原理进行算法分析．2 ．了解秦九韶算法及利用它计算提高计算效率的本质．3 ．对简单的案例能设计程序框图并写出算法程序．明目标、知重点填要点、记疑点1．辗转相除法 (1)辗转相除法，又叫欧几里得算法，是一种求两个正整数的 的古老而有效的算法． (2)辗转相除法的算法步骤 第一步，给定 ． 第二步，计算
第四步，若r＝0，则m，n的最大公约数等于 ； 否则，返回 ． 最大公约数 两个正整数m ， n(m>n) m 除以 n 所得的余数 r m ＝n ， n ＝ r m 第二步 填要点、记疑点2．更相减损术的运算步骤 第一步，任意给定两个正整数，判断它们是否都是 ．若是，用 约简；若不是，执行 ． 第二步，以 的数减去 的数，接着把所得的差与 的数比较，并以大数减小数，继续这个操作，直到所得的数 为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数． 偶数 2 第二步 较大 较小 较小 相等 填要点、记疑点3．秦九韶算法 把一个n次多项式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0改写成如下形式： (…((anx＋an－1)x＋an－2)x＋…＋a1)x＋a0， 求多项式的值时，首先计算 一次多项式的值，即v1＝ ，然后由内向外逐层计算一次多项式的值，即 v2＝ ， v3＝ ， … vn＝ 这样，求n次多项式f(x)的值就转化为求 的值． 最内层括号内 anx ＋ an－ 1 v1x ＋ an－ 2 v2x ＋ an－ 3 vn － 1x ＋a0 n 个一次
