1、1.3 算法案例 辗转相除法与更相减损术,郑州一中 胡莉萍,人教版（数学）必修三,引入课题,求24与9的最大公约数？,知识准备,1.3.1辗转相除法与更相减损术,24,9,3,9,9,6,1.3.1辗转相除法与更相减损术,(一）自主学习,请同学们结合课本的基础知识，思考解决学习指导书第1-2页问题。,1.3.1辗转相除法与更相减损术,(二）交流研讨,请同学们讨论各自的疑惑及感悟，提出问题，并相互解决。,1. 关于辗转相除法的算理问题,所以,1.3.1辗转相除法与更相减损术,(三）精讲,1. 关于辗转相除法的算理问题,1.3.1辗转相除法与更相减损术,(三）精讲,以上满足：,第二步，计算m除以n
2、所得的余数r .,第三步，m=n，n=r.,第四步，若r=0，则m，n的最大公约数等于m； 否则，返回第二步.,第一步，给定两个正整数m，n .,2. 设计算法之 算法步骤,1.3.1辗转相除法与更相减损术,(三）精讲,（1）确立循环体:求m除以n的余数 r, m=n, n=r （2）初始化变量：输入m, n （3）设定循环控制条件：r=0？,2. 设计算法之 构造循环结构,1.3.1辗转相除法与更相减损术,(三）精讲,1.3.1辗转相除法与更相减损术,例1 用更相减损术求98与63的最大公约数.,解：由于63不是偶数，把98和63以大数减小数，并辗转相减，如图所示：,986335 63352
3、8 35287 28721 21714 1477,所以，98与63的最大公约数是7,3. 更相减损术,小结 辗转相除法与更相减损术的比较:,（1）以除法为主.,（2）两个整数差值较大时运算次数较少.,（3）相除余数为零时得结果.,（1）以减法为主.,（2）两个整数差值较大时运算次数较多.,（3）相减，两数相等得结果，相减前要做是否都是偶数的判断.,（1）都是求最大公约数的方法.,（2）二者的实质都是递推的过程.,（3）二者都要用循环结构来实现.,穷 举 法 程 序 框 图,1.3.1辗转相除法与更相减损术,两个正整数 的最小公倍数的算法,最小公倍数,1.3.1辗转相除法与更相减损术,1.必做题：用辗转相除法求下列两数的最大公约数，并用更相减损术检验你的结果： （1）228，48；（2）185，98. 2.选做题：求225，135最小公倍数 3.拓展延伸：请查阅相关书籍资料画出更相减损术这种算法的程序框图，并用语句来描述这个算法,1.3.1辗转相除法与更相减损术,(四）自我测评,
