1.3　算法案例

学习目标　1.理解辗转相除法与更相减损术的含义，了解其执行过程(重点).2.理解秦九韶算法的计算过程，并了解它提高计算效率的实质(重点).3.理解进位制的概念，能进行不同进位制间的转化(重点).

预习教材P34－44，完成下面问题：

知识点1　辗转相除法与更相减损术

1.辗转相除法

(1)辗转相除法：又叫欧几里得算法，是一种求两个正整数的最大公约数的古老而有效的算法.

(2)辗转相除法的算法步骤

第一步，给定两个正整数m，n.

第二步，计算m除以n所得的余数r.

第三步，m＝n，n＝r.

第四步，若r＝0，则m，n的最大公约数等于m；否则，返回第二步.

2.更相减损术

(1)我国古代数学专著《九章算术》中介绍的一种求两个正整数的最大公约数的算法.

(2)运算过程：

第一步，任意给定两个正整数，判断它们是否都是偶数，若是，用2约简；若不是，执行第二步.

第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.

【预习评价】

(1)用"辗转相除法"求得459和357的最大公约数是________.

解析　459＝357×1＋102，357＝102×3＋51，102＝51×2，所以51是102和51的最大公约数，也就是459和357的最大公约数是51.