1．3 算法案例第 1 课时 辗转相除法、更相减损术与秦九韶算法[目标] 1
会用辗转相除法与更相减损术求两个数的最大公约数；2
会用秦九韶算法求多项式的值．[重点] 两种算法的原理及应用．[难点] 两种算法思想的理解．知识点一 辗转相除法与更相减损术 [填一填]1．辗转相除法(1)辗转相除法是用于求两个正整数的最大公约数的一种算法，这种算法是由欧几里得在公元前 300 年左右首先提出的，因而又叫欧几里得算法．(2)所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数．若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数．2．更相减损术更相减损术是我国古代数学专著《九章算术》中介绍的一种求两数最大公约数的方法．其基本过程是：第一步，任意给定两个正整数，判断它们是否都是偶数．若是，用 2 约简；若不是，执行第二步．第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数．继续这个操作，直到所得的数相等为止，则这个数或这个数与约简的数的乘积就是所求的最大公约数．[答一答]1．任意给定两个正整数，是否用辗转相除法和更相减损术都可以求它们的最大公约数
提示：是．辗转相除法和更相减损术都能在有限步内结束，故均可以用来求两个正整数的最大公约数．2．求最大公约数时，如何选择辗转相除法和更相减损术
提示：当两个数大小差别不大时，两种方法的计算次数区别不大，只是辗转相除法以除法为主，更相减损术以减法为主；当两个数大小差别较大时，辗转相除法的计算次数明显较少，可选择辗转相除法．3．用“辗转相除法”求得 459 和 357 的最大公约数是 51
解析：用辗转相除法：459＝357×1＋102,357＝102×3＋51,102＝51×2
∴459 与 357的最大公约数为 51
知识点二 秦九韶算法
