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

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