第一章 1.3 法案例第一章 1.3 算法案例第一章 1.3 算法案例第一章 1.3 算法案例.ppt

返回 辗转相除法与更相减损术 [提出问题] [导入新知] 1．辗转相除法 (1)辗转相除法，又叫欧几里得算法，是一种求两个正整数的 的古老而有效的算法． (2)辗转相除法的算法步骤： 第一步，给定 . 第二步，计算 . 第三步， . 第四步，若r＝0，则m，n的最大公约数等于 ；否则返回 ． 最大公约数 两个正整数m，n m除以n所得的余数r m＝n，n＝r m 第二步 2．更相减损术 (1)更相减损术是我国古代数学专著《九章算术》中介绍的一种求 的算法． (2)其基本过程是： 第一步，任意给定两个正整数，判断它们是否都是 ． 若是， ；若不是，执行 ． 第二步，以 的数减去 的数，接着把所得的差与 的数比较，并以大数减小数，继续这个操作，直到所得的数 为止，则这个数或这个数与约简的数的乘积就是所求的最大公约数． 两个正整数的最大公约数 偶数 用2约简 第二步 较大 较小 较小 相等 秦九韶算法 [导入新知] 计数和运算方便 几 进位制 返回