《计算机导论》教案 15页

《计算机导论》教案第四章算法、程序和编程学习目的和要求：1.了解算法与程序概念2.理解算法的复杂性与NP问题3.熟悉基本算法4.知道数据和数据结构5.熟悉高级语言6.掌握程序设计规划7.了解程序理论和软件工程学习重点：1.算法的复杂性与NP问题2.数据和数据结构3.基本算法4.程序理论和软件工程学习难点：1.数据和数据结构2.基本算法学时：10学习内容：课后反馈讨论围绕以下问题，组织学生分组讨论，然后让每组代表阐述他们的看法和思想。1.怎样养成良好的算法思想？讨论目的：了解算法的描述方式，并掌握其中的一种。可围绕以下内容展开讨论：算法描述常用的方法有自然语言，伪代码和程序流程图。通过该章的学习，能够用以上方法设计完整、合理的算法。为下学期C语言的学习奠定良好的基础。2.如何成为一个优秀的程序开发人员？讨论目的：了解程序员工作流程，逐步养成良好的编程习惯。可围绕以下内容展开讨论：开发软件要按照软件工程的步骤统一实施和管理，协同工作等。3.学习良好的软件开发习惯。讨论目的：了解软件开发的过程，熟悉软件开发过程中容易出现的问题：可围绕以下内容展开：软件开发过程：问题定义、可行性分析、总体描述、系统设计、编码、调试和测试、验收与运行、维护等阶段。在软件开发过程中要有完整的文档，数据，程序等资料。要按照软件工程的思想来开发软件以降低风险。4.软件工程的功能及应用。讨论目的：了解软件工程的功能，以及如何将软件工程的思想应用到软件开发中：可围绕以下内容展开讨论：\n软件工程的目标是：在给定成本、进度的前提下，开发出具有可修改性、有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性并且满足用户需求的软件产品。追求这些目标有助于提高软件产品的质量和开发效率，减少维护的困难。5.如何学好一门基础的编程语言。讨论目的：了解常用的变成语言，选择其中一种编程语言去深入学习，为以后理论学习和实践奠定基础。可围绕以下内容讨论：选一门你感兴趣的语言Java或者是C#之类，VC也可以，做一个实际的东西，比如做个聊天室，做个画图程序（可以保存），做个五子棋或者象棋的程序，从这些小的但是完整的程序开始做，做的过程中碰到问题自己查资料，或者到相应论坛提问，做好后总结，慢慢提高的自己的编程能力。§4.1算法与程序4.1.1算法算法定义1：算法是一组明确步骤的有序集合，它产生结果，并在有限的时间内终止。有以下特性：①有序集合②明确步骤③产生结果④在有限的时间内结束算法定义2：给定问题和设备，一个算法是用该设备可理解的语言表示的，解决这个问题的一种方法是精确刻画。特别地，算法具有以下特征属性：①算法应用于一个具体的输入集合或问题描述将在有穷步动作之后得到结果；②该序列有一个唯一的初始动作：③该序列中的每一个动作有一个唯一的后继动作④该序列终止时或者得到这个问题的解，或者因该问题不可解而获得不可解说明。算法定义3：一个算法，就是一个有穷规则的集合，其中之规则确定了一个解决某一特定型问题的运算序列。此外，算法的规则序列必须满足以下5个重要条件，即具有以下五个特性：①有穷性。算法必须总是在执行有穷步之后结束②确定性。算法的每一个步骤必须是确切地定义的；③输入。算法有零个或多个输入④输出。算法有一个或多个输出，即与输入有某个关系的量。⑤能行性。算法中有待执行的运算和操作必须是相当基本的，即是说，它们原则上是能够精确地进行的，而且用笔和纸做有穷次就可以完成。4.1.2子算法子算法：在结构化编程时应用模块化或分单元的办法来构成这个程序，这些被分成的小单元我们称之为子算法（子程序、子例程、过程、函数、方法和子模块等）。每个子算法又可以划分为更小的子算法，这个过程持续到子算法变为最本质的（可被立即理解的）描述为止。使用编程子算法的优点：⑤使程序更容易理解\n①可以在主算法中不同的地方调用4.1.3程序程序就是一种事先编制好了具有特殊功能的指令序列。其中，指令序列可以是机器指令，汇编语言，也可以是高级语言的语句指令。（1）伪代码：是在编写算法时，为了更好地表示算法本身，不在一些小的细节上纠缠，而采用类似于英语（或其他自然语言）表示算法的算法表示方法。例1用伪代码写出一个求两个数的平均值的算法。解：AverageOfTwoInput:Twonumbers①Addthetwonumbers②Dividetheresultby2③Returntheresultbystep2End（2）流程图程序流程图是人们对解决问题的方法、思路或算法的一种描述。流程图的优点：（a）采用简单规范的符号，画法简单；（b）结构清晰，逻辑性强；c）便于描述，容易理解。程序流程图有以下几部分组成：（1）起始框（2）终止框（3）执行框（4）判别框（5）箭头。例2计算并打印整个班级中每个学生三门课程考试成绩的平均分数。解：程序流程图如图4-1：开始开始求平均值获取三门成绩打印平均成绩全部学生打印？YN图4-1程序流程图§4.2计算的复杂性与NP问题所谓"计算复杂性"，通俗说来，就是用计算机求解问题的难易程度。其度量标准：一是计算所需的步数或指令条数(这叫时间复杂度)，二是计算所需的存储单元数量(这叫空间复杂度)。4.2.1算法复杂性描述\n算法在执行过程中总共所需要的初等运算的步数来表示算法用于求解任一问题的某一例子时所需的时间。1）算法复杂性的表示：（1）多项式时间算法：是指存在某个以输入长度n为变量的多项式函数中(n)，使其时间复杂性函数为O(p(n))的算法。因此复杂性为O(n)、O(106n3)、O(5n8)等算法均为多项式时间算法。（2）指数时间算法：是指任何其时间复杂性函数不可能如上用多项式函数去界定的算法，例如O（2n）、O(n!)、O(nn)、O(2n2)等都在算法上是不可接受的。2）时间复杂性的表示O（1）称为常数级；O（logn）称为对数级；O（n）称为线性级；O(nc)称为多项式级，（C为常数）；O（Cn）称为指数级，（C为常数）；O(n!)称为阶乘级；4.2.2P类问题和NP类问题在介绍P与NP之前,我想先介绍两个概念.（1）确定性算法：设A是求解问题B的一个算法,如果在展示问题B的一个实例时,在整个执行过程中每一步都只有一个选择,则称A是确定性算法.因此如果对于同样的输入,实例一遍又一遍地执行,它的输出从不改变.通常我们在写程序时,用到的都是一些确定性算法,比如说排序算法,最优化算法等。（2）不确定性算法：一个不确定性算法由下列两个阶段组成。①猜测阶段:在这个阶段产生一个任意字任串Y,它可能对应于输入实例的一个解,也可以不对应解.事实上,它甚至可能不是所求解的合适形式,它可能在不确定性算法的不同次运行中不同.它仅仅要求在多项式步数内产生这个串。②验证阶段:在这个阶段,一个确定性算全证两件事.首先,它检查产生的解串Y是否有合适的形式,如果不是,则算法停下并回答NO;另一方面,如果Y是合适形式,那么算法继续检查它是否是问题实例X的解,如果它确实是实例X的解,那么它停下并且回答YES,否则它停下并回答NO.我们也要求这个阶段在多项式步数内完成。可能很多人会认为随机算法是一种不确定性算法.其实随机算法也是一种确定性算法,因为它的随机性也是通过在输入中加入一个用于产生随机值的串实现的,同样的串得到的随机值相同.（3）\nP与NP的定义:P是一个判定问题类,这些问题可以用一个确定性算法在多项式时间内判定或解出;NP是一个判定问题类,这些问题可以用一个确定算法在多项式时间内检查或验证出它们的解。P事实上很直观,我们通常在编程中求解的问题大多都是P类问题.比如说排序,找最短路径等.NP这个类事实上也很有趣,它并不要求给出一个算法来求解问题本身,而只是要求给出一个确定性算法在多项式时间内验证它的解。一个算法如果存在图灵机可计算的多项式时间计算复杂性算法，就将该算法归入P类；如果存在非确定性图灵机可计算的多项式时间计算复杂性算法，就将其归入NP类。（4）NP完全问题：NP完全事实上表求NP中判定问题的一个子类.这类问题也是很有趣的,即如果它们中的一个被证明是多项式时间内确定性算法可解,那么所有属于这一类的其它问题也是多项式时间内确定性算法可解。（5）多项式时间归约:设A和B是两个判定问题.如果存在一个确定性算法C,它的行为如下:当给C展示问题A的一个实例时,算法A可以把这个实例变换成问题B的一个实例,使得A的实例跟B的实例有相同的YES/NO应答,并且这个变换在多项式时间内完成.那么我们说A多项式时间归约到B。事实上,我们可以将多项式时间归约看做是一个函数的映射,即F(A)=B.并且这个F是多项式时间内可计算的.也就是说问题A实现上可以通过它自身满足的条件,通过一些形式上的改变而变换到问题B.形象地讲,问题A事实上不比B难,而问题B也同样不比问题A难.（6）NP困难与NP完全：一个判定问题A称为是NP困难的,如果对于NP中的每个问题B,B多项式时间归约到A。一个判定问题A称为是NP完全的,如果对于NP中的每个问题B,B多项式时间归约到A,并且A在NP类中。（7）NP完全问题的证明:要证明一个判定问题是NP完全的,只要在NP完全类中找到一个问题A,将这个问题归约到待证明问题即可.要证明问题是NP完全是很困难的,因为很多问题之间的转化过程是很难想到的.第一个被证明的NP完全问题是可满足性问题,它是判定一个合取范式的布尔公式F是否存在真值指派的问题.在很多NP完全问题的证明中,我们都可以用这个问题来归约。4.2.3相似性原理和对偶原理（1）相似性原理所有合理的、功能足够强大的计算模型不仅可相互模拟计算，而且他们相互模拟时，同时使用本质上相同的并行时间，本质上相同的空间，本质上相同的顺序时间。（2）对偶原理在并行计算模型上，计算的时间和空间可以相互转换。§4.3基本算法简介4.3.1递归、迭代算法递归、迭代算法：递归算法是算法自我调用的过程。迭代的定义：算法中没有包含算法自身，只是利用上一步计算的结果得出最后答案的算法。递归的定义：算法中包含了算法自身的调用的算法。\n例3求n的阶乘解：（1）用递归算法实现如下：FactorialInput:Apositiveintegernumif(numisequalto0)thenreturn1elsereturnnumxFactorial(num–1)EndifEnd（2）用迭代算法实现如下：FactorialInput:ApositiveintegernumSetFactNto0SetitoIwhile(iislessthanorequaltonum)SetFactNtoFactNxIIncrementiEndwhileReturnFactNEnd4.3.2分治算法就是将一个难以直接解决的大问题，通过分析，分解为一些规模较小的相同问题，进而对各个小问题进行解决，最后达到整个问题的解决。例如，求N个元素集合S的最大元素和最小元素问题。可以将S分成大小相等的两个几个S1和S2，然后递归的求出S1和S2中的最大元素和最小元素，再经过比较得到最终结果。这就是典型的分治思想的应用。§4.4数据和数据结构4.4.1数据与数据类型数据就是算法所要处理的对象。通常分为数值数据和非数值数据。表4-1列出了常用数据类型之间的比较：表4-1简单数据类型类型在VB中的大小和名字在C/C++中的大小和名字在Java中的大小和名字Boo1ean1位—Boolean仅在一些编译器下使用1位—boo1eanCharacter没有字符类型1字节—Char2字节—CharShortinteger没有short类型2字节—short2字节—shortInteger2字节—Integer2字节—int4字节—int1ongintger4字节—Long4字节—long4字节—1ong\nF1oating-point4字节—Single4字节—float4字节—floatdouble-precision8字节—Double8字节—double8字节—double4.4.2数据结构数据结构是一个二元组Data-structure=(D,R),其中D为数据元素的集合，R是D上关系的集合。几种典型的数据结构如下：（1）线性表线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。线性表的逻辑结构简单，便于实现和操作。因此，线性表这种数据结构在实际应用中是广泛采用的一种数据结构。（2）栈栈(Stack)是仅限制在表的一端进行插入和删除运算的线性表，称插入、删除这一端为栈顶，另一端称为栈底。表中无元素时为空栈。栈的修改是按后进先出的原则进行的，我们又称栈为LIFO表(LastInFirstOut)。通常栈有顺序栈和链栈两种存储结构。（3）队列队列(Queue)是一种运算受限的线性表，插入在表的一端进行，而删除在表的另一端进行，允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear),队列的操作原则是先进先出的，又称作FIFO表(FirstInFirstOut)。队列也有顺序存储和链式存储两种存储结构。（4）串串（string）（或字符串）：是由零个或多个字符组成的有限序列，一般记为(n≥0)其中，s是串的名，用单引号括起来的字符序列是串的值，但单引号本身不属于串；（1≤i≤n）可以是字母、数字或其他字符。串的长度：串中字符的数目。空串（nullstring）：零个字符的串，其长度为零。记为“”。空格串（blankstring）：由一个或多个空格组成的串。其长度为串中空格字符的个数。子串：串中任意个连续的字符组成的子序列。主串：包含子串的串相应地称为主串。字符在串中的位置：即字符在序列中的序号。串相等：当且仅当这两个串的值相等。即，两个串的长度相等，并且各个对应位置的字符都相等。（5）数组数组是在程序设计中，为了处理方便，把具有相同类型的若干变量按有序的形式组织起来的一种形式。这些按序排列的同类数据元素的集合称为数组。在Ｃ语言中，\n数组属于构造数据类型。一个数组可以分解为多个数组元素，这些数组元素可以是基本数据类型或是构造类型。因此按数组元素的类型不同，数组又可分为数值数组、字符数组、指针数组、结构数组等各种类别。（6）树和二叉树①树的递归定义：树(Tree)是n(n≥0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：a有且仅有一个特定的称为根(Root)的结点；b其余的结点可分为m(m≥0)个互不相交的子集Tl，T2，…，Tm，其中每个子集本身又是一棵树，并称其为根的子树(Subree)。　　　　　　 注意：树的递归定义刻画了树的固有特性：一棵非空树是由若干棵子树构成的，而子树又可由若干棵更小的子树构成。②二叉树的递归定义二叉树(BinaryTree)是n(n≥0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。数和二叉树如图4-2：图4-2树和二叉树(7)图图G由两个集合V和E组成，记为：G=(V，E)，其中：V是顶点的有穷非空集合，E是V中顶点偶对(称为边)的有穷集。通常，也将图G的顶点集和边集分别记为V(G)和E(G)。E(G)可以是空集。若E(G)为空，则图G只有顶点而没有边。图分为有向图和无向图。图的示例如图4-3。图4-3图的示例①有向图   若图G中的每条边都是有方向的，则称G为有向图(Digraph)，\n在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。有向边也称为弧(Arc)，边的始点称为弧尾(Tail)，终点称为弧头(Head)。②无向图   若图G中的每条边都是没有方向的，则称G为无向图(Undigraph)。无向图中的边均是顶点的无序对，无序对通常用圆括号表示。§4.5高级语言简介高级语言是目前绝大多数编程者的选择⊥汇编语言相比，它不但将许多相关的机器指令合成为单条指令，并且去掉了与具体操作有关但与完成工作无关的细节，例如使用堆栈、寄存器等，这样就大大简化了程序中的指令。同时，由于省略了很多细节，编程者也就不需要有太多的专业知识。高级语言主要是相对于汇编语言而言，它并不是特指某一种具体的语言，而是包括了很多编程语言，如目前流行的vb、vc、foxpro、delphi等，这些语言的语法、命令格式都各不相同。高级语言所编制的程序不能直接被计算机识别，必须经过转换才能被执行，按转换方式可将它们分为两类解释类执行方式类似于我们日常生活中的同声翻译”，应用程序源代码一边由相应语言的解释器翻译”成目标代码(机器语言)，一边执行，因此效率比较低，而且不能生成可独立执行的可执行文件，应用程序不能脱离其解释器，但这种方式比较灵活，可以动态地调整、修改应用程序。编译类编译是指在应用源程序执行之前，就将程序源代码翻译”成目标代码(机器语言)，因此其目标程序可以脱离其语言环境独立执行，使用比较方便、效率较高。但应用程序一旦需要修改，必须先修改源代码，再重新编译生成新的目标文件(＊.obj)才能执行，只有目标文件而没有源代码，修改很不方便。现在大多数的编程语言都是编译型的，例如visualc＋＋、visualfoxpro、delphi等。4.5.1BasicBASIC是属于高阶程式语言的一种，英文名称的全名是"Beginner'sAll-PurposeSymbolicInstructionCode"，取其首字字母简称"BASIC"，就名称的含意来看，是"适用于初学者的多功能符号指令码"，是一种在计算机发展史上应用最为广泛的程式语言。有如下特点：（1）构成简单。BASIC语言的最基本语句只有17种，而且它们都是常见的英文单词或其变形，如READ、END等，很容易学习和掌握。　　（2）是一种“人机会话”式的语言。通过键盘操作，用BASIC语言编写完的程序，可以在计算机上边编写、边修改、边运行。而且还可以在运行中向人们提示信息的指出错误，要求人去改正，即实现了人和机器的对话。　　（3）功能较全、适用面广。BASIC语言除了能进行科学计算和数据处理外，还能进行字符处理、图形处理、音乐演奏等。因此BASIC语言不仅适用于科学计算，也适用于事务管理、计算机辅助教学和游戏编程等方面。　　（4）执行方式灵活。BASIC语言提供两种执行方式，分别是程序执行方式和命令执行方式。程序执行方式把BASIC语言编写成一个完整的程序送入计算机执行；命令执行方式不编写程序，直接从键盘输入某些命令（称键盘命令），计算机能立即执行这些命令。　　BASIC语言采用的是解释器，就是逐句翻译成机器语言程序，译出一句就立即执行，即边翻译边执行．与编译器\n比起来，解释器费时比编译器更多，但可少占计算机的内存．4.5.2FORTRANFORTRAN语言是世界上第一个被正式推广使用的高级语言。它是1954年被提出来的，1956年开始正式使用，至今已有五十多年的历史，但仍历久不衰，它始终是数值计算领域所使用的主要语言。　　FORTRAN语言是FormulaTranslation的缩写，意为“公式翻译”。它是为科学、工程问题或企事业管理中的那些能够用数学公式表达的问题而设计的，其数值计算的功能较强。4.5.3PascalPascal是种高阶的程序设计语言，由瑞士苏黎世理工学院的尼古拉斯·沃斯教授设计，ISO对Pascal进行修改以后，形成了标准Pascal语言。Pascal语言还是一种自编译的语言，这就使它的可靠性大大提高了。Pascal是最早出现的结构化编程语言，具有丰富的数据类型和简洁灵活的操作语句，适于描述数值和非数值的问题。4.5.4CC语言是CombinedLanguage（组合语言）的中英混合简称。是一种计算机程序设计语言。它既具有高级语言的特点，又具有汇编语言的特点。它可以作为工作系统设计语言，编写系统应用程序，也可以作为应用程序设计语言，编写不依赖计算机硬件的应用程序。因此，它的应用范围广泛，不仅仅是在软件开发上，而且各类科研都需要用到C语言，具体应用比如单片机以及嵌入式系统开发。4.5.5C++C++这个词在中国大陆的程序员圈子中通常被读做“C加加”，而西方的程序员通常读做“Cplusplus”，“CPP”。它是一种使用非常广泛的计算机编程语言。C++是一种静态数据类型检查的，支持多重编程范式的通用程序设计语言。它支持过程化程序设计、数据抽象、面向对象程序设计、制作图标等等泛型程序设计等多种程序设计风格。4.5.6JavaJava语言其实最早是诞生于1991年，起初被称为OAK语言，是SUN公司为一些消费性电子产品而设计的一个通用环境。他们最初的目的只是为了开发一种独立于平台的软件技术，而且在网络出现之前，OAK可以说是默默无闻，甚至差点夭折。但是，网络的出现改变了OAK的命运。Java的开发环境有不同的版本，如sun公司的JavaDevelopmentKit，简称JDK。后来微软公司推出了支持Java规范的MicrosoftVisualJ++Java开发环境，简称VJ++。它有以下特点：①平台无关性　　平台无关性是指Java能运行于不同的平台。Java引进虚拟机原理，并运行于虚拟机，实现不同平台的Java接口之间。使用Java编写的程序能在世界范围内共享。Java的数据类型与机器无关，Java虚拟机（JavaVirtualMachine）是建立在硬件和操作系统之上，实现Java二进制代码的解释执行功能，提供于不同平台的接口的。\n　　②安全性　　Java的编程类似C++，学习过C++的读者将很快掌握Java的精髓。Java舍弃了C++的指针对存储器地址的直接操作，程序运行时，内存由操作系统分配，这样可以避免病毒通过指针侵入系统。Java对程序提供了安全管理器，防止程序的非法访问。　　③面向对象　　Java吸取了C++面向对象的概念，将数据封装于类中，利用类的优点，实现了程序的简洁性和便于维护性。类的封装性、继承性等有关对象的特性，使程序代码只需一次编译，然后通过上述特性反复利用。程序员只需把主要精力用在类和接口的设计和应用上。Java提供了众多的一般对象的类，通过继承即可使用父类的方法。在Java中，类的继承关系是单一的非多重的，一个子类只有一个父类，子类的父类又有一个父类。Java提供的Object类及其子类的继承关系如同一棵倒立的树形，根类为Object类，Object类功能强大，经常会使用到它及其它派生的子类。　　④分布式　　Java建立在扩展TCP/IP网络平台上。库函数提供了用HTTP和FTP协议传送和接受信息的方法。这使得程序员使用网络上的文件和使用本机文件一样容易。　　⑤健壮性Java致力于检查程序在编译和运行时的错误。类型检查帮助检查出许多开发早期出现的错误。Java自己操纵内存减少了内存出错的可能性。Java还实现了真数组，避免了覆盖数据的可能，这些功能特征大大提高了开发Java应用程序的周期。并且Java还提供了Null指针检测、数组边界检测、异常出口、Bytecode校验等功能。4.5.7VBVisualBasic,简称VB，是Microsoft公司推出的一种Windows应用程序开发工具。是当今世界上使用最广泛的编程语言之一，它也被公认为是编程效率最高的一种编程方法。无论是开发功能强大、性能可靠的商务软件，还是编写能处理实际问题的实用小程序，VB都是最快速、最简便的方法。VB最早是微软从早期的BASIC语法继承而来，并加入了可视化的程序界面。4.5.8DelphiDelphi，是Windows平台下著名的快速应用程序开发工具(RapidApplicationDevelopment，简称RAD)。它的前身，即是DOS时代盛行一时的“BorlandTurboPascal”，最早的版本由美国Borland（宝兰）公司于1995年开发。主创者为AndersHejlsberg。经过数年的发展，此产品也转移至Embarcadero公司旗下。Delphi是一个集成开发环境（IDE），使用的核心是由传统Pascal语言发展而来的ObjectPascal，以图形用户界面为开发环境，透过IDE、VCL工具与编译器，配合连结数据库的功能，构成一个以面向对象程序设计为中心的应用程序开发工具。§4.6程序规划与设计\n4.6.1程序规划步骤1:分析问题并制定概要设计方案。编程人员必须对问题有完全、准确的了解，用准确的语言对问题进行描述，主要考虑以下几个方面；问题的输入是什么？已知的是什么？还要给什么，使用什么格式。(1)期望的输出是什么？需要什么类型的报告、图表或信息。(2)从给定的输入到期望的输出，必要的处理步骤是什么？步骤2:制定详细设计：（算法设计）必须制定一组精确的步骤，即编写提纲。这些步骤应该是明确、详细和有限的，并能在合理的时间内完成；同时选定实现各步骤的语言。步骤3:用编程语言编写程序代码及其文档。在步骤2中越详细清楚用程序代码就越容易。在用程序代码“翻译”的过程一定要准确、完整。特别是对文档的编写，对各条语句功能的注释，往往会被忽视，现代编程是一种团体的合作行为，让别人能容易地看懂你的程序，对整个系统的编写是绝对必要的。同时对程序的修改维护都有很大的帮助。步骤4:测试程序：这是一个在前几个步骤进行过程中一个不断重复的过程。对于编写出来的每一部分代码，都应该进行测试，以确保程序运行的正确性。步骤5:验证程序：一旦程序编写完并进行一定的测试后，就应该通过大范围的测试来验证。验证时必须根据用户的要求，不断进行修改调整到用户满意为止。4.6.2程序设计举例例2用C语言求N的阶乘。解：#includemain（）{intn,i,x；printf("inputanum:");scanf("%d",&n);if(n<0)printf("dataerror!\n");if(n=0)printf("0!",1);elsefor(i=1;i<=n;i++)x=x*i;printf("%d!,%d",n,x);}  4.6.3程序设计与调试1）程序设计的任务是为新系统编写程序，即把详细设计的结果转换成某种计算机编程语言写成的程序。该阶段相当于机械工程中图纸设计完成的“制造”阶段，程序设计的好坏直接关系到能否有效地利用电子计算机来圆满地达到预期目的。高质量的程序，必须符合以下基本要求：（1）程序的功能必须按照规定的要求，正确地满足预期的需要；（2）程序的内容清晰、明了、便于阅读和理解；（3）程序的结构严谨、简捷、算法和语句选用合理，执行速度快，节省机时；（4）程序和数据的存储、调用安排得当，节省存储空间；\n（5）程序的适应性强。程序交付使用后，若应用问题或外界环境有了变化时，调整和修改程序比较简便易行。以上各要求并不是绝对的，允许根据系统本身以及用户环境的不同情况而有所侧重考虑。此外，程序设计结束后，还应写出操作说明书，说明执行该程序时的具体操作步骤。2）程序调试的意义和目的在管理信息系统的开发过程中，面对着错综复杂的各种问题，人的主观认识不可能完全符合客观现实，开发人员之间的思想交流也不可能十分完善。所以，在管理信息系统开发周期的各个阶段都不可避免地会出现差错。开发人员应力求在每个阶段结束之前进行认真、严格的技术审查，尽可能早的发现并纠正错误，否则等到系统投入运行后再回头来改正错误将在人力、物力上造成很大的浪费，有时甚至导致整个系统的瘫痪。然而，经验表明，单凭审查并不能发现全部差错，加之在程序设计阶段也不可避免还会产生新的错误，所以，对系统进行调试是不可缺少的，是保证系统质量的关键步骤。统计资料表明，对于一些较大规模的系统来说，系统调试的工作量往往占程序系统编制开发总工作量的40%以上。调试的目的在于发现其中的错误并及时纠正，所以在调试时应想方设法使程序的各个部分都投入运行，力图找出所有错误。错误多少与程序质量有关。即使这样，调试通过也不能证明系统绝对无误，只不过说明各模块、各子系统的功能和运行情况正常，相互之间连接无误，系统交付用户使用以后，在系统的维护阶段仍有可能发现少量错误并进行纠正，这也是正常的。程序调试过程如图4-4：设计错误修复错误定位程序错误修复程序重测图4-4程序调试过程4.6.4养成良好的编程风格随着计算机技术的发展，软件的规模增大了，软件的复杂性也增强了。为了提高程序的可阅读性，要建立良好的编程风格。（1）源程序文档化标识符应按意取名，程序应加注释。注释是与日后读者之间通信的重要工具，用自然语言或伪码描述。它说明了程序的功能，特别在维护阶段，对理解程序提供了明确指导。注释分序言性注释和功能性注释。序言性注释应置于每个模块的起始部分，主要内容有：①说明每个模块的用途、功能。②说明模块的接口：调用形式、参数描述及从属模块的清单。③数据描述：重要数据的名称、用途、限制、约束及其他。④开发历史：设计者、审阅者姓名及日期，修改说明及日期。功能性注释嵌入在源程序内部，说明程序段或语句的功能以及数据的状态。注意以下几点：①注释用来说明程序段，而不是每一行程序都要加注释。②使用空行或缩格或括号，以便很容易区分注释和程序。③修改程序也应修改注释。（2）数据说明\n为了使数据定义更易于理解和维护，有以下指导原则：数据说明顺序应规范，使数据的属性更易于查找，从而有利于测试、纠错与维护。例如按以下顺序：常量寿命、类型说明、全程量说明、局部量说明。一个语句说明多个变量时，各变量名按字典序排列。对于复杂的，要加注释，说明在程序实现时的特点。（3）语句结构语句结构的原则是：简单直接，不能为了追求效率而使代码复杂化。为了便于阅读和理解，不要一行多个语句。不同层次的语句采用缩进形式，使程序的逻辑结构和功能特征更加清晰。要避免复杂的判定条件，避免多重的循环嵌套。表达式中使用括号以提高运算次序的清晰度等等。（4）输入和输出在编写输入和输出程序时考虑以下原则：输入操作步骤和输入格式尽量简单。应检查输入数据的合法性、有效性，报告必要的输入状态及错误。输入一批数据时，使用数据或文件结束标志，而不要用计数来控制。交互式输入时，提供可用的选择和边界值。当程序设计语言有严格的格式要求时，应保持输入格式的一致性。输出数据表格化、图形化。输入、输出风格还受其他因素的影响，如输入、输出设备，用户经验及通信环境等。（5）效率效率指处理机时间和空间的使用，对效率的追求明确以下几点：效率是一个性能要求，目标在需求分析给出。追求效率建立在不损害程序可读性或可靠性基础上，要先使程序正确，再提高程序效率，先使程序清晰，再提高程序效率。提高程序效率的根本途径在于选择良好的设计方法、良好的数据结构算法，而不是靠编程时对程序语句做调整。§4.7程序理论和软件工程4.7.1程序理论程序设计理论：通过对程序设计的各种问题进行了系统研究，进行了规范总结，如在程序设计中的自顶向下逐步求精的程序设计方法，自底向上的程序设计方法、程序推导的设计方法、程序变换的设计方法、函数式程序设计技术、逻辑程序设计技术、面向对象的程序设计、程序验证技术、约束程序设计技术和并发程序设计技术等，一系列规范的，好的程序开发方法、形成了丰富的程序设计理论，极大地推进了程序设计技术的发展。4.7.2软件工程软件工程：在大型的软件开发中，引入工程管理的一整套的管理方法，对软件开发过程进行规划、设计、监控和检测，以确保开发的过程、开发时间和软件质量都在人的控制管理之下，从而使软件开发的顺利进行。所以，对软件开发过程和软件质量的管理、监控的方法措施就构成了软件工程学。本章任务1、查阅资料：请你通过互联网或者书籍文献查找“计算机语言”相关内容。2、思考题：P1171-33、讨论:围绕以下问题，组织学生分组讨论，然后让每组代表阐述他们的看法和思想。\n（1）怎样养成良好的算法思想？（2）如何成为一个优秀的程序开发人员？（3）学习良好的软件开发习惯。（4）软件工程的功能及应用。（5）如何学好一门基本的编程语言。4、知识扩展（1）机器语言、汇编语言、高级语言有什么区别？（2）编译性语言与解释性语言的区别是什么？（3）什么是程序和程序设计？（4）论述一下软件的生命周期。