第四章算法程序和编程.docx
《第四章算法程序和编程.docx》由会员分享，可在线阅读，更多相关《第四章算法程序和编程.docx（28页珍藏版）》请在冰点文库上搜索。
第四章算法程序和编程
《计算机导论》教案
第四章算法、程序和编程
学习目的和要求：
1.了解算法与程序概念
2.理解算法的复杂性与NP问题
3.熟悉基本算法
4.知道数据和数据结构
5.熟悉高级语言
6.掌握程序设计规划
7.了解程序理论和软件工程
学习重点：
1.算法的复杂性与NP问题
2.数据和数据结构
3.基本算法
4.程序理论和软件工程
学习难点：
1.数据和数据结构
2.基本算法
学时：
10
学习内容：
课后反馈
讨论
围绕以下问题，组织学生分组讨论，然后让每组代表阐述他们的看法和思想。
1.怎样养成良好的算法思想？
讨论目的：
了解算法的描述方式，并掌握其中的一种。
可围绕以下内容展开讨论：
算法描述常用的方法有自然语言，伪代码和程序流程图。
通过该章的学习，能够用以上方法设计完整、合理的算法。
为下学期C语言的学习奠定良好的基础。
2.如何成为一个优秀的程序开发人员？
讨论目的：
了解程序员工作流程，逐步养成良好的编程习惯。
可围绕以下内容展开讨论：
开发软件要按照软件工程的步骤统一实施和管理，协同工作等。
3.学习良好的软件开发习惯。
讨论目的：
了解软件开发的过程，熟悉软件开发过程中容易出现的问题：
可围绕以下内容展开：
软件开发过程：
问题定义、可行性分析、总体描述、系统设计、编码、调试和测试、验收与运行、维护等阶段。
在软件开发过程中要有完整的文档，数据，程序等资料。
要按照软件工程的思想来开发软件以降低风险。
4.软件工程的功能及应用。
讨论目的：
了解软件工程的功能，以及如何将软件工程的思想应用到软件开发中：
可围绕以下内容展开讨论：
软件工程的目标是：
在给定成本、进度的前提下，开发出具有可修改性、有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性并且满足用户需求的软件产品。
追求这些目标有助于提高软件产品的质量和开发效率，减少维护的困难。
5.如何学好一门基础的编程语言。
讨论目的：
了解常用的变成语言，选择其中一种编程语言去深入学习，为以后理论学习和实践奠定基础。
可围绕以下内容讨论：
选一门你感兴趣的语言Java或者是C#之类，VC也可以，做一个实际的东西，比如做个聊天室，做个画图程序（可以保存），做个五子棋或者象棋的程序，从这些小的但是完整的程序开始做，做的过程中碰到问题自己查资料，或者到相应论坛提问，做好后总结，慢慢提高的自己的编程能力。
§4.1算法与程序
4.1.1算法
算法定义1：
算法是一组明确步骤的有序集合，它产生结果，并在有限的时间内终止。
有以下特性：
1有序集合
2明确步骤
3产生结果
4在有限的时间内结束
算法定义2：
给定问题和设备，一个算法是用该设备可理解的语言表示的，解决这个问题的一种方法是精确刻画。
特别地，算法具有以下特征属性：
①算法应用于一个具体的输入集合或问题描述将在有穷步动作之后得到结果；
②该序列有一个唯一的初始动作：
③该序列中的每一个动作有一个唯一的后继动作
④该序列终止时或者得到这个问题的解，或者因该问题不可解而获得不可解说明。
算法定义3：
一个算法，就是一个有穷规则的集合，其中之规则确定了一个解决某一特定型问题的运算序列。
此外，算法的规则序列必须满足以下5个重要条件，即具有以下五个特性：
①有穷性。
算法必须总是在执行有穷步之后结束
②确定性。
算法的每一个步骤必须是确切地定义的；
③输入。
算法有零个或多个输入
④输出。
算法有一个或多个输出，即与输入有某个关系的量。
⑤能行性。
算法中有待执行的运算和操作必须是相当基本的，即是说，它们原则上是能够精确地进行的，而且用笔和纸做有穷次就可以完成。
4.1.2子算法
子算法：
在结构化编程时应用模块化或分单元的办法来构成这个程序，这些被分成的小单元我们称之为子算法（子程序、子例程、过程、函数、方法和子模块等）。
每个子算法又可以划分为更小的子算法，这个过程持续到子算法变为最本质的（可被立即理解的）描述为止。
使用编程子算法的优点：
5使程序更容易理解
6可以在主算法中不同的地方调用
4.1.3程序
程序就是一种事先编制好了具有特殊功能的指令序列。
其中，指令序列可以是机器指令，汇编语言，也可以是高级语言的语句指令。
（1）伪代码：
是在编写算法时，为了更好地表示算法本身，不在一些小的细节上纠缠，而采用类似于英语（或其他自然语言）表示算法的算法表示方法。
例1用伪代码写出一个求两个数的平均值的算法。
解：
AverageOfTwo
Input:
Twonumbers
①Addthetwonumbers
②Dividetheresultby2
③Returntheresultbystep2
End
（2）流程图
程序流程图是人们对解决问题的方法、思路或算法的一种描述。
流程图的优点：
（a）采用简单规范的符号，画法简单；（b）结构清晰，逻辑性强；c）便于描述，容易理解。
程序流程图有以下几部分组成：
（1）起始框
（2）终止框（3）执行框（4）判别框（5）箭头。
例2计算并打印整个班级中每个学生三门课程考试成绩的平均分数。
解：
程序流程图如图4-1：
图4-1程序流程图
§4.2计算的复杂性与NP问题
所谓"计算复杂性"，通俗说来，就是用计算机求解问题的难易程度。
其度量标准：
一是计算所需的步数或指令条数（这叫时间复杂度），二是计算所需的存储单元数量（这叫空间复杂度）。
4.2.1算法复杂性描述
算法在执行过程中总共所需要的初等运算的步数来表示算法用于求解任一问题的某一例子时所需的时间。
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）P与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递归、迭代算法
递归、迭代算法：
递归算法是算法自我调用的过程。
迭代的定义：
算法中没有包含算法自身，只是利用上一步计算的结果得出最后答案的算法。
递归的定义：
算法中包含了算法自身的调用的算法。
例3求n的阶乘
解：
（1）用递归算法实现如下：
Factorial
Input:
Apositiveintegernum
if（numisequalto0）
then
return1
else
returnnumxFactorial（num–1）
Endif
End
（2）用迭代算法实现如下：
Factorial
Input:
Apositiveintegernum
SetFactNto0
SetitoI
while（iislessthanorequaltonum）
SetFactNtoFactNxI
Incrementi
Endwhile
ReturnFactN
End
4.3.2分治算法
就是将一个难以直接解决的大问题，通过分析，分解为一些规模较小的相同问题，进而对各个小问题进行解决，最后达到整个问题的解决。
例如，求N个元素集合S的最大元素和最小元素问题。
可以将S分成大小相等的两个几个S1和S2，然后递归的求出S1和S2中的最大元素和最小元素，再经过比较得到最终结果。
这就是典型的分治思想的应用。
§4.4数据和数据结构
4.4.1数据与数据类型
数据就是算法所要处理的对象。
通常分为数值数据和非数值数据。
表4-1列出了常用数据类型之间的比较：
表4-1简单数据类型
类型
在VB中的大小
和名字
在C/C++中的
大小和名字
在Java中的
大小和名字
Boo1ean
1位—Boolean
仅在一些编译器
下使用
1位—boo1ean
Character
没有字符类型
1字节—Char
2字节—Char
Shortinteger
没有short类型
2字节—short
2字节—short
Integer
2字节—Integer
2字节—int
4字节—int
1ongintger
4字节—Long
4字节—long
4字节—1ong
F1oating-point
4字节—Single
4字节—float
4字节—float
double-precision
8字节—Double
8字节—double
8字节—double
4.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）数组
数组是在程序设计中，为了处理方便，把具有相同类型的若干变量按有序的形式组织起来的一种形式。
这些按序排列的同类数据元素的集合称为数组。
在Ｃ语言中，数组属于构造数据类型。
一个数组可以分解为多个数组元素，这些数组元素可以是基本数据类型或是构造类型。
因此按数组元素的类型不同，数组又可分为数值数组、字符数组、指针数组、结构数组等各种类别。
（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），在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。
有向边也称为弧（Arc），边的始点称为弧尾（Tail），终点称为弧头（Head）。
②无向图
若图G中的每条边都是没有方向的，则称G为无向图（Undigraph）。
无向图中的边均是顶点的无序对，无序对通常用圆括号表示。
§4.5高级语言简介
高级语言是目前绝大多数编程者的选择⊥汇编语言相比，它不但将许多相关的机器指令合成为单条指令，并且去掉了与具体操作有关但与完成工作无关的细节，例如使用堆栈、寄存器等，这样就大大简化了程序中的指令。
同时，由于省略了很多细节，编程者也就不需要有太多的专业知识。
高级语言主要是相对于汇编语言而言，它并不是特指某一种具体的语言，而是包括了很多编程语言，如目前流行的vb、vc、foxpro、delphi等，这些语言的语法、命令格式都各不相同。
高级语言所编制的程序不能直接被计算机识别，必须经过转换才能被执行，按转换方式可将它们分为两类解释类执行方式类似于我们日常生活中的同声翻译”，应用程序源代码一边由相应语言的解释器翻译”成目标代码（机器语言），一边执行，因此效率比较低，而且不能生成可独立执行的可执行文件，应用程序不能脱离其解释器，但这种方式比较灵活，可以动态地调整、修改应用程序。
编译类编译是指在应用源程序执行之前，就将程序源代码翻译”成目标代码（机器语言），因此其目标程序可以脱离其语言环境独立执行，使用比较方便、效率较高。
但应用程序一旦需要修改，必须先修改源代码，再重新编译生成新的目标文件（＊.obj）才能执行，只有目标文件而没有源代码，修改很不方便。
现在大多数的编程语言都是编译型的，例如visualc＋＋、visualfoxpro、delphi等。
4.5.1Basic
BASIC是属于高阶程式语言的一种，英文名称的全名是"Beginner'sAll-PurposeSymbolicInstructionCode"，取其首字字母简称"BASIC"，就名称的含意来看，是"适用于初学者的多功能符号指令码"，是一种在计算机发展史上应用最为广泛的程式语言。
有如下特点：
（1）构成简单。
BASIC语言的最基本语句只有17种，而且它们都是常见的英文单词或其变形，如READ、END等，很容易学习和掌握。
（2）是一种“人机会话”式的语言。
通过键盘操作，用BASIC语言编写完的程序，可以在计算机上边编写、边修改、边运行。
而且还可以在运行中向人们提示信息的指出错误，要求人去改正，即实现了人和机器的对话。
（3）功能较全、适用面广。
BASIC语言除了能进行科学计算和数据处理外，还能进行字符处理、图形处理、音乐演奏等。
因此BASIC语言不仅适用于科学计算，也适用于事务管理、计算机辅助教学和游戏编程等方面。
（4）执行方式灵活。
BASIC语言提供两种执行方式，分别是程序执行方式和命令执行方式。
程序执行方式把BASIC语言编写成一个完整的程序送入计算机执行；命令执行方式不编写程序，直接从键盘输入某些命令（称键盘命令），计算机能立即执行这些命令。
BASIC语言采用的是解释器，就是逐句翻译成机器语言程序，译出一句就立即执行，即边翻译边执行．与编译器比起来，解释器费时比编译器更多，但可少占计算机的内存．
4.5.2FORTRAN
FORTRAN语言是世界上第一个被正式推广使用的高级语言。
它是1954年被提出来的，1956年开始正式使用，至今已有五十多年的历史，但仍历久不衰，它始终是数值计算领域所使用的主要语言。
FORTRAN语言是FormulaTranslation的缩写，意为“公式翻译”。
它是为科学、工程问题或企事业管理中的那些能够用数学公式表达的问题而设计的，其数值计算的功能较强。
4.5.3Pascal
Pascal是种高阶的程序设计语言，由瑞士苏黎世理工学院的尼古拉斯·沃斯教授设计，ISO对Pascal进行修改以后，形成了标准Pascal语言。
Pascal语言还是一种自编译的语言，这就使它的可靠性大大提高了。
Pascal是最早出现的结构化编程语言，具有丰富的数据类型和简洁灵活的操作语句，适于描述数值和非数值的问题。
4.5.4C
C语言是CombinedLanguage（组合语言）的中英混合简称。
是一种计算机程序设计语言。
它既具有高级语言的特点，又具有汇编语言的特点。
它可以作为工作系统设计语言，编写系统应用程序，也可以作为应用程序设计语言，编写不依赖计算机硬件的应用程序。
因此，它的应用范围广泛，不仅仅是在软件开发上，而且各类科研都需要用到C语言，具体应用比如单片机以及嵌入式系统开发。
4.5.5C++
C++这个词在中国大陆的程序员圈子中通常被读做“C加加”，而西方的程序员通常读做“Cplusplus”，“CPP”。
它是一种使用非常广泛的计算机编程语言。
C++是一种静态数据类型检查的，支持多重编程范式的通用程序设计语言。
它支持过程化程序设计、数据抽象、面向对象程序设计、制作图标等等泛型程序设计等多种程序设计风格。
4.5.6Java
Java语言其实最早是诞生于1991年，起初被称为OAK语言，是SUN公司为一些消费性电子产品而设计的一个通用环境。
他们最初的目的只是为了开发一种独立于平台的软件技术，而且在网络出现之前，OAK可以说是默默无闻，甚至差点夭折。
但是，网络的出现改变了OAK的命运。
Java的开发环境有不同的版本，如sun公司的JavaDevelopmentKit，简称JDK。
后来微软公司推出了支持Java规范的MicrosoftVisualJ++Java开发环境，简称VJ++。
它有以下特点：
①平台无关性
平台无关性是指Java能运行于不同的平台。
Java引进虚拟机原理，并运行于虚拟机，实现不同平台的Java接口之间。
使用Java编写的程序能在世界范围内共享。
Java的数据类型与机器无关，Java虚拟机（JavaVirtualMachine）是建立在硬件和操作系统之上，实现Java二进制代码的解释执行功能，提供于不同平台的接口的。
②安全性
Java的编程类似C++，学习过C++的读者将很快掌握Java的精髓。
Java舍弃了C++的指针对存储器地址的直接操作，程序运行时，内存由操作系统分配，这样可以避免病毒通过指针侵入系统。
Java对程序提供了安全管理器，防止程序的非法访问。
③面向对象
Java吸取了C++面向对象的概念，将数据封装于类中，利用类的优点，实现了程序的简洁性和便于维护性。
类的封装性、继承性等有关对象的特性，使程序代码只需一次编译，然后通过上述特性反复利用。
程序员只需把主要精力用在类和接口的设计和应用上。
Java提供了众多的一般对象的类，通过继承即可使用父类的方法。
在Java中，类的继承关系是单一的非多重的，一个子类只有一个父类，子类的父类又有一个父类。
Java提供的Object类及其子类的继承关系如同一棵倒立的树形，根类为Object类，
升级会员 