人教A版数学必修三1-3算法案例（辗转相除法与更相减损术） 7页

§1.3 算法案例 一、教材分析 在学生学习了算法的初步知识，理解了表示算法的算法步骤、程序框图和程序三种不同 方式以后，再结合典型算法案例，让学生经历设计算法解决问题的全过程，体验算法在解决 问题中的重要作用，体会算法的基本思想，提高逻辑思维能力，发展有条理地思考与数学表 达能力. 二、教学目标 1、知识与技能 （1）理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分 析。 （2）基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序。 （3）了解秦九韶算法的计算过程，并理解利用秦九韶算法可以减少计算次数提高计算 效率的实质。 （4）掌握数据排序的原理能使用直接排序法与冒泡排序法给一组数据排序，进而能设 计冒泡排序法的程序框图及程序，理解数学算法与计算机算法的区别，理解计算机对数学的 辅助作用。 （5）了解各种进位制与十进制之间转换的规律，会利用各种进位制与十进制之间的联 系进行各种进位制之间的转换。 2、过程与方法 （1）在辗转相除法与更相减损术求最大公约数的学习过程中对比我们常见的约分求公 因式的方法，比较它们在算法上的区别，并从程序的学习中体会数学的严谨，领会数学算法 计算机处理的结合方式，初步掌握把数学算法转化成计算机语言的一般步骤。 （2）模仿秦九韶计算方法，体会古人计算构思的巧妙。能根据排序法中的直接插入排 序法与冒泡排序法的步骤，了解数学计算转换为计算机计算的途径，从而探究计算机算法与 数学算法的区别，体会计算机对数学学习的辅助作用。 （3）学习各种进位制转换成十进制的计算方法，研究十进制转换为各种进位制的除 k 去余法，并理解其中的数学规律。 3、情态与价值观 （1）通过阅读中国古代数学中的算法案例，体会中国古代数学对世界数学发展的贡献。 （2）在学习古代数学家解决数学问题的方法的过程中培养严谨的逻辑思维能力，在利 用算法解决数学问题的过程中培养理性的精神和动手实践的能力。 （3）通过对秦九韶算法的学习，了解中国古代数学家对数学的贡献，充分认识到我国 文化历史的悠久。通过对排序法的学习，领会数学计算与计算机计算的区别，充分认识信息 技术对数学的促进。 （4）领悟十进制，二进制的特点，了解计算机的电路与二进制的联系，进一步认识到 计算机与数学的联系。 三、重点难点 教学重点：（1）引导学生得出自己设计的算法步骤、程序框图和算法程序. （2）秦九韶算法的特点 （3）两种排序法的排序步骤及计算机程序设计 （4）各进位制表示数的方法及各进位制之间的转换 教学难点：（1）体会算法的基本思想，提高逻辑思维能力，发展有条理地思考与数学表达能 力. （2）秦九韶算法的先进性理解 （3）排序法的计算机程序设计 （4）除 k 去余法的理解以及各进位制之间转换的程序框图的设计 四、课时安排 3 课时 五、教学设计 第 1 课时 案例 1 辗转相除法与更相减损术 （一）导入新课 思路 1（情境导入） 大家喜欢打乒乓球吧，由于东、西方文化及身体条件的不同，西方人喜欢横握拍打球， 东方人喜欢直握拍打球，对于同一个问题，东、西方人处理问题方式是有所不同的.在小学， 我们学过求两个正整数的最大公约数的方法：先用两个数公有的质因数连续去除，一直除到 所得的商是互质数为止，然后把所有的除数连乘起来. 当两个数公有的质因数较大时（如 8 251 与 6 105），使用上述方法求最大公约数就比较困难.下面我们介绍两种不同的算法 ——辗转相除法与更相减损术,由此可以体会东、西方文化的差异. 思路 2（直接导入） 前面我们学习了算法步骤、程序框图和算法语句.今天我们将通过辗转相除法与更相减 损术来进一步体会算法的思想. （二）推进新课、新知探究、提出问题 （1）怎样用短除法求最大公约数？ （2）怎样用穷举法（也叫枚举法）求最大公约数？ （3）怎样用辗转相除法求最大公约数？ （4）怎样用更相减损术求最大公约数？ 讨论结果： （1）短除法 求两个正整数的最大公约数的步骤：先用两个数公有的质因数连续去除，一直除到所得 的商是两个互质数为止，然后把所有的除数连乘起来. （2）穷举法（也叫枚举法） 穷举法求两个正整数的最大公约数的解题步骤：从两个数中较小数开始由大到小列举， 直到找到公约数立即中断列举，得到的公约数便是最大公约数. （3）辗转相除法 辗转相除法求两个数的最大公约数，其算法步骤可以描述如下： 第一步，给定两个正整数 m，n. 第二步，求余数 r：计算 m 除以 n，将所得余数存放到变量 r 中. 第三步，更新被除数和余数：m=n，n=r. 第四步，判断余数 r 是否为 0.若余数为 0，则输出结果；否则转向第二步继续循环执行. 如此循环，直到得到结果为止. 这种算法是由欧几里得在公元前 300 年左右首先提出的， 因而又叫欧几里得算法. （4）更相减损术 我国早期也有解决求最大公约数问题的算法，就是更相减损术. 《九章算术》是中国古 代的数学专著，其中的“更相减损术”也可以用来求两个数的最大公约数，即“可半者半之， 不可半者，副置分母、子之数，以少减多，更相减损，求其等也.以等数约之.”翻译为现代语 言如下： 第一步，任意给定两个正整数，判断它们是否都是偶数，若是，用 2 约简；若不是，执 行第二步. 第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数， 继续这个操作，直到所得的数相等为止，则这个数（等数）或这个数与约简的数的乘积就是 所求的最大公约数. （三）应用示例 例 1 用辗转相除法求 8 251 与 6 105 的最大公约数,写出算法分析，画出程序框图，写出算 法程序. 解：用两数中较大的数除以较小的数，求得商和余数：8 251=6 105×1+2 146. 由此可得，6 105 与 2 146 的公约数也是 8 251 与 6 105 的公约数，反过来，8 251 与 6 105 的公约数也是 6 105 与 2 146 的公约数，所以它们的最大公约数相等. 对 6 105 与 2 146 重复上述步骤：6 105=2 146×2+1 813. 同理，2 146 与 1 813 的最大公约数也是 6 105 与 2 146 的最大公约数.继续重复上述步骤： 2 146=1 813×1+333， 1 813=333×5+148， 333=148×2+37， 148=37×4. 最后的除数 37 是 148 和 37 的最大公约数，也就是 8 251 与 6 105 的最大公约数. 这就是辗转相除法.由除法的性质可以知道，对于任意两个正整数，上述除法步骤总可 以在有限步之后完成，从而总可以用辗转相除法求出两个正整数的最大公约数. 算法分析：从上面的例子可以看出，辗转相除法中包含重复操作的步骤，因此可以用循 环结构来构造算法. 算法步骤如下： 第一步，给定两个正整数 m，n. 第二步，计算 m 除以 n 所得的余数为 r. 第三步，m=n，n=r. 第四步，若 r=0，则 m，n 的最大公约数等于 m；否则，返回第二步. 程序框图如下图： 程序： INPUT m,n DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END 点评：从教学实践看，有些学生不能理解算法中的转化过程，例如：求 8 251 与 6 105 的最大公约数,为什么可以转化为求 6 105 与 2 146 的公约数.因为 8 251=6 105×1+2 146， 可以化为 8 251-6 105×1=2 164，所以公约数能够整除等式两边的数，即 6 105 与 2 146 的公 约数也是 8 251 与 6 105 的公约数. 变式训练 你能用当型循环结构构造算法，求两个正整数的最大公约数吗？试画出程序框图和程 序. 解：当型循环结构的程序框图如下图： 程序： INPUT m，n r=1 WHILE r＞0 r=m MOD n m=n n=r WEND PRINT m END 例 2 用更相减损术求 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. 点评：更相减损术与辗转相除法的比较：尽管两种算法分别来源于东、西方古代数学名 著，但是二者的算理却是相似的，有异曲同工之妙．主要区别在于辗转相除法进行的是除法 运算，即辗转相除；而更相减损术进行的是减法运算，即辗转相减，但是实质都是一个不断 的递归过程． 变式训练 用辗转相除法或者更相减损术求三个数 324,243,135 的最大公约数. 解：324=243×1＋81， 243=81×3＋0， 则 324 与 243 的最大公约数为 81. 又 135=81×1＋54，81=54×1＋27， 54=27×2＋0， 则 81 与 135 的最大公约数为 27. 所以,三个数 324、243、135 的最大公约数为 27. 另法：324－243=81,243－81=162,162－81=81，则 324 与 243 的最大公约数为 81. 135－81=54,81－54=27,54－27=27，则 81 与 135 的最大公约数为 27. 所以，三个数 324、243.135 的最大公约数为 27. 例 3 （1）用辗转相除法求 123 和 48 的最大公约数. （2）用更相减损术求 80 和 36 的最大公约数. 解：（1）辗转相除法求最大公约数的过程如下： 123＝2×48＋27， 48＝1×27＋21， 27＝1×21＋6， 21＝3×6＋3， 6＝2×3+0， 最后 6 能被 3 整除，得 123 和 48 的最大公约数为 3. （2）我们将 80 作为大数，36 作为小数，因为 80 和 36 都是偶数，要除公因数 2. 80÷2=40，36÷2=18. 40 和 18 都是偶数，要除公因数 2. 40÷2=20，18÷2=9. 下面来求 20 与 9 的最大公约数， 20－9=11， 11－9=2， 9－2=7， 7－2=5， 5－2=3， 3－2=1， 2－1=1， 可得 80 和 36 的最大公约数为 22×1=4. 点评：对比两种方法控制好算法的结束，辗转相除法是到达余数为 0，更相减损术是到 达减数和差相等. 变式训练 分别用辗转相除法和更相减损术求 1 734，816 的最大公约数． 解：辗转相除法： 1 734=816×2+102，816=102×8（余 0）， ∴1 734 与 816 的最大公约数是 102． 更相减损术：因为两数皆为偶数，首先除以 2 得到 867，408，再求 867 与 408 的最大公约 数． 867-408=459， 459-408=51， 408-51=357， 357-51=306， 306-51=255， 255-51=204， 204-51=153， 153-51=102， 102-51=51. ∴1 734 与 816 的最大公约数是 51×2=102． 利用更相减损术可另解： 1 734－816＝918， 918－816＝102， 816－102＝714， 714－102＝612， 612－102＝510， 510－102＝408， 408－102＝306， 306－102＝204， 204－102＝102. ∴1 734 与 816 的最大公约数是 102． （四）知能训练 求 319，377，116 的最大公约数． 解：377=319×1+58， 319=58×5+29， 58=29×2. ∴377 与 319 的最大公约数为 29，再求 29 与 116 的最大公约数． 116=29×4. ∴29 与 116 的最大公约数为 29. ∴377，319，116 的最大公约数为 29. （五）拓展提升 试写出利用更相减损术求两个正整数的最大公约数的程序． 解：更相减损术程序： INPUT “m，n=”；m，n WHILE m<>n IF m>n THEN ｍ＝m-n ELSE m=n-m END IF WEND PRINT m END （六）课堂小结 （1）用辗转相除法求最大公约数. （2）用更相减损术求最大公约数. 思想方法：递归思想. （七）作业 分别用辗转相除法和更相减损术求 261，319 的最大公约数. 分析：本题主要考查辗转相除法和更相减损术及其应用．使用辗转相除法可依据 m=nq+r，反复执行，直到 r=0 为止；用更相减损术就是根据 m-n=r，反复执行，直到 n=r 为 止． 解：辗转相除法： 319=261×1+58, 261=58×4+29, 58=29×2. ∴319 与 261 的最大公约数是 29． 更相减损术： 319-261=58, 261-58=203, 203-58=145, 145-58=87, 87-58=29, 58-29=29, ∴319 与 261 的最大公约数是 29．