高中数学第一章算法初步1.4算法案例课件苏教版必修3.ppt

第1章算法初步 1 4算法案例 学习目标1 理解解决 韩信点兵 孙子问题 的算法思想 2 理解辗转相除法与更相减损术的数学原理 3 能用伪代码实现二分法求方程的近似解 题型探究 问题导学 内容索引 当堂训练 问题导学 知识点一本节涉及的内置函数 就像木工不必自己造锯一样 VB也把一些常用基础工具做成内置函数 以备使用者直接调用 下面是本节涉及的内置函数 思考 知识点二 韩信点兵一孙子问题 的数学本质 三三数之剩二 是什么意思 如何用代数式表示 三三数之剩二 意思是一堆东西 三个三个地分组 余二个 设这堆东西数目为m 则m 3x 2 其中x指组数 答案 梳理 韩信点兵 孙子问题 是求关于x y z的一次不定方程组 的正整数解 思考 知识点三辗转相除法与更相减损术的算法原理 我们知道204 85 2 34 为什么204与85的最大公约数就是85与34的最大公约数 设204与85的最大公约数为a 则a能整除204 故能整除85 2 34 又因为a也是85的约数 故a能整除85 2 所以a必能整除34 即a是34的约数 从而是85与34的最大公约数 显然 204与85的公约数问题转化成了85与34的公约数问题 问题难度降低了 答案 梳理 一般地 有2种算法求两个正整数的最大公约数 1 辗转相除法的运算步骤 第一步 给定 第二步 计算 第三步 第四步 若r 0 则m n的最大公约数等于 否则 返回 第二步 两个正整数m n m n m除以n所得的余数r m n n r m 2 更相减损术的运算步骤 第一步 任意给定两个正整数 判断它们是否都是 若是 用约简 若不是 执行 第二步 以的数减去的数 接着把所得的差与的数比较 并以大数减小数 继续这个操作 直到所得的数为止 则这个数 等数 或这个数与约简的数的乘积就是所求的最大公约数 相等 偶数 2 第二步 较大 较小 较小 思考 知识点四二分法的实现 你还能回忆起二分法的作用和原理吗 二分法是用来求方程近似解的 其原理是先确定一个解所在的大致区间 然后借助零点存在定理 不断缩小这个区间 答案 梳理 求方程f x 0在区间 a b 上的近似解的步骤为 S1取 a b 的中点x0 a b 将区间一分为二 S2若 则x0就是方程的根 否则判断根x 在x0的左侧还是右侧 若 则x x0 b 以x0代替a 若 则x a x0 以x0代替b S3若 a b c 计算终止 此时 否则转 S1 f x0 0f a f x0 0f a f x0 0 x x0 题型探究 类型一 韩信点兵 孙子问题 例1韩信是秦末汉初的著名军事家 据说有一次汉高祖刘邦在卫士的簇拥下来到练兵场 刘邦问韩信有什么办法 不要逐个报数 就能知道场上士兵的人数 韩信先令士兵排成3列纵队进行操练 结果有2人多余 接着他立刻下令将队形改为5列纵队 这一改 又多出3人 随后他又下令改为7列纵队 这一次又剩下2人无法成整列 结果在场的人哈哈大笑 韩信看此情形 立刻报告共有士兵2333人 众人都愣了 不知韩信用什么办法这么快清点出准确人数的 这个故事却引出一个著名的数学问题 即闻名世界的 孙子问题 最早出现在我国 算经十书 之一的 孙子算经 中 原文是 今有物不知其数 三三数之剩二 五五数之剩三 七七数之剩二 问物几何 答曰 二十三 所以人们将这种问题的通用解法称为 孙子剩余定理 或 中国剩余定理 设有物m个 则其本质为由方程组求m的正整数解 试为此问题编写流程图和伪代码 解答 流程图为 伪代码为 此算法的本质是从最小2开始 逐个实验是否满足方程组 对人而言是个笨法 但很适合计算机 以上程序求出的是m的最小值 反思与感悟 跟踪训练1有一堆围棋子 五个五个地数 最后余下2个 七个七个地数 最后余下3个 九个九个地数 最后余下4个 请用伪代码表示 求出这堆棋子至少有多少个 的一种算法 算法的伪代码如下 解答 例2你能根据 欧几里得辗转相除法 设计一种求两个正整数a b a b 的最大公约数的一个算法吗 并画出流程图 编写伪代码 类型二辗转相除法的现代实现 解答 算法如下 S1输入两个正整数a b S2若Mod a b 0 那么转S3 否则转S6 S3r Mod a b S4a b S5b r 转S2 S6输出b 流程图如图 伪代码如下 利用辗转相除法求给定的两个数的最大公约数 即利用带余除法 用数对中较大的数除以较小的数 若余数不为零 则将余数和较小的数构成新的数对 再利用带余除法 直到大数被小数除尽 则这时的较小数就是原来两个数的最大公约数 反思与感悟 跟踪训练2用辗转相除法和更相减损术求261和319的最大公约数 解答 辗转相除法 319 261 1 余58 261 58 4 余29 58 29 2 余0 所以319与261的最大公约数为29 更相减损术 319 261 58 261 58 203 203 58 145 145 58 87 87 58 29 58 29 29 29 29 0 所以319与261的最大公约数是29 类型三求方程f x 0近似解的算法 例3画出用区间二分法求方程x3 x 1 0在区间 1 1 5 上的一个近似解 误差不超过0 001 的一个算法流程图并编写伪代码 解答 流程图如图 伪代码如图 在此算法中用到了条件语句和循环语句 所以用 Do 是因为要执行再判断是否满足条件 因为不知循环次数 所以也不宜用 For 语句 反思与感悟 跟踪训练3改造例3中伪代码 用来求f x lnx 2x 1在区间 a b 上的一个近似解 误差不超过c 解析 伪代码如图 当堂训练 2 3 4 1 1 m是一正整数 对两个正整数a b 若a b是m的倍数 则称模m同余 用符号a b Modm 表示 则a 5 Mod27 中 a的取值最小为 答案 32 2 用更相减损术求36与134的最大公约数 第一步应为 36与134都是偶数 第一步应为 先除以2 得到18与67 先除以2 得到18与67 2 3 4 1 答案 解析 3 求方程x 5y 3 其中y为自然数 的所有小于100的x的正整数解 用伪代码表示 算法的伪代码如图 解答 2 3 4 1 4 求两个正数8251和6105的最大公约数 8251 6105 1 2146 6105 2146 2 1813 2146 1813 1 333 1813 333 5 148 333 148 2 37 148 37 4 0 则37为8251与6105的最大公约数 解答 2 3 4 1 规律与方法 1 求两个正整数的最大公约数时 用辗转相除法进行设计的关键是 将 辗转 的过程用循环语句表示 为了避免求循环次数 对两个具体的正整数 循环次数可