算法的基本思想.ppt

随着计算机科学和信息技术的飞速发展 计算机已经被应用到了我们生活的方方面面 那么计算机是怎样工作的呢 这就要用到算法的思想 在以前的学习中 虽然没有出现算法这个名词 在数学学习中已经学习到了大量的算法的思想 例如四则运算的过程 求解方程的步骤等等 完成这些工作都需要一系列程序化的步骤 这就是算法的思想 本章中 我们将介绍算法的基本思想 基本结构和描述算法的基本语句 这对我们理解数学与计算机技术的关系是有很大帮助的 算法的基本思想 例1 在电视台的某个娱乐节目中 要求参与者快速猜出物品的价格 主持人出示某件物品 参与者每次估算出一个价格 主持人只能回答高了 低了或者正确 在某次节目中 主持人出示了一台价值在1000元以内的随身听 并开始了竞猜 下面是主持人和参与者的一段对话 如果你是参与者 你接下来会怎么猜 800元 高了 400元 600元 低了 高了 参与者 主持人 李咏 例2 给定素数表 设计算法 将936分解成素因数的乘积 判断936是否为素数 否 2 936 468 2 936 234 22 936 117 23 否 2 否 2 否 936 39 23 3 3 否 3 936 13 23 32 是 结束 分解结果为 936 13 23 32 练习 将下列两个数分解素因数 1 840 2 1764 例3 设计一个算法 求840与1764的最大公因数 解 算法步骤如下 1 先将840进行素因数分解 840 23 3 5 7 3 确定它们公共素因数 2 3 7 4 确定公共素因数的指数 公共素因数2 3 7的指数分别为2 1 1 2 先将1764进行素因数分解 1764 22 32 72 5 最大公因数为 22 31 71 84 写算法的要求 写出的算法 必须能解决一类问题 如求两个正整数的最大公因数 并且能重复使用 算法过程要一步一步执行 每一步执行的操作必须明确 不能含混不清 而且在有限步骤内能得出结果 算法要简洁 清晰可读 不能搞得繁杂 算法不同于求解一个具体问题的方法 是这种方法的高度概括 一个好的算法有如下要求 算法是什么 算法可以理解为由基本运算及规定的运算顺序构成的一个完整的解题步骤 或看成是按要求设计好的有限的 确切的计算步骤 并且这样的步骤能解决一类问题 现代意义上的 算法 通常是指可以用计算机来解决的某一类问题的程序或步骤 韩信点兵 问题 思考以下问题的算法 一位商人有9枚银元 其中有1枚略轻的是假银元 你能用天平 不用砝码 将假银元找出来吗 解 2 先将两组分别放在天平的两边 如果天平不平衡 那边假银元就放在轻的那一组 如果天平左右平衡 则假银元就在末称的第3组里 3 取出含假银元的那一组 从中任取两枚放在天平的两边 如果左右不平衡 则轻的那一边就是假银元 如果天平两边平衡 则末称的那一枚就是假银元 1 把银元分成3组 每组3枚 说明 1算法实际上就是解决某一类问题的步骤和方法 在解决问题时形成的规律性的东西 按照算法描述的规则与步骤 一步一步地去做 最终便能解决问题 2算法的基本思想就是我们分析问题时的想法 由于想法不同思考的角度不同 着手点不一样 同一问题存在不同的算法 算法有优劣之分 3从熟悉的问题出发 体会算法的程序化思想 学会用自然语言来描述算法 算法的特点 有限性 一个算法的步骤必须是有限的 必须在有限操作之后停止 不能是无限的 确定性 算法中的每一步应该是确定的并且能有效地执行且得到确定的结果 而不应当是模棱两可 普遍性 一个算法通常设计成能解决一类问题 不不唯一性 求解某一个问题的解法不一定是唯一的 对于一个问题可以有不同的算法 是仅仅解决一个单独问题的 例四设函数f x 的图象是一条连续不断的曲线 写出用 二分法 求方程f x 0的一个近似解的算法 第一步 取函数f x 给定精确度d 第二步 确定区间 a b 满足f a f b 0 第五步 判断 a b 的长度是否小于d或f m 是否等于0 若是 则m是方程的近似解 否则 返回第三步 第三步 取区间中点 第四步 若f a f m 0 则含零点的区间为 a m 否则 含零点的区间为 m b 将新得到的含零点的区间仍记为 a b 两个大人和两个小孩一起渡河 渡口只有一条小船每次只能渡1个大人或两个小孩 他们四人都会划船 但都不会游泳试问他们怎样渡过河去 请写出一个渡河方案 S1两个小孩同船过河去 S2一个小孩划船回来 S3