第四章算法程序和编程.docx

1、第四章算法程序和编程计算机导论教案第四章 算法、 程序和编程学习目的和要求：1. 了解算法与程序概念2. 理解算法的复杂性与NP问题3. 熟悉基本算法4. 知道数据和数据结构5. 熟悉高级语言6. 掌握程序设计规划7. 了解程序理论和软件工程学习重点：1. 算法的复杂性与NP问题2. 数据和数据结构3. 基本算法4. 程序理论和软件工程学习难点：1. 数据和数据结构2. 基本算法学时：10学习内容：课后反馈讨论围绕以下问题，组织学生分组讨论，然后让每组代表阐述他们的看法和思想。1.怎样养成良好的算法思想？讨论目的：了解算法的描述方式，并掌握其中的一种。可围绕以下内容展开讨论：算法描述常用的方法

2、有自然语言，伪代码和程序流程图。通过该章的学习，能够用以上方法设计完整、合理的算法。为下学期C语言的学习奠定良好的基础。 2.如何成为一个优秀的程序开发人员？讨论目的：了解程序员工作流程，逐步养成良好的编程习惯。可围绕以下内容展开讨论： 开发软件要按照软件工程的步骤统一实施和管理，协同工作等。3.学习良好的软件开发习惯。讨论目的：了解软件开发的过程，熟悉软件开发过程中容易出现的问题：可围绕以下内容展开：软件开发过程：问题定义、可行性分析、总体描述、系统设计、编码、调试和测试、验收与运行、维护等阶段。在软件开发过程中要有完整的文档，数据，程序等资料。要按照软件工程的思想来开发软件以降低风险。4.

3、软件工程的功能及应用。讨论目的：了解软件工程的功能，以及如何将软件工程的思想应用到软件开发中：可围绕以下内容展开讨论：软件工程的目标是：在给定成本、进度的前提下，开发出具有可修改性、有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性并且满足用户需求的软件产品。追求这些目标有助于提高软件产品的质量和开发效率，减少维护的困难。5.如何学好一门基础的编程语言。讨论目的：了解常用的变成语言，选择其中一种编程语言去深入学习，为以后理论学习和实践奠定基础。可围绕以下内容讨论：选一门你感兴趣的语言Java或者是C#之类，VC也可以，做一个实际的东西，比如做个聊天室，做个画

4、图程序（可以保存），做个五子棋或者象棋的程序，从这些小的但是完整的程序开始做，做的过程中碰到问题自己查资料，或者到相应论坛提问，做好后总结，慢慢提高的自己的编程能力。4.1 算法与程序4.1.1算法算法定义1：算法是一组明确步骤的有序集合，它产生结果，并在有限的时间内终止。有以下特性：1 有序集合2 明确步骤3 产生结果4 在有限的时间内结束算法定义2：给定问题和设备，一个算法是用该设备可理解的语言表示的，解决这个问题的一种方法是精确刻画。特别地，算法具有以下特征属性： 算法应用于一个具体的输入集合或问题描述将在有穷步动作之后得到结果； 该序列有一个唯一的初始动作： 该序列中的每一个动作有一个

5、唯一的后继动作该序列终止时或者得到这个问题的解，或者因该问题不可解而获得不可解说明。算法定义3：一个算法，就是一个有穷规则的集合，其中之规则确定了一个解决某一特定型问题的运算序列。此外，算法的规则序列必须满足以下5个重要条件，即具有以下五个特性：有穷性。算法必须总是在执行有穷步之后结束确定性。算法的每一个步骤必须是确切地定义的；输入。算法有零个或多个输入输出。算法有一个或多个输出，即与输入有某个关系的量。能行性。算法中有待执行的运算和操作必须是相当基本的，即是说，它们原则上是能够精确地进行的，而且用笔和纸做有穷次就可以完成。4.1.2子算法子算法：在结构化编程时应用模块化或分单元的办法来构成这

6、个程序，这些被分成的小单元我们称之为子算法（子程序、子例程、过程、函数、方法和子模块等）。每个子算法又可以划分为更小的子算法，这个过程持续到子算法变为最本质的（可被立即理解的）描述为止。使用编程子算法的优点：5 使程序更容易理解6 可以在主算法中不同的地方调用4.1.3程序程序就是一种事先编制好了具有特殊功能的指令序列。其中，指令序列可以是机器指令，汇编语言，也可以是高级语言的语句指令。（1）伪代码：是在编写算法时，为了更好地表示算法本身，不在一些小的细节上纠缠，而采用类似于英语（或其他自然语言）表示算法的算法表示方法。例1 用伪代码写出一个求两个数的平均值的算法。解：AverageOfTwo

7、 Input: Two numbersAdd the two numbersDivide the result by 2Return the result by step 2 End（2）流程图程序流程图是人们对解决问题的方法、思路或算法的一种描述。流程图的优点：（a）采用简单规范的符号，画法简单；（b）结构清晰，逻辑性强；c）便于描述，容易理解。 程序流程图有以下几部分组成：（1）起始框 （2）终止框（3）执行框 （4）判别框（5）箭头。例2 计算并打印整个班级中每个学生三门课程考试成绩的平均分数。解：程序流程图如图4-1：图4-1 程序流程图4.2 计算的复杂性与NP问题所谓计算复杂性，通

8、俗说来，就是用计算机求解问题的难易程度。其度量标准：一是计算所需的步数或指令条数(这叫时间复杂度)，二是计算所需的存储单元数量(这叫空间复杂度)。4.2.1算法复杂性描述算法在执行过程中总共所需要的初等运算的步数来表示算法用于求解任一问题的某一例子时所需的时间。1）算法复杂性的表示：（1）多项式时间算法：是指存在某个以输入长度n为变量的多项式函数中(n)，使其时间复杂性函数为O(p(n)的算法。因此复杂性为O(n)、O(106n3)、O(5n8)等算法均为多项式时间算法。（2）指数时间算法：是指任何其时间复杂性函数不可能如上用多项式函数去界定的算法，例如O（2n）、O(n!)、O(nn)、O(

9、2n2)等都在算法上是不可接受的。2）时间复杂性的表示O（1）称为常数级；O（logn）称为对数级；O（n）称为线性级；O (nc)称为多项式级，（C为常数）；O（Cn）称为指数级，（C为常数）；O (n!)称为阶乘级；4.2.2 P类问题和NP类问题 在介绍P与NP之前,我想先介绍两个概念.（1）确定性算法：设A是求解问题B的一个算法,如果在展示问题B的一个实例时,在整个执行过程中每一步都只有一个选择,则称A是确定性算法.因此如果对于同样的输入,实例一遍又一遍地执行,它的输出从不改变.通常我们在写程序时,用到的都是一些确定性算法,比如说排序算法,最优化算法等。（2）不确定性算法：一个不确定性

10、算法由下列两个阶段组成。猜测阶段:在这个阶段产生一个任意字任串Y,它可能对应于输入实例的一个解,也可以不对应解.事实上,它甚至可能不是所求解的合适形式,它可能在不确定性算法的不同次运行中不同.它仅仅要求在多项式步数内产生这个串。验证阶段:在这个阶段,一个确定性算全证两件事.首先,它检查产生的解串Y是否有合适的形式,如果不是,则算法停下并回答NO;另一方面,如果Y是合适形式,那么算法继续检查它是否是问题实例X的解,如果它确实是实例X的解,那么它停下并且回答YES,否则它停下并回答NO.我们也要求这个阶段在多项式步数内完成。可能很多人会认为随机算法是一种不确定性算法.其实随机算法也是一种确定性算法

11、,因为它的随机性也是通过在输入中加入一个用于产生随机值的串实现的,同样的串得到的随机值相同.（3）P与NP的定义:P是一个判定问题类,这些问题可以用一个确定性算法在多项式时间内判定或解出;NP是一个判定问题类,这些问题可以用一个确定算法在多项式时间内检查或验证出它们的解。P事实上很直观,我们通常在编程中求解的问题大多都是P类问题.比如说排序,找最短路径等.NP这个类事实上也很有趣,它并不要求给出一个算法来求解问题本身,而只是要求给出一个确定性算法在多项式时间内验证它的解。一个算法如果存在图灵机可计算的多项式时间计算复杂性算法，就将该算法归入P类；如果存在非确定性图灵机可计算的多项式时间计算复杂

12、性算法，就将其归入NP类。 （4）NP完全问题：NP完全事实上表求NP中判定问题的一个子类.这类问题也是很有趣的,即如果它们中的一个被证明是多项式时间内确定性算法可解,那么所有属于这一类的其它问题也是多项式时间内确定性算法可解。（5）多项式时间归约:设A和B是两个判定问题.如果存在一个确定性算法C,它的行为如下:当给C展示问题A的一个实例时,算法A可以把这个实例变换成问题B的一个实例,使得A的实例跟B的实例有相同的YES/NO应答,并且这个变换在多项式时间内完成.那么我们说A多项式时间归约到B。事实上,我们可以将多项式时间归约看做是一个函数的映射,即F(A)=B.并且这个F是多项式时间内可计算

13、的.也就是说问题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完全问题是可满足性问题,它是判定

14、一个合取范式的布尔公式F是否存在真值指派的问题.在很多NP完全问题的证明中,我们都可以用这个问题来归约。4.2.3相似性原理和对偶原理（1）相似性原理所有合理的、功能足够强大的计算模型不仅可相互模拟计算，而且他们相互模拟时，同时使用本质上相同的并行时间，本质上相同的空间，本质上相同的顺序时间。（2）对偶原理在并行计算模型上，计算的时间和空间可以相互转换。4.3 基本算法简介4.3.1递归、迭代算法递归、迭代算法：递归算法是算法自我调用的过程。迭代的定义：算法中没有包含算法自身，只是利用上一步计算的结果得出最后答案的算法。递归的定义：算法中包含了算法自身的调用的算法。例3 求n的阶乘解：（1）用

15、递归算法实现如下： Factorial Input: A positive integer numif (num is equal to 0)then return 1else return num x Factorial (num 1) End if End（2）用迭代算法实现如下： Factorial Input: A positive integer numSet FactN to 0Set i to Iwhile (i is less than or equal to num) Set FactN to FactN x I Increment i End whileReturn Fac

16、tN End4.3.2分治算法就是将一个难以直接解决的大问题，通过分析，分解为一些规模较小的相同问题，进而对各个小问题进行解决，最后达到整个问题的解决。例如，求N个元素集合S的最大元素和最小元素问题。可以将S分成大小相等的两个几个S1和S2，然后递归的求出S1和S2中的最大元素和最小元素，再经过比较得到最终结果。这就是典型的分治思想的应用。4.4 数据和数据结构4.4.1数据与数据类型数据就是算法所要处理的对象。通常分为数值数据和非数值数据。表4-1列出了常用数据类型之间的比较：表4-1 简单数据类型类型在VB中的大小和名字在C/C+ +中的大小和名字在Java中的大小和名字Boo1ean1位

17、Boolean仅在一些编译器下使用1位boo1eanCharacter没有字符类型1字节 Char2字节 CharShort integer没有short类型2字节 short2字节 shortInteger2字节 Integer2字节 int4字节 int1ongintger4字节 Long4字节 long4字节 1ongF1oating-point4字节 Single4字节 float4字节 floatdouble-precision8字节 Double8字节 double8字节 double4.4.2数据结构数据结构是一个二元组Data-structure=(D,R),其中D为数据元素的

18、集合，R是D上关系的集合。几种典型的数据结构如下：（1）线性表线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。线性表的逻辑结构简单，便于实现和操作。因此，线性表这种数据结构在实际应用中是广泛采用的一种数据结构。（2）栈栈(Stack)是仅限制在表的一端进行插入和删除运算的线性表，称插入、删除这一端为栈顶，另一端称为栈底。表中无元素时为空栈。栈的修改是按后进先出的原则进行的，我们又称栈为LIFO表(Last In First Out)。通常栈有顺序栈和链栈两种存储结构。（3）队列队列(Qu

19、eue)是一种运算受限的线性表，插入在表的一端进行，而删除在表的另一端进行，允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear) ,队列的操作原则是先进先出的，又称作FIFO表(First In First Out) 。队列也有顺序存储和链式存储两种存储结构。（4）串串（string）（或字符串）：是由零个或多个字符组成的有限序列，一般记为 (n0)其中，s是串的名，用单引号括起来的字符序列是串的值，但单引号本身不属于串；（1in）可以是字母、数字或其他字符。串的长度：串中字符的数目。 空串（null string）：零个字符的串，其长度为零。记为“”。空格串（blank

20、string）：由一个或多个空格组成的串。其长度为串中空格字符的个数。 子串：串中任意个连续的字符组成的子序列。 主串：包含子串的串相应地称为主串。 字符在串中的位置：即字符在序列中的序号。串相等：当且仅当这两个串的值相等。即，两个串的长度相等，并且各个对应位置的字符都相等。（5）数组数组是在程序设计中，为了处理方便， 把具有相同类型的若干变量按有序的形式组织起来的一种形式。这些按序排列的同类数据元素的集合称为数组。在语言中， 数组属于构造数据类型。一个数组可以分解为多个数组元素，这些数组元素可以是基本数据类型或是构造类型。因此按数组元素的类型不同，数组又可分为数值数组、字符数组、指针数组、结

21、构数组等各种类别。（6）树和二叉树树的递归定义：树(Tree)是n(n0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：a有且仅有一个特定的称为根(Root)的结点；b其余的结点可分为m(m0)个互不相交的子集Tl，T2，Tm，其中 每个子集本身又是一棵树，并称其为根的子树(Subree)。注意：树的递归定义刻画了树的固有特性：一棵非空树是由若干棵子树构成的，而子树又可由若干棵更小的子树构成。二叉树的递归定义二叉树(BinaryTree)是n(n0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。数和二叉树如图

22、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)，在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。有向边也称为弧(Arc)，边的始点称为弧尾(Tail)，终点称为弧头(Head)。无向图 若图G中的每条边都是没有方向的，则称G为

23、无向图(Undigraph)。无向图中的边均是顶点的无序对，无序对通常用圆括号表示。4.5 高级语言简介高级语言是目前绝大多数编程者的选择汇编语言相比，它不但将许多相关的机器指令合成为单条指令，并且去掉了与具体操作有关但与完成工作无关的细节，例如使用堆栈、寄存器等，这样就大大简化了程序中的指令。同时，由于省略了很多细节，编程者也就不需要有太多的专业知识。 高级语言主要是相对于汇编语言而言，它并不是特指某一种具体的语言，而是包括了很多编程语言，如目前流行的vb、vc、foxpro、delphi等，这些语言的语法、命令格式都各不相同。 高级语言所编制的程序不能直接被计算机识别，必须经过转换才能被执

24、行，按转换方式可将它们分为两类 解释类执行方式类似于我们日常生活中的同声翻译”，应用程序源代码一边由相应语言的解释器翻译”成目标代码(机器语言)，一边执行，因此效率比较低，而且不能生成可独立执行的可执行文件，应用程序不能脱离其解释器，但这种方式比较灵活，可以动态地调整、修改应用程序。 编译类编译是指在应用源程序执行之前，就将程序源代码翻译”成目标代码(机器语言)，因此其目标程序可以脱离其语言环境独立执行，使用比较方便、效率较高。但应用程序一旦需要修改，必须先修改源代码，再重新编译生成新的目标文件( .obj)才能执行，只有目标文件而没有源代码，修改很不方便。现在大多数的编程语言都是编译型的，例

25、如visual c、visual foxpro、delphi等。4.5.1BasicBASIC 是属于高阶程式语言的一种，英文名称的全名是 Beginners All-Purpose Symbolic Instruction Code，取其首字字母简称 BASIC，就名称的含意来看，是适用于初学者的多功能符号指令码，是一种在计算机发展史上应用最为广泛的程式语言。有如下特点：（1）构成简单。 BASIC语言的最基本语句只有17种，而且它们都是常见的英文单词或其变形，如READ、END等，很容易学习和掌握。 （2）是一种“人机会话”式的语言。通过键盘操作，用BASIC语言编写完的程序，可以在计算机

26、上边编写、边修改、边运行。而且还可以在运行中向人们提示信息的指出错误，要求人去改正，即实现了人和机器的对话。 （3）功能较全、适用面广。BASIC语言除了能进行科学计算和数据处理外，还能进行字符处理、图形处理、音乐演奏等。因此BASIC语言不仅适用于科学计算，也适用于事务管理、计算机辅助教学和游戏编程等方面。 （4）执行方式灵活。BASIC语言提供两种执行方式，分别是程序执行方式和命令执行方式。程序执行方式把BASIC语言编写成一个完整的程序送入计算机执行；命令执行方式不编写程序，直接从键盘输入某些命令（称键盘命令），计算机能立即执行这些命令。 BASIC 语言采用的是解释器，就是逐句翻译成机

27、器语言程序，译出一句就立即执行，即边翻译边执行与编译器比起来，解释器费时比编译器更多，但可少占计算机的内存4.5.2FORTRAN FORTRAN语言是世界上第一个被正式推广使用的高级语言。它是1954年被提出来的，1956年开始正式使用，至今已有五十多年的历史，但仍历久不衰，它始终是数值计算领域所使用的主要语言。 FORTRAN语言是Formula Translation的缩写，意为“公式翻译”。它是为科学、工程问题或企事业管理中的那些能够用数学公式表达的问题而设计的，其数值计算的功能较强。 4.5.3Pascal Pascal是种高阶的程序设计语言，由瑞士苏黎世理工学院的尼古拉斯沃斯教授设

28、计，ISO对Pascal进行修改以后，形成了标准Pascal语言。 Pascal语言还是一种自编译的语言，这就使它的可靠性大大提高了。Pascal是最早出现的结构化编程语言，具有丰富的数据类型和简洁灵活的操作语句，适于描述数值和非数值的问题。4.5.4 C C语言是Combined Language（组合语言）的中英混合简称。是一种计算机程序设计语言。它既具有高级语言的特点，又具有汇编语言的特点。它可以作为工作系统设计语言，编写系统应用程序，也可以作为应用程序设计语言，编写不依赖计算机硬件的应用程序。因此，它的应用范围广泛，不仅仅是在软件开发上，而且各类科研都需要用到C语言，具体应用比如单片机

29、以及嵌入式系统开发。4.5.5 C+ C+这个词在中国大陆的程序员圈子中通常被读做“C加加”，而西方的程序员通常读做“C plus plus”，“CPP”。 它是一种使用非常广泛的计算机编程语言。C+是一种静态数据类型检查的，支持多重编程范式的通用程序设计语言。它支持过程化程序设计、数据抽象、面向对象程序设计、制作图标等等泛型程序设计等多种程序设计风格。4.5.6 JavaJava语言其实最早是诞生于1991年，起初被称为OAK语言，是SUN公司为一些消费性电子产品而设计的一个通用环境。他们最初的目的只是为了开发一种独立于平台的软件技术，而且在网络出现之前，OAK可以说是默默无闻，甚至差点夭折

30、。但是，网络的出现改变了OAK的命运。Java的开发环境有不同的版本，如sun公司的Java Development Kit， 简称JDK。后来微软公司推出了支持Java规范的Microsoft Visual J+ Java开发环境，简称 VJ+。它有以下特点：平台无关性 平台无关性是指Java能运行于不同的平台。Java引进虚拟机 原理，并运行于虚拟机，实现不同平台的Java接口之间。使用Java编写的程序能在世界范围内共享。Java的数据类型与 机器无关，Java虚拟机（Java Virtual Machine）是建立在硬件和操作系统之上，实现Java二进制代码的解释执行功能， 提供于不同

31、平台的接口的。 安全性 Java的编程类似C+，学习过C+的读者将很快掌握Java的精髓。Java舍弃了C+的指针对存储器地址的直接操作，程序运行时，内存由操作系统分配，这样可以避免病毒通过指针侵入系统。Java对程序提供了安全管理器，防止程序的非法访问。 面向对象 Java吸取了C+面向对象的概念，将数据封装于类中，利用类的优点，实现了程序的简洁性和便于维护性。类的封装性、继承性等有关对象的特性，使程序代码只需一次编译，然后通过上述特性反复利用。程序员只需把主要精力用在类和接口的设计和应用上。Java提供了众多的一般对象的类，通过继承即可使用父类的方法。在Java中，类的继承关系是单一的非多重的，一个子类只有一个父类，子类的父类又有一个父类。Java提供的Object类及其子类的继承关系如同一棵倒立的树形，根类为Object类，