程序设计基础知识.pptx
C语言程序设计,计算机学院谭忠兵,目 录,程序与程序语言,算法和算法表示,第1章 程序设计基础知识,C语言程序设计 第一章 程序设计基础知识,结构化程序设计方法,C语言程序设计 第一章 程序设计基础知识,1.1 程序与程序语言程序语言的发展,CPU指令系统，由0、1序列构成的指令码组成如：10000000 加 10010000 减,用助记符号描述的指令系统，可进行地址、位操作如 ADD A,B编写系统软件，直接对硬件操作，可读性，移植性差,面向机器的语言,可读性，移植性好，编写应用程序一般较难实现汇编语言的某些功能如：地址和位的操作,C语言兼有高级和低级语言的功能适合写系统软件和应用软件又称中级语言,C语言程序设计 第一章 程序设计基础知识,程序设计：用计算机语言对所要解决的问题中的数据以及处理问题的方法和步骤所做的完整而准确的描述过程。程序包括：数据结构：数据的类型和组织形式算法：操作步骤的描述,Nikiklaus Wirth提出：,教材认为：,程序,=算法+数据结构+程序设计方法+语言工具和环境,灵魂,加工对象,工具,C语言程序设计 第一章 程序设计基础知识,1.2 算法和算法的表示算法的概念,广义地说，为解决一个问题而采取的方法和有限的步骤，就称为“算法”。,方法1：1+2，+3，+4，一直加到100方法2：100+(1+99)+(2+98)+(49+51)+50=100+49100+50,对同一个问题，可有不同的解题方法和步骤,例：求,为了有效地进行解题，不仅需要保证算法正确，还要考虑算法的质量，选择合适的算法。希望方法简单，运算步骤少。,计算机算法可分为两大类别：数值运算算法：求数值解，例如求方程的根、求函数的定积分等。非数值运算：包括的面十分广泛，最常见的是用于事务管理领域，例如图书检索、人事管理、行车调度管理等。,C语言程序设计 第一章 程序设计基础知识,1.2 算法和算法的表示算法的概念,简单算法举例,例1:求12345,步骤1：先求12，得到结果2步骤2：将步骤1得到的乘积2再乘以3，得到结果6步骤3：将6再乘以4，得24步骤4：将24再乘以5，得120,太繁琐,如果要求121000，则要写999个步骤,C语言程序设计 第一章 程序设计基础知识,S1：使p=1 S2：使i=2 S3：使pi，乘积仍放在变量p中，可表示为：p=pi S4：使i的值加1，即i=i+1。S5：如果i不大于5，返回重新执行步骤S3以及其后的步骤S4和S5；否则，算法结束。最后得到p的值就是5!的值。,可以设两个变量：一个变量代表被乘数，一个变量代表乘数。不另设变量存放乘积结果，而直接将每一步骤的乘积放在被乘数变量中。设p为被乘数，i为乘数。用循环算法来求结果,算法可改写：,C语言程序设计 第一章 程序设计基础知识,S1：p=1S2：i=3S3：p=piS4：i=i+2S5：若i999，返回S3。否则，结束。,如果题目改为：求135999算法只需作很少的改动：,算法简练,C语言程序设计 第一章 程序设计基础知识,用这种方法表示的算法具有通用性、灵活性。S3到S5组成一个循环，在实现算法时 要反复多次执行S3，S4，S5等步骤，直到某一时刻，执行S5步骤时经过判断，乘数i已超过规定的数值而不返回S3步骤为止。此时算法结束，变量p的值就是所求结果。,C语言程序设计 第一章 程序设计基础知识,例2 有50个学生，要求将他们之中成绩在80分以上者打印出来。设n表示学号，n1代表第一个学生学号，ni代表第i个学生学号。用G代表学生成绩，gi代表第i个学生成绩，算法表示如下:,S1：i=1 S2：如果gi 80，则打印，否则不打印。S3：i=i+1 S4：如果i50，返回S2，继续执行。否则算法结束,例3 求,算法如下：,S1：sign=1 S2：sum=1 S3：deno=2 S4：sign=(-1)sign S5：term=sign(1/deno)S6：sum=sum+term S7：deno=deno+1 S8：若deno100返回S4，否则算法结束。,单词作变量名，以使算法更易于理解：sum表示累加和，deno是英文分母（denom inator）缩写，sign代表数值的符号，term代表某一项。,反复执行S4到S8步骤，直到分母大于100为止。一共执行了99次循环，向sum累加入了99个分数。sum最后的值就是多项式的值。,C语言程序设计 第一章 程序设计基础知识,有穷性：包含有限的操作步骤确定性：算法中的每一个步骤都应当是确定的 有效性：算法中的每一个步骤都应当能有效地执行，并得到确定的结果。有零个或多个输入：输入是指在执行算法时需要从外界取得必要的信息 有一个或多个输出：算法的目的是为了求解，“解”就是输出,一个算法应该具有以下特点：,C语言程序设计 第一章 程序设计基础知识,1.2 算法和算法的表示算法的基本特征,可以用不同的方法表示算法，常用的有：自然语言程序语言流程图N-S图PAD图伪代码,C语言程序设计 第一章 程序设计基础知识,1.2 算法和算法的表示算法的表示,用流程图表示算法,美国国家标准化协会ANSI(American National Standard Institute)规定了一些常用的流程图符号：,例1 将求5!的算法用流程图表示,如果需要将最后结果打印出来，可在菱形框的下面加一个输出框。,例2 将例2的算法用流程图表示。打印50名 学生中成绩在80分以上者的学号和成绩。,如果包括输入数据的部分，流程图为,例3 将例3的算法用流程图表示,小结：,流程图是表示算法的较好的工具。一个流程图包括以下几部分：(1)表示相应操作的框；(2)带箭头的流程线；(3)框内外必要的文字说明。,1、传统流程图的弊端 传统流程图用流程线指出各框的执行顺序，对流程线的使用没有严格限制。因此，使用者可以毫不受限制地使流程随意地转向，使流程图变得毫无规律，阅读者要花很大精力去追踪流程，使人难以理解算法的逻辑。如图：,C语言程序设计 第一章 程序设计基础知识,1.3 结构化程序设计方法,传统流程图的流程可以是：,这种如同乱麻一样的算法称为BS型算法，意为一碗面条(A Bowl of Spaghetti)，乱无头绪。,缺点：难以阅读、修改，使算法的可靠性和可维护性难以保证。解决办法：必须限制箭头的滥用，即不允许无规律地使流程随意转向，只能顺序地进行下去。,C语言程序设计 第一章 程序设计基础知识,传统流程图流向混乱、可读性差，所以应该采用结构化流程图。结构化程序设计 基本思想：任何程序都可以用三种基本结构表示，限制使用无条件转移语句（goto）结构化程序：由三种基本结构反复嵌套构成的程序 优点：结构清晰，易读，提高程序设计质量和效率,2、三种基本结构 计算机科学家Bohra和Jacopini提出了以下三种基本结构：顺序结构、选择结构、循环结构 用这三种基本结构作为表示一个良好算法的基本单元。,C语言程序设计 第一章 程序设计基础知识,三种基本结构的图示：,顺序结构,选择结构,C语言程序设计 第一章 程序设计基础知识,循环结构的图示：,当型(While型)循环结构,直到型(Until型)循环,C语言程序设计 第一章 程序设计基础知识,三种基本结构的共同特点：(1)只有一个入口；(2)只有一个出口；（请注意：一个菱形判断框有两个出口，而一个选择结构只有一个出口。不要将菱形框的出口和选择结构的出口混淆。）(3)结构内的每一部分都有机会被执行到；(4)结构内不存在“死循环”(无终止的循环)。,C语言程序设计 第一章 程序设计基础知识,图中没有一条从入口到出口的路径通过A框。,不正确的流程表示：,流程内的死循环,C语言程序设计 第一章 程序设计基础知识,小结：,由三种基本结构顺序组成的算法结构，可以解决任何复杂的问题。由基本结构所构成的算法属于“结构化”的算法，它不存在无规律的转向，只在本基本结构内才允许存在分支和向前或向后的跳转。,C语言程序设计 第一章 程序设计基础知识,C语言程序设计 第一章 程序设计基础知识,总结结构化程序设计方法结构化程序：用三种基本结构组成的程序基本设计思路：复杂问题分解成 几个最基本问题，再分别处理。采用的方法：自顶向下；逐步细化；模块化设计：复杂问题按功能分成多个子模块结构化编码：正确采用三种基本结构实现,用这种方法逐步分解，直到作者认为可以直接将各小段表达为文字语句为止。这种方法就叫 做“自顶向下，逐步细化”。,C语言程序设计 第一章 程序设计基础知识,自顶向下，逐步细化方法的优点：考虑周全，结构清晰，层次分明，作者容易写，读者容易看。如果发现某一部分中有一段内容不妥，需要修改，只需找出该部分修改有关段落即可，与其它部分无关。我们提倡用这种方法设计程序。这就是用工程的方法设计程序。,C语言程序设计 第一章 程序设计基础知识,模块设计的方法：模块化设计的思想实际上是一种“分而治之”的思想，把一个大任务分为若干个子任务，每一个子任务就相对简单了。在拿到一个程序模块以后，根据程序模块的功能将它划分为若干个子模块，如果这些子模块的规模还嫌大，还再可以划分为更小的模块。这个过程采用自顶向下方法来实现。子模块一般不超过50行划分子模块时应注意模块的独立性，即：使一个模块完成一项功能，耦合性愈少愈好。,C语言程序设计 第一章 程序设计基础知识,小结：,算法为解决一个问题而采取的方法和有限的步骤算法表示：流程图三种基本结构：顺序结构、选择结构、循环结构结构化程序设计方法：自顶向下；逐步细化；模块化设计：结构化编码：,C语言程序设计 第一章 程序设计基础知识,
