[理学]李玲玲C课件最终版-第二章.ppt

第二章 算 法 教学目与要求 理解算法的含义 掌握算法的特性和怎样表示一个算法 掌握结构化程序设计的三种基本结构及设计方法 教学内容 算法的概念 算法的特性和怎样表示一个算法 结构化程序设计的三种基本结构 教学重点与难点 算法的特征与算法的表示 结构化程序设计的三种基本结构 提纲 2.1 算法的概念 2.2 简单算法举例 2.3 算法的特性 2.4 算法的表示 2.5 结构化程序设计方法 2.1 算法的概念 算法就是解决一个问题所采取的步骤 算法的好坏决定了解决问题的效率 炒肉片 买肉(20)→切肉(1)→切葱(0.5)→热锅(2)→炒肉(3) 耗时26.5 买肉(20)→热锅(2) →炒肉(3)　　　　 →切肉(1)→切葱(0.5) → 耗时25 在12 23 25 33 45 57 80这列数中定位到57　12→23→25→33→45→57 6步 33→57 2步 2.1 算法的概念 算法的分类 数值运算算法： 求数值解 非数值运算算法： 事物管理领域 2.2 简单算法举例 例1 求1×2×3×4×5 最原始的方法： 求1×2, 得结果2。 将第1步得到的结果再乘以3, 得结果6。 将第2步得到的结果再乘以4, 得结果24。 将第3步得到的结果再乘以5, 得120。即最后结果。 算法正确，但过于繁琐 如果问题改成求1×2×3×...×1000，需要999步才行。 2.2 简单算法举例 改进的方法： 先设两个变量p和i，p代表被乘数，i代表乘数；将每一步乘积直接放入被乘数变量p中；用循环算法求结果。 令p=1 令i=2 使p×i，并将乘积放入p中，表示为p=p×i 使 i 的值加1，表示为i= i+1 如果i不大于5，返回到步骤3继续向下执行；否则算法结束，p中的值即最后结果。 算法简练通用 如果改成求1×2×3×...×1000，只需将步骤5中对i的判断改成1000既可。 2.2 简单算法举例 如果改成1×3×5×7×9×11×13，算法如下： 令p=1 令i=3 使p×i，并将乘积放入p中，表示为p=p×i 使 i 的值加2，表示为 i=i+2 如果i不大于13，返回到步骤3继续向下执行；否则算法结束，p中的值即最后结果。 2.2 简单算法举例 例2 有50个学生，要求将他们之中成绩在80分以上者打印出来。 用i表示序号，ni表示第i个学生的学号，gi表示该学生的成绩。算法： 令i=1 如果gi≥80，打印ni和gi。 i=i+1 如果i不大于50，返回到步骤2继续向下执行；否则算法结束。 2.3 算法特性 有穷性 有限的操作步骤 确定性 每一个步骤都是确定的 有零个或多个输入 输入：在执行算法时从外界取得的信息 有一个或多个输出 算法的目的是为了求解，得到结果 有效性 每个步骤都能有效执行，并得到确定的结果 2.4 算法的表示 常用的算法表示方法： 自然语言 传统流程图 结构化流程图 N-S流程图 伪代码 计算机语言 一、用自然语言表示 自然语言指人们日常使用的语言，如汉语、英语等 2.2节中介绍的算法是用自然语言写的 用自然语言表示算法通俗易懂，但不严谨，容易产生歧义 除非问题很简单，一般不用自然语言描述算法 二、用流程图表示 流程图是用一些图框表示各种操作。 用流程图表示算法直观形象，易于理解。 美国国家标准化协会ANSI规定了一些常用的流程图符号。 二、用流程图表示 小结： 一个流程图包括以下几个部分： 表示相应操作的框 带箭头的流程线 框内必要的文字说明 三、三种基本结构和改进的流程图 传统流程图的弊端 流程线的大量使用造成阅读困难，修改困难 三种基本结构 顺序结构 选择结构 循环结构 顺序结构 三、三种基本结构和改进的流程图 3. 三种基本结构的共同点 只有一个入口 一个出口 结构内每一部分都有机会被执行 结构内不存在“死循环” 三、三种基本结构和改进的流程图 已经证明，用上述三种基本结构顺序组成的算法结构，可以解决任何复杂的问题。 由基本结构构成的算法属于“结构化”的算法，不存在无规律的转向。 只要符合上述的四个特点的结构，都称为基本结构。 四、用N-S流程图表示算法 1973年，Nassi和Shneiderman提出，也称盒图。 完全取