1、1.3 算法案例 辗转相除法与更相减损术 郑州一中郑州一中 胡莉萍胡莉萍 人教版（数学）必修三人教版（数学）必修三 引入课题引入课题 求求24与与9的最大公约数？的最大公约数？ 知识准备知识准备 249 26(24,9)(9,6) 24 9 3 9 9 6 请同学们结合课本的基础知识，思请同学们结合课本的基础知识，思 考解决考解决学习指导书学习指导书第第1-2页问题。页问题。 请同学们讨论各自的疑惑及感悟，请同学们讨论各自的疑惑及感悟， 提出问题，并相互解决。提出问题，并相互解决。 1. 关于辗转相除法的算理问题关于辗转相除法的算理问题 82516105 12146 61052146 2 18
2、13 21461813 1 333 1813333 5 148 333148 237 148374 (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)(148,37)37 (0) 0,( , ) 0,( , )( , ) mn qrrn rm nn rm nn r 若则 若则 1. 关于辗转相除法的算理问题关于辗转相除法的算理问题 , ,m n qr NN以上满足：以上满足： 第二
3、步，计算第二步，计算m除以除以n所得的余数所得的余数r . 第三步，第三步，m=n，n=r. 第四步，若第四步，若r=0，则，则m，n的最大公约数等于的最大公约数等于m； 否则，返回第二步否则，返回第二步. 第一步，给定两个正整数第一步，给定两个正整数m，n . 2. 设计算法之设计算法之 算法步骤算法步骤 （1）确立循环体）确立循环体:求求m除以除以n的余数的余数 r, m=n, n=r （2）初始化变量：输入）初始化变量：输入m, n （3）设定循环控制条件：）设定循环控制条件：r=0？ 2. 设计算法之设计算法之 构造循环结构构造循环结构 求求m除以除以n的余数的余数r 开始开始 输入输
4、入m，n m=n n=r r=0？ 是是 输出输出m 结束结束 否否 例例1 用更相减损术求用更相减损术求98与与63的最大公约数的最大公约数. 解：由于解：由于63不是偶数，把不是偶数，把98和和63以大数减小数，并以大数减小数，并 辗转相减，如图所示：辗转相减，如图所示： 989863633535 636335352828 353528287 7 28287 72121 21217 71414 14147 77 7 所以，所以，98与与63的最大公约数是的最大公约数是7 3. 3. 更相减损术更相减损术 名称名称 辗转相除法辗转相除法 更相减损术更相减损术 区别区别 联系联系 （1）以除法
5、为主）以除法为主. （2）两个整数差值较）两个整数差值较 大时运算次数较少大时运算次数较少. （3）相除余数为零时）相除余数为零时 得结果得结果. （1）以减法为主）以减法为主. （2）两个整数差值较大时）两个整数差值较大时 运算次数较多运算次数较多. （3）相减，两数相等得结）相减，两数相等得结 果，相减前要做是否都是偶果，相减前要做是否都是偶 数的判断数的判断. （1）都是求最大公约数的方法）都是求最大公约数的方法. （2）二者的实质都是递推的过程）二者的实质都是递推的过程. （3）二者都要用循环结构来实现）二者都要用循环结构来实现. 开始开始 i=m+1 输入：输入：m,n m MOD
6、i=0且且n MOD i=0? i=i-1 输出：输出：i 结束结束 是是 否否 mn? t=m,m=n,n=t 否否 是是 两个正整数两个正整数 的的 最小公倍数的算法最小公倍数的算法 , a b 最小公倍数 a b 最大公约数 求求m除以除以n的余数的余数r 开始开始 输入输入m，n m=n n0？ 否否 输出输出 是是 n=r S m Sm n 1.必做题：用辗转相除法求下列两数的最大公约必做题：用辗转相除法求下列两数的最大公约 数，并用更相减损术检验你的结果：数，并用更相减损术检验你的结果： （1）228，48；（；（2）185，98. 2.选做题：求选做题：求225，135最小公倍数最小公倍数 3.拓展延伸：请查阅相关书籍资料画出更相减损拓展延伸：请查阅相关书籍资料画出更相减损 术这种算法的程序框图，并用语句来描述这个算法术这种算法的程序框图，并用语句来描述这个算法
