13算法案例 整体设计 教学分析 在学生学习了算法的初步知识,理解了表示算法的算法步骤、程序框图和程序三种不同 方式以后,再结合典型算法案例,让学生经历设计算法解决问题的全过程,体验算法在解决 问题中的重要作用,体会算法的基本思想,提高逻辑思维能力,发展有条理地思考与数学表 达能力 三维目标 1.理解算法案例的算法步骤和程序框图 2.引导学生得出自己设计的算法程序 3.体会算法的基本思想,提高逻辑思维能力,发展有条理地思考与数学表达能力 重点难点 教学重点:引导学生得出自己设计的算法步骤、程序框图和算法程序 教学难点:体会算法的基本思想,提高逻辑思维能力,发展有条理地思考与数学表达能力 课时安排 3课时 教学过程 第1课时案例1辗转相除法与更相减损术 导入新课 思路1(情境导入) 大家喜欢打乒乓球吧,由于东、西方文化及身体条件的不同,西方人喜欢横握拍打球, 东方人喜欢直握拍打球,对于同一个问题,东、西方人处理问题方式是有所不同的在小学, 我们学过求两个正整数的最大公约数的方法:先用两个数公有的质因数连续去除,一直除到 所得的商是互质数为止,然后把所有的除数连乘起来.当两个数公有的质因数较大时(如8 25Ⅰ与6105),使用上述方法求最大公约数就比较困难下面我们介绍两种不同的算法 辗转相除法与更相减损术,由此可以体会东、西方文化的差异 思路2(直接导入) 前面我们学习了算法步骤、程序框图和算法语句今天我们将通过辗转相除法与更相减 损术来进一步体会算法的思想 推进新课 新知探究 提出问题 (1)怎样用短除法求最大公约数? (2)怎样用穷举法(也叫枚举法)求最大公约数? (3)怎样用辗转相除法求最大公约数? (4)怎样用更相减损术求最大公约数? 讨论结果: (1)短除法 求两个正整数的最大公约数的步骤:先用两个数公有的质因数连续去除,一直除到所得 的商是两个互质数为止,然后把所有的除数连乘起来 (2)穷举法(也叫枚举法) 穷举法求两个正整数的最大公约数的解题步骤:从两个数中较小数开始由大到小列举, 直到找到公约数立即中断列举,得到的公约数便是最大公约数 (3)辗转相除法
1 1.3 算法案例 整体设计 教学分析 在学生学习了算法的初步知识，理解了表示算法的算法步骤、程序框图和程序三种不同 方式以后，再结合典型算法案例，让学生经历设计算法解决问题的全过程，体验算法在解决 问题中的重要作用，体会算法的基本思想，提高逻辑思维能力，发展有条理地思考与数学表 达能力. 三维目标 1．理解算法案例的算法步骤和程序框图. 2．引导学生得出自己设计的算法程序. 3. 体会算法的基本思想，提高逻辑思维能力，发展有条理地思考与数学表达能力. 重点难点 教学重点：引导学生得出自己设计的算法步骤、程序框图和算法程序. 教学难点：体会算法的基本思想，提高逻辑思维能力，发展有条理地思考与数学表达能力. 课时安排 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用辗转相除法求8251与6105的最大公约数写出算法分析,画出程序框图,写出算 法程序 解:用两数中较大的数除以较小的数,求得商和余数:8251=6105×1+2146 由此可得,6105与2146的公约数也是8251与6105的公约数,反过来,8251与6105 的公约数也是6105与2146的公约数,所以它们的最大公约数相等 对6105与2146重复上述步骤:6105=2146×2+1813 同理,2146与1813的最大公约数也是6105与2146的最大公约数继续重复上述步骤: 2146=1813×1+333, 1813=333×5+148, 333=148×2+37, 148=37×4 最后的除数37是148和37的最大公约数,也就是8251与6105的最大公约数 这就是辗转相除法由除法的性质可以知道,对于任意两个正整数,上述除法步骤总可 以在有限步之后完成,从而总可以用辗转相除法求出两个正整数的最大公约数 算法分析:从上面的例子可以看出,辗转相除法中包含重复操作的步骤,因此可以用循环结 构来构造算法 算法步骤如下: 第一步,给定两个正整数m,n. 第二步,计算m除以n所得的余数为r 第三步,m=n,n= 第四步,若r=0,则m,n的最大公约数等于m:否则,返回第二步 程序框图如下图 2
2 辗转相除法求两个数的最大公约数，其算法步骤可以描述如下： 第一步，给定两个正整数 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；否则，返回第二步. 程序框图如下图：
开始 输人mn/ 求m除以的余数r m=n 结束 程序 INPUT mn rm mod n 1=n n-l LOOP UNTIL 0 PRINT m END 点评:从教学实践看,有些学生不能理解算法中的转化过程,例如:求8251与6105的最 大公约数,为什么可以转化为求6105与2146的公约数因为8251=6105×1+2146, 可以化为8251-6105×1=2164,所以公约数能够整除等式两边的数,即6105与2146的公 约数也是8251与6105的公约数 变式训练 你能用当型循环结构构造算法,求两个正整数的最大公约数吗?试画出程序框图和程 序 解:当型循环结构的程序框图如下图 开始 ∠输入mn 求m除以的余数 输出m 结束
3 程序： 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 WHILE r>0 MOD 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的最大公约数等于 点评:更相减损术与辗转相除法的比较:尽管两种算法分别于东、西方古代数学名著,但是 二者的算理却是相似的,有异曲同工之妙.主要区别在于辗转相除法进行的是除法运算,即 辗转相除:而更相减损术进行的是减法运算,即辗转相减,但是实质都是一个不断的递归过 变式训练 用辗转相除法或者更相减损术求三个数324,243,135的最大公约数 解:324=243×1+81 243=81×3+0, 则324与243的最大公约数为 又135=81×1+54,81=54×1+27, 则81与135的最大公约数为27 所以,三个数324、243、135的最大公约数为27 另法:324-243=81,243-81=162,162-81=81,则324与243的最大公约数为81 135-81=5481-54=27,54-27=27,则81与135的最大公约数为27 所以,三个数324、243.135的最大公约数为27 例3(1)用辗转相除法求123和48的最大公约数 (2)用更相减损术求80和36的最大公约数 解:(1)辗转相除法求最大公约数的过程如下: 123=2×48+27 27=1×21+6, 21=3×6+3, 6=2×3+0, 最后6能被3整除,得123和48的最大公约数为3
4 程序： 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 下面来求20与9的最大公约数 20-9=11, l1-9=2 9-2=7 7-2=5, 5-2=3 3-2=1, 2-1=1, 可得80和36的最大公约数为22×1=4 点评:对比两种方法控制好算法的结束,辗转相除法是到达余数为0,更相减损术是到达减 数和差相等 变式训练 分别用辗转相除法和更相减损术求1734,816的最大公约数 解:辗转相除法: 1734=816×2+102,816=102×8(余0), ∴1734与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-5l=51 ∴1734与816的最大公约数是51×2=102 利用更相减损术可另解: 1734-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 1734与816的最大公约数是102 知能训练
5 （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 的最大公约数为 2 2×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 ∴37与319的最大公约数为29,再求29与116的最大公约数 116=29×4 ∴29与116的最大公约数为29 ∴377,319,116的最大公约数为29 拓展提升 试写出利用更相减损术求两个正整数的最大公约数的程序 解:更相减损术程序: INPUT,n=”;m,n WHILE mon IF m>n ThEN ELSE m-n-m END IF WEND PRINT m END 课堂小结 (1)用辗转相除法求最大公约数 (2)用更相减损术求最大公约数 思想方法:递归思想 作业 分别用辗转相除法和更相减损术求261,319的最大公约数 分析:本题主要考查辗转相除法和更相减损术及其应用.使用辗转相除法可依据m=nq+r, 反复执行,直到r=0为止;用更相减损术就是根据m-n=,反复执行,直到n=r为止 解:辗转相除法 319=261×1+58 261=58×4+29, 58=29×2. ∴319与261的最大公约数是29 更相减损术: 319-26=58, 203-58=145 145-58=87 58-29=29 .319与261的最大公约数是29 设计感想 数学不仅是一门科学,也是一种文化,本节的引入从东、西方文化的不同开始,逐
6 求 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． 设计感想 数学不仅是一门科学，也是一种文化，本节的引入从东、西方文化的不同开始，逐
步向学生渗透数学文化从知识方面主要学习用两种方法求两个正整数的最大公约数,从 思想方法方面,主要学习递归思想本节设置精彩例题,不仅让学生学到知识,而且让学 生进一步体会算法的思想,培养学生的爱国主义情操
7 步向学生渗透数学文化.从知识方面主要学习用两种方法求两个正整数的最大公约数，从 思想方法方面，主要学习递归思想.本节设置精彩例题，不仅让学生学到知识，而且让学 生进一步体会算法的思想，培养学生的爱国主义情操．