杜红全《算法案例》辗转相除法与更相减损术课件 新人教A版必修3.ppt

1 3算法案例 第一课时 康县一中杜红全 1 研究一个实际问题的算法 主要从算法步骤 程序框图和编写程序三方面展开 在程序框图中算法的基本逻辑结构有哪几种 在程序设计中基本的算法语句有哪几种 2 求两个正整数的最大公约数 是数学中的一个基础性问题 它有各种解决办法 我们以此为案例 对该问题的算法作一些探究 问题提出 辗转相除法与更相减损术 思考1 18与30的最大公约数是多少 你是怎样得到的 先用两个数公有的质因数连续去除 一直除到所得的商是互质数为止 然后把所有的除数连乘起来即为最大公约数 知识探究 一 辗转相除法 思考2 对于8251与6105这两个数 由于其公有的质因数较大 利用上述方法求最大公约数就比较困难 注意到8251 6105 1 2146 那么8251与6105这两个数的公约数和6105与2146的公约数有什么关系 思考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 上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法 一般地 用辗转相除法求两个正整数m n的最大公约数 可以用什么逻辑结构来构造算法 其算法步骤如何设计 第一步 给定两个正整数m n m n 第二步 计算m除以n所得的余数r 第三步 m n n r 第四步 若r 0 则m n的最大公约数等于m 否则 返回第二步 思考5 该算法的程序框图如何表示 思考6 该程序框图对应的程序如何表述 INPUTm n DO r mMODn m n n r LOOPUNTILr 0 PRINTm END 思考7 如果用当型循环结构构造算法 则用辗转相除法求两个正整数m n的最大公约数的程序框图和程序分别如何表示 INPUTm n WHILEn 0 r mMODn m n n r WEND PRINTm END 思考1 设两个正整数m n 若m n k 则m与n的最大公约数和n与k的最大公约数相等 反复利用这个原理 可求得98与63的最大公约数为多少 98 63 35 14 7 7 21 7 14 28 7 21 35 28 7 63 35 28 知识探究 二 更相减损术 思考2 上述求两个正整数的最大公约数的方法称为更相减损术 一般地 用更相减损术求两个正整数m n的最大公约数 可以用什么逻辑结构来构造算法 其算法步骤如何设计 第一步 给定两个正整数m n m n 第二步 计算m n所得的差k 第三步 比较n与k的大小 其中大者用m表示 小者用n表示 第四步 若m n 则m n的最大公约数等于m 否则 返回第二步 思考3 该算法的程序框图如何表示 思考4 该程序框图对应的程序如何表述 INPUTm n WHILEmn k m n IFn kTHEN m n n k ELSE m k ENDIF WEND PRINTm END 更相减损术 在中国古代数学专著 九章算术 中记述为 可半者半之 不可半者 副置分母 子之数 以少减多 更相减损 求其等也 以等数约之 比较辗转相除法与更相减损术的区别 1 都是求最大公约数的方法 计算上辗转相除法以除法为主 更相减损术以减法为主 计算次数上辗转相除法计算次数相对较少 特别当两个数字大小区别较大时计算次数的区别较明显 2 从结果体现形式来看 辗转相除法体现结果是以相除余数为0则得到 而更相减损术则以减数与差相等而得到 小结 理论迁移 例1分别用辗转相除法和更相减损术求168与93的最大公约数 辗转相除法 168 93 1 75 93 75 1 18 75 18 4 3 18 3 6 更相减损术 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 例2求325 130 270三个数的最大公约数 因为325 130 2 65 130 65 2 所以325与130的最大公约数是65 因为270 65 4 10 65 10 6 5 10 5 2 所以65与270最大公约数是5 故325 130 270三个数的最大公约数是5 1 辗转相除法 就是对于给定的两个正整数 用较大的数除以较小的数 若余数不为零 则将余数和较小的数构成新的一对数 继续上面的除法 直到大数被小数除尽为止 这时的较小的数即为原来两个数的最大公约数 小结作业 2 更相减损术 就是