必修 3 学案 §1
1 算法案例(1) 姓名 ☆学习目标：1°理解辗转相除法与更相减损术中蕴含的数学原理， 能根据这些原理进行算法分析； 2°能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序； 3°感受算法的意义和价值
☻知识情境： 1：10 WHILE 语句: 计算机执行语句的过程是 20 UNTIL 语句: 计算机执行语句的过程是 能编写一个程序,用二分法求方程的近似解吗
2：我们已经学过求最大公约数的方法，你能求出 18 与 30 的公约数吗
如果公约数比较大而且根据我们的观察又不能得到一些公约数，又应该怎样求它 们的最大公约数
比如,如何求 1424 与 801 的最大公约数
☻知识生成： 1
教学辗转相除法：思路：可以利用除法将大数化小,找两数的最大公约数
(适于两数较大时)(1)用较大的数 m 除以较小的数 n 得到一个商和一个余数；(2)若＝0,则 n 为 m,n 的最大公约数；若≠0,则用除数 n 除以余数得到一个商和 一个余数；(3)若＝0,则为 m,n 的最大公约数;若≠0,则用除数除以余数 得到一个商和一个余数；……依次计算直至＝0， 此时所得到的即为所求的最大公约数
例题 1：求两个正数 1424 和 801 的最大公约数
① 以上我们求最大公约数的方法就是辗转相除法，也叫欧几里德算法
② 由上述步骤可以看出，辗转相除法中的除法是一个反复执行的步骤，且执行次数由余数 是否等于 0 来决定,所以可把它看成一循环体, 写出辗转相除法完整的程序框图和程序语言
教学更相减损术：我国早期也有求最大公约数问题的算法，就是更相减损术
在《九章算 术》中有更相减损术求最大公约数的步骤：可半者半之，不可半者，副置 分母•子之数，以少减多，更相减损，求其等也，以等数约之
翻译为：(1) 任意给出两个正数；判断它们是否都是偶数
