辗转相除法ppt课件.ppt

辗转相除法与更相减损术 1 知识探究 一 辗转相除法 思考1 18与30的最大公约数是多少 你是怎样得到的 先用两个数公有的质因数连续去除 一直除到所得的商是互质数为止 然后把所有的除数连乘起来即为最大公约数 2 思考2 对于8251与6105这两个数 由于其公有的质因数较大 利用上述方法求最大公约数就比较困难 注意到8251 6105 1 2146 那么8251与6105这两个数的公约数和6105与2146的公约数有什么关系 3 思考3 又6105 2146 2 1813 同理 6105与2146的公约数和2146与1813的公约数相等 重复上述操作 你能得到8251与6105这两个数的最大公约数吗 2146 1813 1 333 148 37 4 0 333 148 2 37 1813 333 5 148 8251 6105 1 2146 6105 2146 2 1813 4 辗转相除法是一个反复执行直到余数等于0停止的步骤 这实际上是一个循环结构 m n q r 用程序框图表示出右边的过程 r mMODn m n n r r 0 是 否 思考4 辗转相除法中的关键步骤是哪种逻辑结构 5 思考5 上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法 一般地 用辗转相除法求两个正整数m n的最大公约数 可以用什么逻辑结构来构造算法 其算法步骤如何设计 第一步 给定两个正整数m n m n 第二步 计算m除以n所得的余数r 第三步 m n n r 第四步 若r 0 则m n的最大公约数等于m 否则 返回第二步 6 思考6 该算法的程序框图如何表示 7 思考7 该程序框图对应的程序如何表述 INPUTm n DO r mMODn m n n r LOOPUNTILr 0 PRINTm END 8 思考8 如果用当型循环结构构造算法 则用辗转相除法求两个正整数m n的最大公约数的程序框图和程序分别如何表示 9 INPUTm n WHILEr 0 r mMODn m n n r WEND PRINTm END 10 练习1 利用辗转相除法求两数4081与20723的最大公约数 53 20723 4081 5 318 4081 318 12 265 318 265 1 53 265 53 5 0 11 更相减损术 更相减损术 也是求两个正整数的最大公约数的算法 步骤 第一步 任意给定两个正整数 判断他们是否都是偶数 若是 则用2约简 若不是则执行第二步 第二步 以较大的数减较小的数 接着把所得的差与较小的数比较 并以大数减小数 继续这个操作 直到所得的减数和差相等为止 则这个等数或这个数与约简的数的乘积就是所求的最大公约数 12 例 用更相减损术求98与63的最大公约数 自己按照步骤求解 解 由于63不是偶数 把98和63以大数减小数 并辗转相减 所以 98和63的最大公约数等于7 98 63 35 63 35 28 35 28 7 28 7 21 21 7 14 14 7 7 13 更相减损是一个反复执行直到减数等于差时停止的步骤 这实际也是一个循环结构 思考 更相减损直到何时结束 运用的是哪种算法结构 14 程序 INPUT a b a bi 0WHILEaMOD2 0ANDbMOD2 0a a 2b b 2i i 1WENDDOIFb aTHENt aa bb tENDIFa a bLOOPUNTILa bPRINTa 2 iEND 15 例2分别用辗转相除法和更相减损术求168与93的最大公约数 辗转相除法 168 93 1 75 93 75 1 18 75 18 4 3 18 3 6 16 更相减损术 168 93 75 93 75 18 75 18 57 57 18 39 39 18 21 21 18 3 18 3 15 15 3 12 12 3 9 9 3 6 6 3 3 17 例3 用辗转相除法和更相减损术求210与714的最大公约数 18 比较辗转相除法与更相减损术的区别 1 都是求最大公约数的方法 计算上辗转相除法以除法为主 更相减损术以减法为主 计算次数上辗转相除法