开始 输入m，n 求m除以n的余数r
更相减损术
算法步骤
m=n n=r
r=0？ 是
输出m 结束
否
本节课基本原则： 认识特殊 阅读案例 推广一般 经历过程
本节课基本流程是： 从解决特殊问题开始到一般问题解决的算法分析， 写算法步骤，画程序框图和编制程序．
谢谢，请多批评指导！
9
6
知识准备
24 9 2 6
(24,9) (9,6)
同学们生成的问题主要有三个方面: （1）辗转相除法的算理问题 （2）对程序框图的理解问题 （3）多题一解和一题多解
1. 关于辗转相除法的算理问题
8251 6105 1 2146 6105 2146 2 1813 2146 1813 1 333 1813 333 5 148 333 148 2 37 148 37 4
(148,37) 37
1. 关于辗转相除法的算理问题
m n q r (0 r n) 若r 0, 则(m, n) n 若r 0, 则(m, n) (n, r )
以上满足：m, n, q N , r N
2. 设计算法之 算法步骤 第一步，给定两个正整数m，n . 第二步，计算m除以n所得的余数r .
是
1.必做题：用辗转相除法求下列两数的最大公约 数，并用更相减损术检验你的结果： （1）228，48；（2）185，98.
2.选做题：求225，135最小公倍数．
3.拓展延伸：请查阅相关书籍资料画出更相减损 术这种算法的程来自框图，并用语句来描述这个算法．
辗转相除法与更相减损术
算法分析
辗转相除法算法框图
结束
是
3. 更相减损术 例1 用更相减损术求98与63的最大公约数. 解：由于63不是偶数，把98和63以大数减小数，并 辗转相减，如图所示： 98－63＝35 63－35＝28 35－28＝7 28－7＝21 21－7＝14 14－7＝7 所以，98与63的最大公约数是7．
名称
辗转相除法
更相减损术
(1)初步了解辗转相除法与更相减损术中蕴含的数学原理， 通过阅读中国古代数学中的算法案例，体会 不强调对这些知识的记忆与灵活应用，但能根据这些原理进行 算法分析，能够画出程序框图表示算法. . 中国古代数学对世界数学发展的贡献
(2)模仿、操作、探索、经历设计算法，解决问题的全过程， 体会算法的基本思想. (3)感受算法在解决实际问题中的重要作用，培养学生利用 算法解决问题的意识. (4)在计算机上验证算法，领会数学算法与计算机处理的结 合方式，初步掌握把数学算法转化成计算机语言的一般步骤.
人教版（数学）必修三
1.3 算法案例 辗转相除法与更相减损术
郑州一中 胡莉萍
算法内容反应了时代的特点 中国古代数学思想在新的层次上的复兴
辗转相除法与更相减损术，秦九韶算法和进位制 经历设计算法解决问题的全过程，体验算法在 解决问题中的重要作用，体会算法的基本思想。提 高逻辑思维能力，发展有条理的思考与数学表达能 力
（1）以除法为主. （2）两个整数差值较 区别 大时运算次数较少. （3）相除余数为零时 得结果.
（1）以减法为主. （2）两个整数差值较大时 运算次数较多. （3）相减，两数相等得结果， 相减前要做是否都是偶数的判 断. （1）都是求最大公约数的方法. 联系 （2）二者的实质都是递推的过程. （3）二者都要用循环结构来实现.
DO r =m MOD n m=n n=r LOOP UNTIL r =0 PRINT m END
r=0？ 是
输出m
否
结束
开始 输入m，n n=r m=n 求m除以n的余数r
INPUT m，n WHILE n<>0 r =m MOD n m=n n=r WEND PRINT m END
n≠0？ 否 输出m
(8251, 6105) (6105, 2146) (6105, 2146) (2146,1813) (2146,1813) (1813,333) (1813,333) (333,148) (333,148) (148,37) (148,37) 37
所以
(8251,6105)
第三步，m=n，n=r.
第四步，若r=0，则m，n的最大公约数等于m； 否则，返回第二步.
2. 设计算法之 构造循环结构
（1）确立循环体:求m除以n的余数 r, m=n, n=r
（2）初始化变量：输入m, n （3）设定循环控制条件：r=0？
开始 输入m，n 求m除以n的余数r m=n n=r
INPUT m，n
强调一题多解 用不同的算理解决同一个问题 用不同的逻辑结构实现同一个算理
遵循教学过程 写算法步骤 画程序框图 编制程序
算法目标：求两个正整数的最大公约数 知识准备：带余除法 教学方法：阅读指导（主体课堂模式） 教学环节：自主学习 交流研讨 精讲 自我测评
引入课题 求24与9的最大公约数？
9
24 9 3
开始 输入：m,n m>n? 否
是
t=m,m=n,n=t i=m+1 i=i-1
否
m MOD i=0且n MOD i=0?
是
输出：i 结束
开始
两个正整数 a , b 的 最小公倍数的算法
输入m，n
S m n
ab 最小公倍数＝ 最大公约数
n=r
m=n 求m除以n的余数r n≠0？ 否
S 输出 m