人教版高中数学必修三（教案）1.3 算法案例（4课时）.doc

第一课时 1.3.1 算法案例---辗转相除法与更相减损术 教学要求：理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理 进行算法分析； 基本能根据算法语句与程序框图的知识设计出辗转相除法与更 相减损术完整的程序框图并写出它们的算法程序. 教学重点：理解辗转相除法与更相减损术求最大公约数的方法. 教学难点：把辗转相除法与更相减损术的方法转换成程序框图与程序语言. 教学过程： 一、复习准备： 1. 回顾算法的三种表述：自然语言、程序框图（三种逻辑结构）、程序语言（五 种基本语句）. 2. 提问：①小学学过的求两个数最大公约数的方法？（先用两个公有的质因数 连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来.）口 算 出 36 和 64 的 最 大 公 约 数 . ② 除 了 用 这 种 方 法 外 还 有 没 有 其 它 方 法 ？ ， 和 28 的最大公约数就是 64 和 36 的最大公约数，反复进 行这个步骤，直至 ，得出 4 即是 36 和 64 的最大公约数. 二、讲授新课： 1. 教学辗转相除法： 例 1：求两个正数 1424 和 801 的最大公约数. 分析：可以利用除法将大数化小，然后逐步找出两数的最大公约数. （适用于两 数较大时） ①以上我们求最大公约数的方法就是辗转相除法，也叫欧几里德算法，它是由欧 几里德在公元前 300 年左右首先提出的. 利用辗转相除法求最大公约数的步骤如 下： （1）用较大的数 m 除以较小的数 n 得到一个商 和一个余数 ；（2）若 ＝ 0，则 n 为 m，n 的最大公约数；若 ≠0，则用除数 n 除以余数 得到一个商 和一个余数 ；（3）若 ＝0，则 为 m，n 的最大公约数；若 ≠0，则用除 数 除以余数 得到一个商 和一个余数 ；……依次计算直至 ＝0，此时所得到的 即为所求的最大公约数. ②由上述步骤可以看出，辗转相除法中的除法是一个反复执行的步骤， 且执行次数由余数是否等于 0 来决定，所以我们可以把它看成一个循环 体，它的程序框图如右图：（师生共析，写出辗转相除法完整的程序框图 和程序语言） 练习：求两个正数 8251 和 2146 的最大公约数. （乘法格式、除法格式） 2. 教学更相减损术： 我国早期也有求最大公约数问题的算法，就是更相减损术. 在《九章算术》中有 更相减损术求最大公约数的步骤：可半者半之，不可半者，副置分母•子之数， 以少减多，更相减损，求其等也，以等数约之. 翻译为：（1）任意给出两个正数；判断它们是否都是偶数. 若是，用 2 约简； 若不是，执行第二步.（2）以较大的数减去较小的数，接着把较小的数与所得的 差比较，并以大数减小数. 继续这个操作，直到所得的数相等为止，则这个数 （等数）就是所求的最大公约数. 例 2：用更相减损术求 91 和 49 的最大公约数. 分析：更相减损术是利用减法将大数化小，直到所得数相等时，这个数（等数） 64 36 1 28= × + 36∴ 8 4 2= × 0S 0R 0R 0R 0R 1S 1R 1R 1R 1R 0R 1R 2S 2R nR 1nR −就是所求的最大公约数. （反思：辗转相除法与更相减损术是否存在相通的地方） 练习：用更相减损术求 72 和 168 的最大公约数. 3. 小结：辗转相除法与更相减损术及比较①都是求最大公约数的方法，辗转相 除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对 较少；②结果上，辗转相除法体现结果是以相除余数为 0 得到，而更相减损术则 以减数与差相等而得到. 三、巩固练习：1、练习：教材 P35 第 1 题　　2、作业：教材 P38 第 1 题 第二课时 1.3.2 算法案例---秦九韶算法 教学要求：了解秦九韶算法的计算过程，并理解利用秦九韶算法可以减少计算次 数、提高计算效率的实质；理解数学算法与计算机算法的区别，理解计算机对数 学的辅助作用. 教学重点：秦九韶算法的特点及其程序设计. 教学难点：秦九韶算法的先进性理解及其程序设计. 教学过程： 一、复习准备： 1. 分别用辗转相除法和更相减损术求出两个正数 623 和 1513 的最大公约数. 2. 设计一个求多项式 当 时的值的算法. （学生自己提出一般的解决方案：将 代入多项式进行计算即可） 提问：上述算法在计算时共用了多少次乘法运算？多少次加法运算？此方案有何 优缺点？(上述算法一共做了 5＋4＋3＋2＋1＝15 次乘法运算，5 次加法运算.优 点是简单、易懂；缺点是不通用，不能解决任意多项式的求值问题，而且计算效 率不高.) 二、讲授新课： 1. 教学秦九韶算法： ① 提问：在计算 的幂值时，可以利用前面的计算结果，以减少计算量，即先 计算 ，然后依次计算 ， ， 的值，这样计算上述多项 式的值，一共需要多少次乘法，多少次加法?（上述算法一共做了 4 次乘法运算， 5 次加法运算） ② 结论：第二种做法与第一种做法相比，乘法的运算次数减少了，因而能提高 运算效率，而且对于计算机来说，做一次乘法所需的运算时间比做一次加法要长 得多，因此第二种做法能更快地得到结果. ③ 更有效的一种算法是： 将 多 项 式 变 形 为 ： ， 依 次 计 算 ， ， ， ， 故 . ――这种算法就是“秦九韶算法”. （注意变形，强调格式） ④ 练习：用秦九韶算法求多项式 当 时的值. （学生板书 师生共评 教师提问：上述算法共需多少次乘法运算？多少次加 法运算？） ⑤ 如何用秦九韶算法完成一般多项式 的求值问 题？ 改写： . 5 4 3 2( ) 2 5 4 3 6 7f x x x x x x= − − + − + 5x = 5x = x 2x 2x x⋅ 2( )x x x⋅ ⋅ 2(( ) )x x x x⋅ ⋅ ⋅ 5 4 3 2( ) 2 5 4 3 6 7 ((((2 5) 4) 3) 6) 7f x x x x x x x x x x x= − − + − + = − − + − + 2 5 5 5× − = 5 5 4 21× − = 21 5 3 108× + = 108 5 6 534× − = 534 5 7 2677× + = (5) 2677f = 4 3 2( ) 2 3 5 1f x x x x x= + − + + 4x = → → 1 1 1 0( ) n n n nf x a x a x a x a− −= + + + + 1 1 1 0 1 2 1 0( ) ( ( ) ) )n n n n n n nf x a x a x a x a a x a x a x a x a− − − −= + + + + = + + + + +  首先计算最内层括号内一次多项式的值，即 ，然后由内向外逐层计 算一次多项式的值，即 ， ， ， . ⑥结论：秦九韶算法将求 次多项式的值转化为求 个一次多项式的值，整个过 程只需 次乘法运算和 次加法运算；观察上述 个一次式，可发出 的计算要 用 到 的 值 ， 若 令 ， 可 得 到 下 列 递 推 公 式 ： . 这是一个反复执行的步骤，因此可用循环结构来 实现. ⑦ 练习：用秦九韶算法求多项式 当 时的值并画出程序框图. 2. 小结：秦九韶算法的特点及其程序设计 三、巩固练习：1、练习：教材 P35 第 2 题　　2、作业：教材 P36 第 2 题 第三课时 1.3.3 算法案例---进位制 教学要求：了解各种进位制与十进制之间转换的规律，会利用各种进位制与十进 制之间的联系进行各种进位制之间的转换；学习各种进位制转换成十进制的计算 方法，研究十进制转换为各种进位制的除 k 去余法，并理解其中的数学规律. 教学重点：各种进位制之间的互化. 教学难点：除 k 取余法的理解以及各进位制之间转换的程序框图及其程序的设计. 教学过程： 一、复习准备： 1. 试用秦九韶算法求多项式 当 时的值，分析此过程共需 多少次乘法运算？多少次加法运算？ 2. 提问：生活中我们常见的数字都是十进制的，但是并不是生活中的每一种数 字都是十进制的.比如时间和角度的单位用六十进位制,电子计算机用的是二进 制，旧式的秤是十六进制的，计算一打数值时是 12 进制的......那么什么是进 位制？不同的进位制之间又有什么联系呢？ 二、讲授新课： 1. 教学进位制的概念： ① 进位制是人们为了计数和运算方便而约定的记数系统，“满几进一”就是几进 制，几进制的基数就是几. 如：“满十进一”就是十进制，“满二进一”就是二 进制 . 同一个数可以用不同的进位制来表示，比如：十进数 57，可以用二进 制表示为 111001，也可以用八进制表示为 71、用十六进制表示为 39，它们所代 表的数值都是一样的. 表示各种进位制数一般在数字右下脚加注来表示，如上例 中： ② 一般地，任意一个 进制数都可以表示成不同位上数字与基数的幂的乘积之 和 的 形 式 ， 即 . 如 ： 把 化 为 十 进 制 数 ， =1 25+1 24+0 23+0 22+1 21+1 20=32+16+2+1=51. 把八进制数 化为十进制数， . 2. 教学进位制之间的互化： 1 1n nv a x a −= + 2 1 2nv v x a −= + 3 2 3nv v x a −= +  1 0n nv v x a−= + n n n n n kv 1kv − 0 nv a= 0 1 , ( 1,2, , ) n k k n k v a v v x a k n− − =  = + =  5 4 3 2( ) 5 2 3.5 2.6 1.7 0.8f x x x x x x= + + − + − 5x = 5 2( ) 4 2f x x x= − + 3x =  (2) (8) (16)111001 71 39= = k 1 1 0 1 1 0( ) 1 1 0 1 1 0... (0 ,0 ,..., , ) n n n n k n n n na a a a a k a a a k a k a k a k a k− − − −< < ≤ < = × + × + × + × (2)110011 (2)110011 × × × × × × (8)7348 3 2 1 0 (8)7348 7 8 3 8 4 8 8 8 3816= × + × + × + × =①例 1：把二进制数 化为十进制数. （学生板书 教师点评 师生共同总结将非十进制转为十进制数的方法） 分析此过程的算法过程，编写过程的程序语言. 见 P34 ②练习：将 、 转化成十进制数. ③例 2、把 89 化为二进制数. 分析：根据进位制的定义，二进制就是“满二进一”，可以用 2 连续去除 89 或所 得商，然后取余数. （教师板书） 上述方法也可以推广为把十进制化为 k 进制数的算法,这种算法成为除 k 取余法. ④练习：用除 k 取余法将 89 化为四进制数、六进制数. ⑤例 3、把二进制数 化为十进制数. 解 ： . （小数也可利用上述方法化进行不同进位制之间的互化. ） 变式：化为八进制 方法：进制互化 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)1001101 → → (5)2341 (3)121 (2)11011.101 4 3 2 1 0 1 2 3 (2)11011.101 1 2 1 2 0 2 1 2 1 2 1 2 0 2 1 2 27.625− − −= × + × + × + × + × + × + × + × = →③考虑第一项将会超期的作业以及它左边的所有作业，从中取出花费时间最长的 那项作业，并把它从表中去掉；④回到第二步，并重复第二到四步，直到做完. 2. 孙子问题： 韩信是秦末汉初的著名军事家. 据说有一次汉高祖刘邦在卫士的簇拥下来到 练兵场，刘邦问韩信有什么办法，不要逐个报数，就能知道场上士兵的人数. 韩信先令士兵排成了 3 列纵队进行操练，结果有 2 人多余；接着他立刻下令 将队形改为 5 列纵　队，这一改又多出 3 人；随后他又下令改为 7 列纵队，这一 次又剩下 2 人无法成整行. 由此得出共有士兵 2333 人. 如何用现在的算法思想分 析这一过程？ 《孙子算经》中给出了它的具体解法，其步骤是：选定 的倍数，被 3 除 余 1，即 70；选定 的一个倍数，被 5 除余 1，即 21；选定 的一个倍数， 被 7 除余 1，即 15. 然后按下式计算 ，式中 105 为 的最小公倍数， 为适当的整数，使得 ，这里取 . 求解“孙子问题”的一种普通算法： 第一步： . 第二步：若 除以 3 余 2，则执行第三步；否则 ，执行第二步. 第三步：若 除以 5 余 3，则执行第四步；否则 ，执行第二步. 第四步：若 除以 7 余 2，则执行第五步；否则 ，执行第二步. 第五步：输出 . 3. 小结：算法的基本思想. 三、巩固练习：　　作业：教材 P38 第 3 题　 5 7× 3 7× 3 5× 70 2 21 3 15 2 105m p= × + × + × − 3,5,7 p 0 105m< ≤ 2p = 2m = m 1m m= + m 1m m= + m 1m m= + m