人教版高中数学必修三(教案)1.3算法案例(4课时).pdf

第一课时算法案例 - 辗转相除法与更相减损术 教学要求 ： 基本能根据算法语句与程序框图的知识设计出辗转相除法与更相减损 术完整的程序框图并写出它们的算法程序. 理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分 析； 教学重点 ：理解辗转相除法与更相减损术求最大公约数的方法. 教学难点 ：把辗转相除法与更相减损术的方法转换成程序框图与程序语言. 教学过程 ： 一、复习准备 ： 1. 回顾算法的三种表述：自然语言、程序框图（三种逻辑结构）、程序语言（五 种基本语句） . 2. 提问：小学学过的求两个数最大公约数的方法？（先用两个公有的质因数 连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来.）口 算出36 和 64 的最大公约数. 除了用这种方法外还有没有其它方法？ 6436 128，36和 28 的最大公约数就是64 和 36 的最大公约数，反复进 行这个步骤，直至 842，得出 4 即是 36 和 64 的最大公约数 . 二、讲授新课： 1. 教学辗转相除法： 例 1：求两个正数 1424 和 801 的最大公约数 . 分析：可以利用除法将大数化小，然后逐步找出两数的最大公约数. （适用于两 数较大时） 以上我们求最大公约数的方法就是辗转相除法 ，也叫欧几里德算法 ，它是由欧 几里德在公元前300 年左右首先提出的 . 利用辗转相除法求最大公约数的步骤 如下： （1）用较大的数 m除以较小的数 n 得到一个商 0 S和一个余数 0 R； （2）若 0 R0， 则 n 为 m ，n 的最大公约数；若 0 R0，则用除数 n除以余数 0 R得到一个商 1 S和 一个余数 1 R； （3）若 1 R0，则 1 R为 m ，n 的最大公约数；若 1 R0，则用除数 0 R 除以余数 1 R得到一个商 2 S和一个余数 2 R；依次计算直至 n R0，此 时所得到的 1n R即为所求的最大公约数 . 由上述步骤可以看出，辗转相除法中的除法是一个反复执行的步骤， 且执行次数由余数是否等于0 来决定，所以我们可以把它看成一个循环 体，它的程序框图如右图： （师生共析，写出辗转相除法完整的程序框 图和程序语言） 练习：求两个正数8251 和 2146 的最大公约数 . （乘法格式、除法格式） 2. 教学更相减损术： 我国早期也有求最大公约数问题的算法，就是更相减损术 . 在九章算术 中有 更相减损术求最大公约数的步骤：可半者半之，不可半者，副置分母?子之数， 以少减多，更相减损，求其等也，以等数约之. 翻译为： （1）任意给出两个正数；判断它们是否都是偶数. 若是，用 2 约简；若 不是，执行第二步 .（2）以较大的数减去较小的数，接着把较小的数与所得的差 比较，并以大数减小数 . 继续这个操作，直到所得的数相等为止，则这个数（等 数）就是所求的最大公约数. 例 2：用更相减损术求91 和 49 的最大公约数 . 分析：更相减损术是利用减法将大数化小，直到所得数相等时，这个数（等数） 就是所求的最大公约数 . （反思：辗转相除法与更相减损术是否存在相通的地方） 练习：用更相减损术求72 和 168 的最大公约数 . 3. 小结：辗转相除法与更相减损术及比较都是求最大公约数的方法，辗转相 除法以除法为主， 更相减损术以减法为主， 计算次数上辗转相除法计算次数相对 较少；结果上， 辗转相除法体现结果是以相除余数为0 得到，而更相减损术则 以减数与差相等而得到 . 三、巩固练习： 1、练习：教材 P35第 1 题2、作业：教材 P38第 1 题 第二课时1.3.2 算法案例 - 秦九韶算法 教学要求 ：了解秦九韶算法的计算过程， 并理解利用秦九韶算法可以减少计算次 数、提高计算效率的实质； 理解数学算法与计算机算法的区别，理解计算机对数 学的辅助作用 . 教学重点 ：秦九韶算法的特点及其程序设计. 教学难点 ：秦九韶算法的先进性理解及其程序设计. 教学过程 ： 一、复习准备 ： 1. 分别用辗转相除法和更相减损术求出两个正数623 和 1513 的最大公约数 . 2. 设计一个求多项式 5432 ( )254367f xxxxxx当5x时的值的算法 . （学生自己提出一般的解决方案：将5x代入多项式进行计算即可） 提问：上述算法在计算时共用了多少次乘法运算？多少次加法运算？此方案有何 优缺点？ (上述算法一共做了 5432115次乘法运算，5次加法运算 . 优 点是简单、易懂；缺点是不通用，不能解决任意多项式的求值问题，而且计算效 率不高 .) 二、讲授新课： 1. 教学秦九韶算法： 提问：在计算x的幂值时，可以利用前面的计算结果，以减少计算量，即先 计算 2 x，然后依次计算 2 xx， 2 ()xxx， 2 ()xxxx的值，这样计算上述多项 式的值，一共需要多少次乘法，多少次加法? （上述算法一共做了4 次乘法运算， 5 次加法运算） 结论：第二种做法与第一种做法相比，乘法的运算次数减少了，因而能提高 运算效率，而且对于计算机来说， 做一次乘法所需的运算时间比做一次加法要长 得多，因此第二种做法能更快地得到结果. 更有效的一种算法是： 将多项式变形为： 5432 ()254367fxxxxxx， 依 次 计 算 2555 ， 5 5421 ， 21 53108 ， 108 56534 ， 534 572677 故(5)2677f. 这种算法就是“秦九韶算法”. （注意变形，强调格式） 练习：用秦九韶算法求多项式 432 ( )2351f xxxxx当4x时的值 . （学生板书师生共评教师提问：上述算法共需多少次乘法运算？多少次加 法运算？） 如何用秦九韶算法完成一般多项式 1 110 ( ) nn nn f xa xaxa xa的求值 问题？ 改写： 1 1101210 ( )() nn nnnnn f xa xaxa xaa xaxaxaxa. 首先计算最内层括号内一次多项式的值，即 11nn va xa，然后由内向外逐层计 算一次多项式的值，即 212n vv xa， 323n vv xa， 10nn vvxa. 结论：秦九韶算法将求n次多项式的值转化为求n个一次多项式的值，整个 过程只需n次乘法运算和n次加法运算；观察上述n个一次式，可发出 k v的计算 要用到 1k v的值， 若令 0n va， 可得到下列递推公式： 0 1 , (1,2, ) n kknk va vvxakn . 这是一个反复执行的步骤，因此可用循环结构来实现. 练习：用秦九韶算法求多项式 5432 ( )523.52.61.70.8f xxxxxx当 5x时的值并画出程序框图 . 2. 小结： 秦九韶算法的特点及其程序设计 三、巩固练习： 1、练习：教材 P35第 2 题2、作业：教材 P36第 2 题 第三课时1.3.3 算法案例 - 进位制 教学要求 ：了解各种进位制与十进制之间转换的规律，会利用各种进位制与十进 制之间的联系进行各种进位制之间的转换；学习各种进位制转换成十进制的计算 方法，研究十进制转换为各种进位制的除k 去余法，并理解其中的数学规律. 教学重点 ：各种进位制之间的互化 . 教学难点 ：除 k 取余法的理解以及各进位制之间转换的程序框图及其程序的设 计. 教学过程 ： 一、复习准备 ： 1. 试用秦九韶算法求多项式 52 ( )42f xxx当3x时的值，分析此过程共需 多少次乘法运算？多少次加法运算？ 2. 提问：生活中我们常见的数字都是十进制的，但是并不是生活中的每一种数 字都是十进制的 . 比如时间和角度的单位用六十进位制, 电子计算机用的是二进 制，旧式的秤是十六进制的，计算一打数值时是12 进制的 那么什么是进 位制？不同的进位制之间又有什么联系呢？ 二、讲授新课： 1. 教学进位制的概念： 进位制是人们为了计数和运算方便而约定的记数系统，“满几进一”就是几进 制，几进制的基数就是几 . 如： “满十进一”就是十进制， “满二进一”就是二进 制. 同一个数可以用不同的进位制来表示，比如：十进数57，可以用二进制 表示为 111001，也可以用八进制表示为71、用十六进制表示为39，它们所代表 的数值都是一样的 . 表示各种进位制数一般在数字右下脚加注来表示，如上例 中： (2)(8)(16) 1110017139 一般地，任意一个k 进制数都可以表示成不同位上数字与基数的幂的乘积之 和的形式，即 1 110()1 .(0, nn nnknnnn a aa aakaa akakakakak . 如：把 (2) 110011 化为十进制数， ( 110011=12 5+1 24+0 23+0 2 2+1 21+1 20=32+16+2+1=51. 把八进制数 (8) 7348化为十进制数， 3210 (8) 73487 83 8488 83816. 2. 教学进位制之间的互化： 例 1：把二进制数 (2)1001101化为十进制数 . （学生板书教师点评师生共同总结将非十进制转为十进制数的方法） 分析此过程的算法过程，编写过程的程序语言. 见 P34 练习：将 (5) 2341、 (3) 121转化成十进制数 . 例 2、把 89 化为二进制数 . 分析：根据进位制的定义，二进制就是“满二进一” ，可以用 2 连续去除 89 或所 得商，然后取余数 . （教师板书） 上述方法也可以推广为把十进制化为k 进制数的算法 , 这种算法成为除 k取余法 . 练习：用除 k 取余法将 89 化为四进制数、六进制数 . 例 3、把二进制数 (2) 11011.101化为十进制数 . 解： 4 (2 11 . （小数也可利用上述方法化进行不同进位制之间的互化. ） 变式：化为八进制方法：进制互化 3. 小结： 进位制的定义；进位制之间的互化. 三、巩固练习： 1、练习：教材 P35第 3 题2、作业：教材 P38第 3 题 第四课时1.3.4 生活中的算法实例 教学要求 ：通过生活实例进一步了解算法思想. 教学重点 ：生活实例的算法分析 . 教学难点 ：算法思想的理解 . 教学过程 ： 一、复习准备 ： 1. 前面学习了哪几种算法案例？每种算法的作用及操作方法是怎样的？ 2. 算法思想在我们的生活中无处不在，如何利用我们所学习的知识解决生活中 的实际问题？ 二、讲授新课： 1. 霍奇森算法： 提问：同学们经常会面对一个共同的问题，就是有时有太多的事情要做. 例如， 你可能要面临好几门课的作业的最后期限，你如何合理安排以确保每门课的作业 都能如期完成？如果根本不可能全部按期完成，你该怎么办？（霍奇森算法可以 使得迟交作业的数目减到最小. 这一算法已经广泛应用于工业生产安排的实践 中. ） 例如：当你拿到下面这组数据后， 你会如何安排你的时间， 以确保每门课的作业 都能如期完成？若不能全部按期完成，也能尽量使迟交作业的数目减到最小？ 学科数学语文历史外语物理化学 期限/ 小时2 5 2 4 2 1 所需时间 / 小 时 1 2 0.5 1 0.5 0.5 若知道各项作业的到期日， 并且知道或能估计出完成每项作业将花费的时间，那 么霍奇森算法可用自然语言描述为：把这些作业按到期日的顺序从左到右排 列，从最早到期的到最晚到期的；假设从左到右一项一项做这些作业的话，计 算出从开始到完成某一项作业时所花的时间. 依次做此计算直到完成了所列表 中的全部作业而没有一项作业会超期，停止；或你算出某项作业将会超期，继续 第三步；考虑第一项将会超期的作业以及它左边的所有作业，从中取出花费时 间最长的那项作业，并把它从表中去掉；回到第二步，并重复第二到四步，直 到做完 . 2. 孙子问题： 韩信是秦末汉初的著名军事家. 据说有一次汉高祖刘邦在卫士的簇拥下来 到练兵场，刘邦问韩信有什么办法，不要逐个报数，就能知道场上士兵的人数. 韩信先令士兵排成了3 列纵队进行操练， 结果有 2人多余；接着他立刻下令 将队形改为 5 列纵队，这一改又多出 3 人；随后他又下令改为7 列纵队，这一 次又剩下 2人无法成整行 . 由此得出共有士兵 2333人. 如何用现在的算法思想分 析这一过程？ 孙子算经中给出了它的具体解法，其步骤是：选定5 7 的倍数，被3 除余 1，即 70；选定 3 7的一个倍数， 被 5 除余 1，即 21；选定 3 5的一个倍数， 被 7 除余 1，即 15. 然后按下式计算702213152105mp，式中 105 为3,5,7的最小公倍数， p 为适当的整数，使得0105m，这里取2p. 求解“孙子问题”的一种普通算法： 第一步：2m. 第二步：若m除以 3 余 2，则执行第三步；否则1mm，执行第二步 . 第三步：若m除以 5 余 3，则执行第四步；否则1mm，执行第二步 . 第四步：若m除以 7 余 2，则执行第五步；否则1mm，执行第二步 . 第五步：输出m. 3. 小结： 算法的基本思想 . 三、巩固练习：作业：教材 P38第 3 题