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

知识点二;1．1　算法案例分析; (1)算法是解决某类问题的一系列 或 ，只要按照这些 执行，都能使问题得到解决． (2)在解决某些问题时，需要设计出一系列可操作或可计算的步骤，通过实施这些步骤来解决问题，通常把这些 称为解决这些问题的算法．这种描述不是算法的严格定义，但是反映了算法的基本思想．; 现代算法的作用之一是使计算机能代替人完成某些工作．; (3)有序性：算法从初始步骤开始，分为若干明确的步骤，每一个步骤只能有一个确定的后继步骤，前一步是后一步的前提，只有执行完前一步才能进行下一步，并且每一步都要准确无误，才能解决问题． (4)不唯一性：求解某一个问题的算法不是唯一的，对于一个问题可以有不同的算法． (5)普遍性：很多具体的问题都可以设计合理的算法去解决，如心算、计算器计算都要经过有限的、事先设计好的步骤加以解决．;　 [例1]　下列对算法的理解不正确的是 (　　) A．一个算法应包含有限的步骤，而不能是无限的 B．算法可以理解为由基本运算及规定的运算顺序构成的完整的解题步骤 C．算法中的每一步都应当有效地执行，并得到确定的结果 D．一个问题只能设计出一个算法 [思路点拨]　先正确理解算法的概念及其特点，然后逐一验证每个选项是否正确．;[精解详析]; [一点通]　解答这类问题的方法为特征判断法，主要从以下三方面判断： (1)看是否满足顺序性．算法实际上就是顺序化的解题过程，是指可以用计算机来解决某一类问题的程序或步骤． (2)看是否满足明确性．算法的每一步都是确定的，而不是含糊的、模棱两可的． (3)看是否满足有限性．一个算法必须在有限步后结束．如果一个解题步骤永远不能结束，那么就永远得不到答案．因此，有始无终的解题步骤不是算法． 此外，算法的不唯一性也要考虑到．;1．下列叙述能称为算法的个数为 (　　) ①植树需要运苗、挖坑、栽苗、浇水这些步骤． ②顺序进行下列运算：1＋1＝2,2＋1＝3,3＋1＝4，…，99＋1＝100. ③3xx＋1. ④求所有能被3整除的正数，即3,6,9,12，…. A．1　　　　　　　　　　　 B．2 C．3 D．4;解析：根据算法的含义和特征：①②都是算法．③④不是算法．其中③，3xx＋1不是一个明确的逻辑步骤，不符合逻辑性；④的步骤是无穷的，与算法的有穷性矛盾．;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]　一个人带着三只狼和三只羚羊过河，只有一条船，该船最多可容纳一个人和两只动物．没有人在的时候，如果狼的数量不少于羚羊