《C语言程序设计》算法及算法设计简介.ppt

1 武汉理工大学计算机学院 授课教师： C语言程序设计 2 第二章 算法及算法设计简介 2.1 算法的概念 2.2 算法的设计与表达 2.3 简单的算法实例 2.4 结构化程序设计方法简介 3 算法的概念 任何一个程序应包含的如下两方面的内容： (1)对数据的描述。在程序中要指定数据的类型和数据的组织形式，即数据结构(data structure). (2)对操作的描述。即操作步骤，也就是算法(algorithm)。 著名计算机科学家沃思(Nikiklaus Wirth)提出公式 数据结构＋算法＝程序 算法：是对解决某个问题的方法步骤的描述。 程序：从计算机角度来说，程序是用某种计算机能理解并执 行的计算机语言描述解决问题的方法和步骤。 4 实际上，一个程序除了以上两个主要要素之外，还应当采用 结构化程序设计方法进行程序设计，并且用某一种计算机语 言表示。因此，可以这样表示： 程序＝算法＋数据结构＋程序设计方法＋语言工具和环境 在这4个方面中，算法是灵魂，数据结构是加工对象，语言 是工具，编程需要采用合适的算法。算法是解决“做什么” 和“怎么做”的问题。 5 算法的表示 1、用自然语言表示算法 采用汉语、英语或其它语言来描述解决问题的方法和步骤。 由于自然语言容易出现“歧义性”，且描述问题的文字冗长， 因此一般很少使用自然语言来描述算法。 6 例1： 有50个学生 ，要求将他们之中成绩在80分以上者打印出来。用n表示学号，n1代表第一个学生学号，ni代表第i个学生学号。用g代表学生成绩， gi 代表第i个学生成绩，算法可表示如下： S1：1?i S2：读入学号ni和成绩gi S3: 如果gi ?80 ，则打印 ni 和gi ，否则不打印 S4： i+1 ?i S5: 如果 i? 50, 返回S2， 继续执行； 否则，算法结束。 7 2、用流程图表示算法 （1）常用的流程图符号 8 上例用流程图表示： （1）? 流程图表示算法的优点： ①表示算法直观形象，比较清楚地显示出各个框之间 的逻辑关系。 ②简单，易于掌握。 流程图 9 3、用N－S图表示算法 1973年美国学者I.Nassi和B.Shneiderman提出了 一种新的流程图形式。在这种流程图中，完全去掉 了带箭头的流程线。全部算法写在一个矩形框内， 在该框内还可以包含其他的从属于它的框。 这种流程图又称N—S结构化流程图。 N—S流程图用以下的流程图符号： （1）顺序结构： A B 10 （2）选择结构： P 成立 不成立 A B （3）循环结构： 当p1成立 A 当型循环结构 直到p1成立 A 直到型循环结构 用以上3种N—S流程图中的基本框，可以组成复杂的N—S流程图，以表示算法 11 上例用N－S图表示： 用N—S表示算法如图 12 4、用伪码表示算法 伪代码是用介于自然语言和计算机语言之间的文字和符号来 描述算法。它不用图形符号，因此书写方便，格式紧凑，也 比较好懂，便于向计算机语言算法（即程序）过渡。 例 有50个学生，要求将他们之中成绩在80分以上者打印出来。 用n表示学生学号，n1表示第一个学生学号，ni表示第i个学生 学号。用g表示学生成绩，gi表示第i个学生成绩。 13 BEGIN(算法开始) 1=i While i=50 { input ni and gi if gi≥80 print ni and gi i+1=i } END（算法结束） 用伪代码表示算法如下： 14 5、用计算机语言表示算法 设计算法的目的是为了实现算法。因此，不仅要考 虑如何设计一个算法，也要考虑如何实现一个算法。 我们的任务是用计算机解题，也就是要用计算机实 现算法。计算机是无法识别流程图和伪代码的。只 有用计算机语言编写的程序才能被计算机执行（当 然还要经过编译成目标程序才能被计算机识别和执 行）。因此，在用流程图或伪代码描述出一个算法 后，还要将它转换成计算机语言程序。 15 例： 有50个学生，要求将他们之中成绩在80分以上者打印出来。 用n表示学生学号，n1表示第一个学生学号，ni表示第i个学生 学号。用g表示学生成绩，gi表示第i个学生成绩。 C语言程序如下： main( ) { int g[50],n[50],i; for(i=0;i50;i++) scanf(“%d,%d”,n[i],g[i]);