苏教版必修三第09课时《算法案例》word教案

1、文档编码 : CX3O7W3N1K9 HW9M5S6S10L5 ZF6V9C4A10U3总 课 题名师精编优秀教案总课时第 9 课时算法案例分 课 题算法案例分课时第 1 课时通过明白中国古代算法案例, 体会中国古代数学对世界数学进展的教学目标贡献重点难点 通过案例分析,体会算法思想,娴熟算法设计例题剖析【案例 1】韩信是秦末汉初的著名军事家,据说有一次汉高祖刘邦在卫士的簇拥下来到练兵场,刘邦问韩信有什么方法,不要逐个报数,就能知道场上士兵的人数韩信先令士兵排成 3 列纵队,结果有 2 人余外；接着他立刻下令将队形改为 5 列纵队,这一改,又多出 3 人；随后他又下令改为 7 列纵队,这一次又

2、剩下 2 人无法成整行韩信看此情形,立刻报告共有士兵 2333 人众人都愣了,不知韩信用什么方法清点出精确人数的这个故事是否属实,已无从查考, 但这个故事却引出一个著名的数学问题,即著名世界的“ 孙子问题”这种神机妙算,最早显现在我国算经十书之一的孙子算经中,原文是：“ 今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何？答曰：二十三”所以人们将这种问题的通用解法称为“ 孙子剩余定理” 或“ 中国剩余定理”【算法设计思想】m 3 x 2“ 孙子问题” 相当于求关于 x,y,z 的不定方程组 m 5 y 3 的整数解m 7 z 2设所求的数为 m ,依据题意,m 应同时中意以下三

3、个条件：（1） m被 3 除后余 2 ,即 Mod m,3 2；（2） m被 5 除后余 3 ,即 Mod m,5 3；（3） m被 7 除后余 2 ,即 Mod m,7 2；第一,从 m 2 开头检验条件,如 3个条件中有任何一个不中意,就 m 递增 1,当 m 同时中意 3 个条件时,输出 m 【流程图】【伪代码】名师精编 优秀教案【案例 2】写出求两个正整数 a , b a b 的最大公约数的一个算法公元前 3 世纪, 欧几里得介绍了求两个正整数 a,b a b 的最大公约数的方法,即求出一列数：a,b,r 1,r 2,r n 1,r n,0,这列数从第三项开头,每一项都是前两项相除所得

4、的余数（即 r n Mod r n 2,r n 1 ）,余数等于 0 的前一项 nr ,即是 a 和 b 的最大公约数,这种方法称为“ 欧几里得辗转相除法”【算法设计思想】欧几里得展转相除法求两个正整数 a,b 的最大公约数的步骤是：运算出 a b 的余数r ,如 r 0,就 b 即为 a,b 的最大公约数； 如 r 0,就把前面的除数 b 作为新的被除数,把余数 r 作为新的除数,连续运算,直到余数为 0 ,此时的除数即为 a,b 的最大公约数求 a,b a b 的最大公约数的算法为：S 1 输入两个正整数 a,b；S 2 假如 Mod a,b 0,那么转 S ,否就转 S 6；S 3 r

5、Mod a,b ；S 4 a b；S 5 b r,转 S 2；S 6 输出 b 【流程图】【伪代码】【案例 3】写出方程x3x10在区间1,1内的一个近似解（误差不超过0 .001）的一个算法【算法设计思想】如下图：假如设计出方程 f x 0 在某区间 a,b 内有一个根 x,就能用二分搜寻求得符合误差限制 c的近似解算法步骤可表示为：S 1 取 a,b 的中点 x 0 1 a b ,将区间一分为二；2S 2 如 f x 0,就 0 x 就是方程的根,否就判定根 x 在 x 的左侧仍是右侧；如 f a f x 0 0,就 x x 0b ,以 x 代替 a ；如 f a f x 0 0,就 x

6、a , x 0 ,以 x 代替 b ；S 3 如 a b c,运算终止,此时 x 0 x,否就转 S 【流程图】【伪代码】名师精编 优秀教案巩固练习1下面一段伪代码的目的是_ Readm , nmOa0yx0fxfb b0While mIntxnnm ncmnIntm n Endn cWhile Printnfa注明： 案例 3 的图2在直角坐标系中作出函数yx 2 和y4x的图像,依据图像判定方程2x4x的解的范畴,再用二分法求这个方程的近似解（误差不超过0 .001）,并写出这个算法的伪代码,画出流程图课堂小结通过案例分析, 体会算法思想, 娴熟算法设计,进一步懂得算法的基本思想,在分析案

7、 例的过程中设计规范合理的算法名师精编 优秀教案课后训练一基础题班级：高二（）班姓名： _ 1一种放射性物质不断变化为其它物质,每经过一年剩留下来的物质的质量约为原先,那么,约经过多少年,剩留的质量是原先的一半？试写出运用二分法运算这个近似值的伪代码2设计一个算法,运算两个正整数a,b的最小公倍数二 提高题3判定某年份是否为闰年,要看此年份数能否被 4 整除如不能被 4 整除就是平年,2 月是 28 天；如能被 4 整除但不能被 100 整除,就该年是闰年,2 月是 29 天；如能被 4 整除又能被 100 整除, 仍要看能否被 400 整除, 如能就为闰年,否就为平年画出上述算法的流程图,并写出伪代码4我国古代劳动人民对不定方程的争论作出过重要贡献,其中张丘建算经中的“ 百鸡问题” 就是一个很有影响力的不定方程问题,今有鸡翁一值钱五,鸡母一值钱三,鸡雏三值钱一,凡百钱买百只,问鸡翁、鸡母、鸡雏各几何其意思是：一只公鸡的价格是 5 钱,一只母鸡的价格是 3 钱,三只小鸡的价格是 1钱,想用 100 钱买100 只鸡,问公鸡、母鸡、小鸡个买几只设 x,y,z 分别代表公鸡、母鸡、小鸡的只数,我们可以大致确定 x,y,z 的取值范畴：如 100 钱全买公鸡,就最多可买