高中数学 算法的基本思想1课件 北师大必修3.ppt

1算法的基本思想 课题引入 作为家里的一员 在平时分担一些力所能及的事是我们应尽的义务 你每天都帮家里做事吗 你会烧开水吗 请写出你在家中烧开水的过程 1 往壶内注水 2 点火加热 3 观察 如果水开 则停止烧火 否则继续烧火 4 如果水未开 重复 3 直至水开 总结 1 其实大部分事情都是按照一定的程序执行 因此要理清事情的每一步 2 判断水是否烧开与是否继续烧火的过程是一个反馈与判断过程 因此有必要不断重复过程 3 事实上 我们完成任何事 都要有一个步骤 合理安排步骤 会达到事半功倍的效果 在我们数学的意义来讲 在解决某些问题时 需要设计出一系列可操作或可计算的步骤 通过实施这些步骤来解决问题 我们通常把这些步骤称为解决问题的一种算法 这种描述不是算法的定义 但反映了算法的基本思想 中国古代数学以算法为主要特征 这可以从中国古代数学家的著作中看出端倪 其中最具代表性的就是 九章算术 就其成就来说堪称是世界数学名著 其内容按类分章 以数学问题的形式出现 包括分数四则运算 开平方和开立方 包括二次方程数值的解法 盈不足术 各种面积和体积的计算公式 线性方程组解法 正负数运算的加减法法则 勾股形解法等 另外还有贾宪的 黄帝九章算法细草 刘益 议古根源 秦九韶的 数书九章 杨辉的 详解九章算法 和 杨辉算法 等 随着计算科学和信息技术的飞速发展 算法的思想已经渗透到社会的方方面 在以前的学习中 虽然没有出现算法这个名词 但实际上在数学教学中已经渗透了大量的算法思想 如四则运算的过程 求解方程的步骤等等 完成这些工作都需要一系列程序化的步骤 这就是算法的思想 例1 在中央电视台的 幸运52 节目中 要求参与者快速猜出物品的价格 主持人出示某件物品 参与者每次估算出一个价格 主持人只能回答高了 低了或者正确 在某次节目中 主持人出示了一台价值在1000元以内的随身听 并开始了竞猜 下面是主持人和参与者的一段对话 如果你是参与者 你接下来会怎么猜 800元 高了 400元 600元 低了 高了 参与者 主持人 李咏 例2两个大人和两个小孩一起渡河 渡口只有一条小船每次只能渡1个大人或两个小孩 他们四人都会划船 但都不会游泳试问他们怎样渡过河去 请写出一个渡河方案 s1两个小孩同船过河去 s2一个小孩划船回来 s3一个大人划船过河去 s4对岸的小孩划船回来 s5两个小孩同船渡过河去 s6一个小孩划船回来 s7余下的一个大人独自划船渡过河去 对岸的小孩划船回来 s8两个小孩再同时划船渡过河去 智力大比拼 例3 韩信点兵 问题 韩信是汉高祖刘邦手下的大将 他英勇善战 智谋超群 为建立汉朝立下了汗马功劳 据说他在点兵的时候 为了保住军事机密 不让敌人知道自己部队的实力 采用下述点兵的方法 先令士兵从1 3报数 结果最后一个士兵报2 再令士兵从1 5报数 结果最后一个士兵报3 又令士兵从1 7报数 结果最后一个士兵报4 这样 韩信很快就算出了自己部队的总人数 请设计一个方案 求出士兵至少有多少人 分析 从报数情况分析 总人数除以3余2 总人数除以5余3 总人数除以7余4 算法的第一步是将所有的除以3余2的正整数找出来 按从小到大排成一列 第二步是从第一步的数列中找出除以5余3的一列数 按从小到大排成一列 最后在满足前两个条件的第二步数列中再找出除以7余4的一列数 这列数中最小的数 即为我们所求的数 解 具体算法步骤如下 1 首先确定最小的满足除以3余2的正整数 2 2 依次加3就得到所有除以3余2的正整数 2 5 8 11 14 17 20 23 26 29 32 35 38 41 44 47 50 53 56 3 在上列数中确定最小的满足除以5余3的正整数 8 4 然后依次加上15 得到8 23 38 53 显然这些数既满足除以3余2 又满足除以5余3 5 在第4步得到的一列数中 找出满足除以7余4的最小数 53 这就是我们要求的数 在给定素数表的条件下 请你设计一个算法 将936分成素因数的乘积 解 算法步骤如下 判断936是否为素数 否 确定936的最小素因数 2 936 2 468判断468是否为素数 否 确定468的最小素因数 2 936 2 2 234判断234是否为素数 否 确定234的最小素因数 2 936 2 2 2 117判断117是否为素数 否 确定117的最小素因数 3 936 2 2 2 3 39判断39是否为素数 否 确定39的最小素因数 3 936 2 2 2 3 3 13判断13是否为素数 13是素数 所以分解结束 分解结果是 936 2 2 2 3 3 13 实际操作 写算法的要求 算法不同于求解一个具体问题的方法 是这种方法的高度概括 一个好的算法有如下要求 写出的算法 必须能解决一类问题 如一元二次方程求根公式 并且能重复使用 算法过程要能一步一步执行 每一步执行的操作 必须确切 不能含混不清 而且在有限步能得出结果 算法要简洁 要清晰可读 不能弄搞繁杂 以以致于易程序化 思考以下问题的算法 一位商人有9枚银元 其中有1枚略轻的是假银元 你能用天平 不用砝码 将假银元找出来吗 解 1 把银元分成3组 每组3枚 2 先将两组分别放在天平的两边 如果天平不平衡 那边假银元就放在轻的那一组 如果天平左右平衡 则假银元就在末称的第3组里 3 取出含假银元的那一组 从中任取两枚放在天平的两边 如果左右不平衡 则轻的那一边就是假银元 如果天平两边平衡 则末称的那一枚就是假银元 算法是什么 算法可以理解为由基本运算及规定的运算顺序构成的完整的解题步骤 或看成按要求设计好的有限的 确切的计算序列 并且这样的步骤或序列能解决一类问题 现代意义上的 算法 通常是指可以用计算机来解决的某一类问题的程序或步骤 说明 1算法实际上就是解决某一类问题的步骤和方法 在解决问题时形成的规律性的东西 按照算法描述的规则与步骤 一步一步地去做 最终便能解决问题 2算法的基本思想就是我们分析问题时的想法 由于想法不同思考的角度不同 着手点不一样 同一问题存在不同的算法 算法有优劣之分 3从熟悉的问题出发 体会算法的程序化思想 学会用自然语言来描述算法 求方程在 0 5 上的近似解 精确到0 05 分析 如何求方程的根 我们可以参考p91 92 解法1 1 移项 得 2 两边同时加1并配方得 3 两边同时开放得 x 3或x 1 4 取x 3 解法2 1因为f 0 3 f 5 12 f 0 f 5 0 05 2取 0 5 的中点2 5 计算f 2 5 1 75 则f 5 f 2 5 0 01 3取 2 5 5 的中点3 75 计算f 3 75 3 5625 则f 2 5 f 3 5625 0 05 4取 2 5 3 5625 的中点3 03125 则f 3 03125 0 12598 则f 3 03125 f 2 5 0 05 5取 2 5 3 03125 的中点2 765625 则f 2 765625 0 88257 精度 3 03125 2 765625 0 2657 0 05 6取 2 765625 3 03125 的中点2 8984 f 2 8984 0 340 则f 2 8984 f 3 03125 0 05 7取 2 8984 3 03125 的中点2 9648 则f 2 96 0 140 则f 3 03125 f 2 9648 0 01 8取 2 9648 3 031 的中点3 009 则f 3 009 0 008 则f 3 009 f 2 965 0 精度 3 009 2 965 0 045 0 05 9取 3 009 2 965 的中点2 99 则x 2 99 算法的特征 有穷性 一个算法应包含有限的操作步骤而不能是无限的 确定性 算法中每一个步骤应当是确定的 而不应当是含糊的 模棱两可的 有效性 算法中每一个步骤应当能有效地执行 并得到确定