C语言.ppt

2020 1 3 1 第二章算法及算法设计 2 1算法的概念 2 2算法的设计与表述2 3简单的算法实例2 4结构化程序设计方法简介 2020 1 3 2 2 1算法的概念 算法 是对解决某个问题的方法步骤的描述 程序 计算机操作指令的集合 是用某种计算机能理解并执行的计算机语言描述解决问题的方法和步骤 任何一个程序应包含的如下两方面的内容 1 对数据的描述 在程序中要指定数据的类型和数据的组织形式 即数据结构 datastructure 2 对操作的描述 即操作步骤 也就是算法 algorithm 著名计算机科学家沃思 NikiklausWirth 提出公式数据结构 算法 程序 对数据的描述 对操作的描述 2020 1 3 3 实际上 一个程序除了数据结构 算法主要要素之外 还应当采用结构化程序设计方法进行程序设计 并且用某一种计算机语言表示 因此 可以这样表示 程序 算法 数据结构 程序设计方法 语言工具和环境在这4个方面中 算法是灵魂 数据结构是加工对象 语言是工具 编程需要采用合适的算法 算法是解决 做什么 和 怎么做 的问题 2020 1 3 4 1 什么叫算法 解决一个问题而采取的方法和步骤 就称为算法 2 算法的特性 1 有穷性一个算法应包含有限的操作步骤而不是无限的 2 确定性算法中的每一个步骤都应当是确定的 而不应当是含糊的 模棱两可的 3 有零个或多个输入所谓输入即在执行算法时需要从外界取得必要的信息 4 有一个或多个输出算法的目的是为了求解 解 就是输出 没有输出的算法是没有意义的 5 有效性算法中的每一个步骤都应当能有效地执行 并得到确定结果 2020 1 3 5 2 2算法的设计与表述 1 用自然语言表示算法采用汉语 英语或其它语言来描述解决问题的方法和步骤 2020 1 3 6 例1 有50个学生 要求将他们之中成绩在80分以上者打印出来 用n表示学号 n1代表第一个学生学号 ni代表第i个学生学号 用g代表学生成绩 gi代表第i个学生成绩 算法可表示如下 S1 1 iS2 读入学号ni和成绩giS3 如果gi 80 则打印ni和gi 否则不打印S4 i 1 iS5 如果i 50 返回S2 继续执行 否则 算法结束 S1 S5 表示算法步骤 由于自然语言描述问题文字冗长 且容易出现 歧义性 因此一般很少使用自然语言来描述算法 2020 1 3 7 2 用流程图表示算法 1 常用的流程图符号 2 N S流程图符号 2020 1 3 8 N S流程图是1973年美国学者I Nassi和B Shneiderman提出的一种新流程图形式 这种流程图完全去掉了带箭头的流程线 全部算法写在一个矩形框内 该框内还可包含其他从属于它的框 这种流程图又称N S结构化流程图 用顺序 分支 循环3种N S流程图的基本框 可以组成复杂的N S流程图 以表示算法 2020 1 3 9 常用流程图 用流程图表示例1算法 N S流程图 2020 1 3 10 流程图表示算法的优势 表示算法直观形象 比较清楚地显示出各个框之间的逻辑关系 简单 易于掌握 对应编程逻辑性强 不易出错 2020 1 3 11 3 用伪代码表示算法 伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法 而不用图形符号描述 因此书写容易 格式紧凑 也比较好懂 便于向计算机语言算法 即程序 过渡 用伪代码表示例1算法BEGIN 算法开始 i 1whilei 80printniandgii i 1 END 算法结束 2020 1 3 12 4 用计算机语言表示算法 程序 设计算法的目的是为了实现算法 首先考虑如何设计一个算法其次考虑如何实现一个算法 我们的任务是用计算机实现算法 即用计算机语言编写程序 经系统编译成目标程序 使计算机执行以实现算法 因此 用流程图或伪代码描述的算法 需转换成计算机语言程序 2020 1 3 13 用计算机语言表示例1算法 伪代码的转换 伪代码算法BEGIN 算法开始 i 1whilei 80outputniandgii i 1 END 算法结束 计算机C语言算法 程序 voidmain intg 50 n 50 i 1 while i 80 printf 6d 3d n n i g i i i 1 2020 1 3 14 C语言程序设计的基本结构 1 顺序结构 2020 1 3 15 2 选择结构 或称选取结构 此结构中必包含一个判断框 根据给定的条件P是否成立而选择执行A框或B框 2020 1 3 16 l 3 循环结构 它又称为重复结构 即反复执行某一部分的操作 又两类循环结构 a 当型 while型 循环结构 它的功能是判断当前给定的条件p1成立时 执行A框操作 执行完A后 再判断条件p1是否成立 如果仍然成立 再执行A框 如此反复执行A框 直到某一次p1条件不成立为止 此时不执行A框 而从b点脱离循环结构 2020 1 3 17 b 直到型 Until型 循环结构 它的功能是先执行A框 然后判断给定的p2条件是否成立 如果p2条件不成立 则再执行A 然后再对p2条件作判断 如果p2条件仍然不成立 又执行A 如此反复执行A 直到给定的p2条件成立为止 此时不再执行A 从b点脱离本循环结构 2020 1 3 18 2 4结构化程序设计方法简介 1 三种基本结构回顾 1 顺序结构 2 选择结构 3 循环结构 2020 1 3 19 1 只有一个入口 2 只有一个出口 注意 一个菱形判断框有两个出口 而一个选择结构只有一个出口 两者不要混淆 3 结构的每一部分都有机会被执行到 对每一个框 都有从入口到出口的路径通过它 4 结构内不存在 无限循环 无终结循环 2 三种基本结构的共同特点 2020 1 3 20 3 结构化程序 所谓结构化程序 就是使用顺序 选择 循环等三种基本结构所构造的程序 4 结构化程序设计结构化程序设计方法的基本思想是 把一个复杂问题的求解过程分阶段进行 每个阶段的问题都控制在人们容易理解和处理的范围内 具体的说 采用以下方法保证得到结构化的程序 1 自顶而下 2 逐步求精 3 模