搜索
第6章算法初步6.1算法的概念6.2算法的表示方法6.3结构化程序设计退出6.1算法的概念6.1.1什么是算法当我们要编写一个程序的时候，我们总要首先想好这个程序是干什么的？应该如何实现这些目标？应该先进行什么处理、后进行什么处理？所处理的数据的格式是是什么？遇到一些复杂的问题，我们可能还需要考虑采用什么数学方法。这一切都涉及一个专业名词——“算法”。所谓算法，就是程序处理问题的步骤与方法。很多时候，程序设计者所面临的问题就是寻找一个合适的算法。例如，一个熟练的程序员，要设计一个下“五子棋”的游戏程序，对他而言，C语言的编程规则已经清楚。他所面对的核心问题是寻找一种可以模拟人下棋的算法。因此，算法在软件设计中具有重要的地位。正如著名的计算机科学家沃思（NikiklausWirth）所指出的如下公式：程序=数据结构+算法6.1.2算法的特性一个方法要成为我们可以在程序设计中所使用的算法，需要具备如下特征。1有穷性一个算法要在有限的步骤内解决问题（这里所说的步骤是指计算机执行步骤）。计算机程序不能无限地运行下去（甚至不能长时间地运行下去），所以一个无限执行的方法不能成为程序设计中的“算法”。例如，求某一自然树N的阶乘：N！=1*2*3*......*N这是一个算法。因为对任何一个自然数而言，无论这个数多大，总是有限的。用这个公式计算N！总是需要有限的步骤。但是，以下计算公式则不能作为算法，因为其计算步骤是无限的：SUM=1+1/1+1/2+1/3+......+1/n+......事实上有穷性是指合理的范围之内，比如，设计了一个算法是有限的，但按照目前计算机发展的水平要计算1000年才能完成，这样的算法没有实际意义，可以不当作算法，可以视为无穷。实际上，在计算机的许多加密算法中，可以解密的方法不是不存在，而是要执行这样的解密算法需要极其大量的时间。这样就实现了保密。所谓保密就是让在一定的时间内信息不被他人知晓。当然，计算机技术的进步回对算法有影响。对于现在的计算机1000年才能完成的算法可能几个月的功夫就能完成，到那时某些现在无穷性的方法将变成切实可行的算法。2确定性算法中操作步骤的顺序和每一个步骤的内容都应当是确定的，不应当是含糊不清的。它也不能有不同的解释存在，即不能具有“二义性”，不应当产生两种或多种以上的含义。3有零个或多个输入输入就是从外界取得必要的信息。一个算法可以有零个或多个输入，例如：输入一个年份，判断其是否是闰年。同时一个算法可以没有输入，例如：计算出5！是多少。4有一个或多个输出算法的目的就求解，“解”就是我们想要得到的最终结果。输出是同输入有着某些特定关系的量。一个算法得到的最终结果就是输出。没有输出的算法是没有意义的。5可执行性一个算法应当是可以由计算机执行的，算法中描述的操作都是可以通过计算机的运行来实现。6.1.3算法设计的要求什么样的算法是好的算法呢？我们在设计算法时应向哪些方面努力呢？一般包括以下这几个方面。1正确性一个算法应当能够解决具体问题。其“正确性”可分为以下几个方面：不含逻辑错误；对于几组输入数据能够得出满足要求的结果；对于精心选择的典型、苛刻的输入数据都能得到要求的结果；对于一切合法的输入都能输出满足要求的结果；2可读性算法应该可以用能够被人理解的形式表示。太复杂的、不能被程序员所理解的算法难以在程序设计中采用。3健壮性健壮性指算法具有抵御“恶劣”输入信息的能力。当输入数据非法时，算法也能适当的作出反应或进行处理，而不会产生莫明其妙的输出结果。例如，当输入三个边的长度值来计算三角形的面积时，一个有效的算法在三个输入数据不能构成一个三角形时，应报告输入的错误，应返回一个表示错误或错误性质的值并中止执行。4效率与低存储量的需求高效率和低存储量是优秀程序员追求的目标。效率指的是算法执行时间，对于一个问题如果有多个算法可以解决，执行时间短的算法效率高。存储量需求指算法执行进程所需要的最大存储空间。效率与低存储量需求这两者都与问题规模有关。占用存储量最小、运算时间最少的算法就是最好的算法。但是，在实际中，运行时间和存储空间往往是一对矛盾。要根据具体情况选择更优先考虑哪一个因素。6.2算法的表示方法算法的实质是一种逻辑关系。对于这样一种关系，可以用多种方式来表达。常用的有自然语言、流程图（传统的流程图和结构化的流程图）、伪代码、N-S流程图、计算机语言等。6.2.1自然语言表示算法自然语言是相对于计算机语言而言的。就是指人们在日常生活中使用的语言，如汉语、英语、发语等。对于某些程序员来说，自然语言通俗易懂。但是，对于规模大、复杂的算法，使用自然语言来描述，往往很冗长，不直观，而且容易发生歧义。比如对于以下这句话：如果A大于B，就给它加1。在理解时就可能出现歧义，是给A加1？还是给B加1。对于以上的一段话，如果我们用C语言进行编程则为：if(AB)A=A+1;正是由于自然语言描述算法具有的缺陷，所以在程序设计中没有人使用。6.2.2传统流程图表法流程图表示法就是用各种图框表示各种操作。这种表示法的优点是直观易于理解。流程图表示法是美国国家标准化协会ANSI（AmreicanNationalStandardInstitute）规定的。一些常用的流程图符号在Word中都可以通过“绘图”命令来绘制。6.2.3用N-S流程图表示算法1973年美国学者I.Nassi和B.Shneiderman提出了一种新的流程图形式。在这种流程图中，完全去掉了带箭头的流程线。全部算法都是在一个矩形框内，在该框内还包含其它的从属于它的框。式者说由一些基本的框组成一个大框。这种方法就以这两位学者的名字缩写而成，被称为“N—S盒图”。N-S盒图可以表示以下几种典型结构。1顺序结构在顺序结构中，算法的步骤是依照先后顺序依此执行的。即执行完第一步骤后，再执行第二步骤。2选择结构选择结构也叫做条件选择。即根据某一条件选择下一步的执行操作。如图6-4和图6-5所示。3循环结构循环结构就是当某一条件满足或不满足时，一直执行某些操作的算法。它可以再细分为以下两种：当型循环。当某一条件满足时一直执行某些操作。直到型循环。就是一直执行某些操作，直到某一条件不满足时为止。6.2.4用伪码表示算法所谓“伪代码”就是程序员自己定义的一种“语言体系”，它不同于自然语言（比自然语言简单），也不同于任何一种具体的计算机语言（这样才有广泛性）。它有自己的文字和符号体系，用来描述算法。它比自然语言更接近计算机语言。便于向计算机语言过渡。并不是每一个程序员都需要也都可以定义“伪码”。因为你自己定义一套伪码供自己一个人使用没有太大的意义。一般而言，一个“伪码体系”是由很大的软件公司定义，供全公司的程序员使用。6.3结构化程序设计6.3.1三种基本结构传统的流程图用流程线描述各框的执行顺序。但对流程线的使用并没有严格的限制，因此，若使用者不受限制的随意转移流程时，就变得很混乱。实际上，即便程序员努力控制流程的变化，但当算法复杂时，流程图往往不可避免地变得复杂和混乱。而但结构异常复杂时，“N—S盒图”也很复杂。那么，能不能只使用几种基本的结构，来组合表达出各种复杂的算法结构呢？1966年，Bohra和Jacopini给出了肯定的答案。他们证明了：使用顺序、分支（也叫做“条件选择“）和循环这三种基本结构可以表示任何一个算法的基本单元。这正是我们在以上只讲述这三种基本结构的原因。6.3.2结构化程序设计从目前的编程实践看，结构化程序设计的思路已经被绝大多数程序员所接受。人们普遍认为，必须采用结构化的程序设计方法。因为结构化程序具有结构清晰、便于阅读、便于修改和便于维护的优点。结构化程序设计的基本思路是：把一个复杂的问题的求解过程分阶段进行，每个阶段处理的问题都控制在人们容易理解的范围之内。采取以下的方法保证得到结构化的程序：自顶向下；逐步细化（求精）；模块化设计；结构化编码。采用自顶向下、逐步细化的方法可以使程序的结构清晰、层次分明、容易改写。就象进行房屋设计所采用的施工步骤一样：先进行整体的规划，画出施工的图纸，再进行各个部分的设计，最后进行细节的设计（楼宇通信系统、安全设施的装备、办公系统、室内的装修）。结构化程序具有如下的特征：一个程序单元由顺序、分支和循环这三种基本结构组成；一个大的程序由若干个不同功能的小模块组成；每一个小模块只用一个入口和一个出口；6.3.3结构化程序设计中的注意事项在我们使用这三种基本结构来构造程序模块时，应该注意下述事项。1不可交叉在顺序结构、循环结构和分支结构之间，允许互相嵌套（参见图6-10），但不允许交叉。具体地说，循环结构和循环结构之间不能交叉、分支结构和分支结构之间不能交叉、循环结构和分支结构之间不能交叉。另外，循环和分支之间也不能交叉。【例6-1】(见课本）【例6-2】(见课本）同样的道理，不能在一个循环体中包括分支的一支，而在另一循环体中，包含分支的另一支。这也交叉了。在具体编程实践中，较多出现的编程错误是：分支与分支交叉、循环与循环交叉。分支与循环交叉这类错误并不多见。2不可从循环体外转入循环体内在结构化程序设计中，我们强调一个程序模块具有单入口和单出口。一般不允许从循环体内转到循环体外（当有多层循环时，特别强调这一点）。值得特别说明的时，绝对不允许从循环体外转到循环体内。6.3.4算法的合理性与优化在一个算法被设计出来之后，要考虑其合理性。如果可能，要对其优化。对此，我们通过以下两个例子来说明。【例6-3】(见课本）【例6-4】(见课本）