部分第二章§11.1算法案例分析.ppt

知识点二 第二章算法初步 1算法的基本思想 知识点一 理解教材新知 应用创新演练 考点一 把握热点考向 考点二 考点三 1 1算法案例分析 1 1算法案例分析 1 算法是解决某类问题的一系列或 只要按照这些执行 都能使问题得到解决 2 在解决某些问题时 需要设计出一系列可操作或可计算的步骤 通过实施这些步骤来解决问题 通常把这些称为解决这些问题的算法 这种描述不是算法的严格定义 但是反映了算法的基本思想 步骤 程序 步骤 步骤 现代算法的作用之一是使计算机能代替人完成某些工作 算法的主要特征 1 有穷性 一个算法的步骤是有限的 它应在有限步操作之后停止 而不能是无限的 2 确定性 算法中的每一步应该是确定的并且能有效地执行和得到确定的结果 而不应当模棱两可 比如让学生求的近似值却没有要求近似的精确度 不同的学生会得到不同的结果 或者说该问题根本不能求解 3 有序性 算法从初始步骤开始 分为若干明确的步骤 每一个步骤只能有一个确定的后继步骤 前一步是后一步的前提 只有执行完前一步才能进行下一步 并且每一步都要准确无误 才能解决问题 4 不唯一性 求解某一个问题的算法不是唯一的 对于一个问题可以有不同的算法 5 普遍性 很多具体的问题都可以设计合理的算法去解决 如心算 计算器计算都要经过有限的 事先设计好的步骤加以解决 例1 下列对算法的理解不正确的是 A 一个算法应包含有限的步骤 而不能是无限的B 算法可以理解为由基本运算及规定的运算顺序构成的完整的解题步骤C 算法中的每一步都应当有效地执行 并得到确定的结果D 一个问题只能设计出一个算法 思路点拨 先正确理解算法的概念及其特点 然后逐一验证每个选项是否正确 精解详析 答案 D 一点通 解答这类问题的方法为特征判断法 主要从以下三方面判断 1 看是否满足顺序性 算法实际上就是顺序化的解题过程 是指可以用计算机来解决某一类问题的程序或步骤 2 看是否满足明确性 算法的每一步都是确定的 而不是含糊的 模棱两可的 3 看是否满足有限性 一个算法必须在有限步后结束 如果一个解题步骤永远不能结束 那么就永远得不到答案 因此 有始无终的解题步骤不是算法 此外 算法的不唯一性也要考虑到 1 下列叙述能称为算法的个数为 植树需要运苗 挖坑 栽苗 浇水这些步骤 顺序进行下列运算 1 1 2 2 1 3 3 1 4 99 1 100 3x x 1 求所有能被3整除的正数 即3 6 9 12 A 1B 2C 3D 4 解析 根据算法的含义和特征 都是算法 不是算法 其中 3x x 1不是一个明确的逻辑步骤 不符合逻辑性 的步骤是无穷的 与算法的有穷性矛盾 答案 B 2 有关算法的描述有下列几种说法 对一类问题都有效 对个别问题有效 计算可以一步一步地进行 每一步都有唯一的结果 是一种通法 只要按部就班地做 总能得到结果 其中说法正确的是 解析 算法通常是指可以用计算机来解决的某一类问题的程序或步骤 所以 正确 错误 由于程序必须是明确的 有效的 而且在有限步之内完成 故 正确 综上知 正确 答案 例2 写出解方程x2 2x 3 0的一个算法 思路点拨 本题是一个求一元二次方程的解的问题 方法很多 可用配方法 也可用判别式法 精解详析 法一 算法步骤如下 1 移项 得x2 2x 3 2 两边同加1并配方 得 x 1 2 4 3 式两边开方 得x 1 2 4 解 得x 3或x 1 一点通 对于数值型计算问题的算法 可以借助数学公式采用数学计算的方法 将过程分解成清晰的步骤 使之条理化即可 但应注意多个数进行四则运算时应分步计算 依次进行 直到算出结果 3 求过P a1 b1 Q a2 b2 两点的直线斜率有如下的算法 请在横线上填上适当步骤 1 取x1 a1 y1 b1 x2 a2 y2 b2 2 判断 x1 x2 是否成立 若是 则输出 斜率不存在 否则 进行下一步 3 4 输出k 4 写出求1 2 3 4 5 6的一个算法 解 算法一 1 计算1 2得3 2 将第一步中的运算结果3与3相加得到6 3 将第二步中的运算结果6与4相加得到10 4 将第三步中的运算结果10与5相加得到15 5 将第四步中的运算结果15与6相加得到21 算法二 1 将原式变形为 1 6 2 5 3 4 3 7 2 计算3 7 3 得到运算结果 例3 一个人带着三只狼和三只羚羊过河 只有一条船 该船最多可容纳一个人和两只动物 没有人在的时候 如果狼的数量不少于羚羊的数量 狼就会吃羚羊 此人如何才能将动物平安转移过河 请设计一个算法 思路点拨 人和动物同船不用考虑狼会吃羚羊但需考虑承载的数量 另外还应考虑到两岸的动物都得保证狼的数量要小于羚羊的数量 故在算法的设计中应尽可能保证船里面有狼 这样才能使得两岸的羚羊数量占到优势 精解详析 具体算法步骤如下 1 人带两只狼过河 并自己返回 2 人带一只狼过河 并自己返回 3 人带两只羚羊过河 并带两只狼返回 4 人带一只羚羊过河 并自己返回 5 人带两只狼过河 一点通 解决此类问题 需先建立过程模型 通过模型进行算法设计与描述 设计具体的数学问题的算法 实际上就是寻求一类问题的算法 它可以通过计算机来完成 设计算法的关键是把过程分解成若干个明确的步骤 然后用计算机能接受的 语言 准确地描述出来 5 早上从起床到出门需要洗脸刷牙 5min 刷水壶 2min 烧水 8min 泡面 3min 吃饭 10min 听广播 8min 几个步骤 从下列选项中选出较好的一种算法 A 第一步洗脸刷牙 第二步刷水壶 第三步烧水 第四步泡面 第五步吃饭 第六步听广播B 第一步刷水壶 第二步烧水同时洗脸刷牙 第三步泡面 第四步吃饭 第五步听广播 C 第一步刷水壶 第二步烧水同时洗脸刷牙 第三步泡面 第四步吃饭同时听广播D 第一步吃饭同时听广播 第二步泡面 第三步烧水同时洗脸刷牙 第四步刷水壶解析 完成这个过程用时最少的是最好的算法 因此我们可以从四个答案所给出的步骤是否合理 需要花费多少时间入手 答案 C 6 有蓝和黑两个墨水瓶 但现在却错把蓝墨水装在了黑墨水瓶中 黑墨水错装在了蓝墨水瓶中 要求将其互换回来 请设计一个算法解决这个问题 解 算法步骤如下 1 取一只空的墨水瓶 设其为白色 2 将黑墨水瓶中的蓝墨水装入白瓶中 3 将蓝墨水瓶中的黑墨水装入黑墨水瓶中 4 将白瓶中的蓝墨水装入蓝墨水瓶中 5 交换结束 1 写一个算法应遵循由粗到细的处理问题的方法 先确定大的框架 再根据情况具体化 这是设计算法时普遍采用的方法 2 给出一个问题 设计算法时要注意 1 认真分析问题 联系解决此问题的一般数学方法 2 综合考虑此类问题中可能涉及的各种情况 3 将解决问题的过程划分为若干个步骤 点击此图片进入 应用创新演练