高中数学算法案例辗转相除法与更相减损术学案及课件人教版必修三辗转相除法与更相减损术.ppt

欢迎光临 算法案例 一 辗转相除法与更相减损术山东淄博五中孙天军 学习目标 1 通过算法的典型案例 经历设计算法解决问题的全过程 感受算法解决问题的重要作用 2 理解辗转相除法与更相减损术中蕴含的数学原理 并能根据这些原理进行算法分析 设计出这两种算法的程序框图并写出它们的算法程序 熟练运用这两种算法求最大公约数 3 进一步体会算法的基本思想 发展有条理地思考与解决问题的能力 提高逻辑思维能力 重点难点 重点 理解辗转相除法与更相减损术求最大公约数的方法 难点 把辗转相除法与更相减损术的方法转换成程序框图与程序语言 一 课前自学 1 回顾算法的三种表述 自然语言 程序框图 程序语言 程序框图有三种逻辑结构 顺序结构 条件结构 循环结构 程序语言有五种基本算法语句 输入语句 输出语句 赋值语句 条件语句 循环语句 2 回顾求两个数的最大公约数的法 先用两个公有的质因数连续去除 一直除到所得的商是互质数为止 然后把所有的除数连乘起来 3 求24与30的最大公约数 求210与462的最大公约数 如何求8251和6105的最大公约数 所以 24和30的最大公约数为6 210和462的最大公约数为42 板块二 新知探究 1 问题提出 当两个数公有的质因数较大时 用原来的显然困难 须改进算法 用什么方法好 2 点拨 辗转相除法是解决上述问题的有效方法之一 此算法是欧几里得在公元前300左右首先提出的 因而 又叫欧几里得算法 3 师生探究 例1 用辗转相除法求8251与6105的最大公约数 观察用辗转相除法求8251和6105的最大公约数的过程 第一步 用两数中较大的数除以较小的数求得商和余数8251 6105 1 2146 结论 8251和6105的公约数就是6105和2146的公约数 求8251和6105的最大公约数 只要求出6105和2146的公约数就可以了 第二步对6105和2146重复第一步的做法6105 2146 2 1813同理6105和2146的最大公约数也是2146和1813的最大公约数 为什么呢 思考 从上述的过程你体会到了什么 若m是6105与2146的公约数 则8251必能被m整除 探究1 用辗转相除法求225和135的最大公约数 完整的过程 显然37是148和37的最大公约数 也就是8251和6105的最大公约数 显然45是90和45的最大公约数 也就是225和135的最大公约数 探究2 辗转相除法的解题步骤如何 其蕴含的数学原理是什么 225 135 1 90 135 90 1 45 90 45 2 辗转相除法算法步骤 第一步 输入两个正整数a b a b 第二步 求a除以b的余数r 第三步 若r 0 则把b的值赋于a r的值赋于b 转到第二步 否则转到第四步 第四步 输出最大公约数b数学原理是 在展转相除的过程中的b与r的公约数始终和a与b的公约数相等 且相除的步骤是有限的 程序框图 程序 input a b a bdor amodba bb rloopuntilr 0printaend 4 问题提出 除了用上述算法求两个数的最大公约数之外还有没有别的算法 5 点拨 用 更相减损术 更相减损术 是我国数学家刘徽的专著 九章算术 中记载的 更相减损术求最大公约数的步骤如下 可半者半之 不可半者 副置分母分子之数 以少减多 更相减损 求其等也 以等数约之 翻译出来为 第一步 任意给出两个正数 判断它们是否都是偶数 若是 用2约简 若不是 执行第二步 第二步 以较大的数减去较小的数 接着把较小的数与所得的差比较 并以大数减小数 继续这个操作 直到所得的数相等为止 则这个数 等数 就是所求的最大公约数 6 师生再探 例2 用更相减损术求91与49的最大公约数 并用辗转相除法检验结果 解法1 更相减损术 由于49不是偶数 把91和49以大数减小数 并辗转相减 即 91 49 4249 42 742 7 3535 7 2828 7 2121 7 1414 7 7 91与49的最大公约数是7 解法2 辗转相除法 91 49 1 4249 42 1 742 7 6 91与49的最大公约数是7 探究3 怎样用更相减损术求182与98的最大公约数 方法 由于182与98都是偶数 故将它们同除以2 得91与49 再用上面的方法求得91与49的最大公约数为7 则7 2 14为182与98的最大公约数 探究4 用更相减损术求80与36的最大公约数 并用辗转相除法检验结果 用更相减损术 用辗转相除法检验 80 36 4480 36 2 844 36 836 8 4 436 8 288 4 2 028 8 2020 8 12 80与36的最大公约数是412 8 48 4 4 80与36的最大公约数是4 请设计用 更相减损术 求两个数的最大大公约数的程序 程序 inputa bwhilea br a bifb rthena bb relsea rendifwendprintbend 探究5 更相减损术 蕴含的数学原理是什么 数学原理 由a b r 得a b r a与b和b与r有相同的公约数 辗转相减的步骤是有限的 思考 辗转相除法 与 更相减损术 的区别是什么 都是求最大公约数的方法 辗转相除法以除法为主 更相减损术以减法为主 计算次数上辗转相除法计算次数相对较少 特别当两个数字大小区别较大时计算次数的区别较明显 结果上 辗转相除法体现结果是以相除余数为0得到 而更相减损术则以减数与差相等而得到 板块三 知识拓展 问题提出 如何求三个正整数的最大公约数 分析 可以先求出其中两个数的最大公约数 用这两个数的最大公约数再与第三个数求最大公约数 所得结果就是这三个数的最大公约数 例3 求三个数175 100 75的最大公约数 解 先求175与100的最大公约数 175 100 1 75 100 75 1 25 75 25 3 175与100的最大公约数是25 再求75与25的最大公约数 由75 25 3 或75 25 50 50 25 25 得75与25的最大公约数是25 三个数175 100 75的最大公约数是25 探究6 如何求4个正整数的最大公约数 方法1 可以先求其中两个数的最大公约数a 再求a与第三个数的公约数b 再求b与第四个数的公约数c 则c为这4个数的最大公约数 方法2 将4个数分两组 每组两个数 先求每组两个数的最大公约数a与b 再求a与b的最大公约数c 则c就是这4个数的最大公约数 板块四 当堂反馈 见学案 板块五 课堂总结 1 辗转相除法 与 更相减损术 都是求最大公约数有的效方法 2 计算上辗转相除法以除法为主 更相减损术以减法为主 计算次数上辗转相除法计算次数相对较少 特别当两个数字大小区别较大时计算次数的区别