数学人教版必修三：1.3 算法案例 第一课时 辗转相除法与更相减损术.ppt

郑州一中 胡莉萍 人教版（数学）必修三 引入课题 求24与9的最大公约数？ 知识准备 24 9 3 9 9 6 请同学们结合课本的基础知识，思考解决《学习指导书》第1-2页问题。 请同学们讨论各自的疑惑及感悟，提出问题，并相互解决。 1. 关于辗转相除法的算理问题 所以 1. 关于辗转相除法的算理问题 以上满足： 第二步，计算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 开始 输入m，n m=n n=r r=0？ 是 输出m 结束 否 例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． 3. 更相减损术 名称 辗转相除法 更相减损术 区别 联系 （1）以除法为主. （2）两个整数差值较大时运算次数较少. （3）相除余数为零时得结果. （1）以减法为主. （2）两个整数差值较大时运算次数较多. （3）相减，两数相等得结果，相减前要做是否都是偶数的判断. （1）都是求最大公约数的方法. （2）二者的实质都是递推的过程. （3）二者都要用循环结构来实现. 开始 i=m+1 输入：m,n m MOD i=0且n MOD i=0? i=i-1 输出：i 结束 是 否 mn? t=m,m=n,n=t 否 是 两个正整数 的最小公倍数的算法 最小公倍数＝ 求m除以n的余数r 开始 输入m，n m=n n≠0？ 否 输出 是 n=r 1.必做题：用辗转相除法求下列两数的最大公约数，并用更相减损术检验你的结果： （1）228，48；（2）185，98. 2.选做题：求225，135最小公倍数．  3.拓展延伸：请查阅相关书籍资料画出更相减损术这种算法的程序框图，并用语句来描述这个算法． * * * * * *