C语言程序设计2第6章算法初步

《C语言程序设计2第6章算法初步》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章算法初步6.1算法的概念6.2算法的表示方法6.3结构化程序设计退出6.1算法的概念6.1.1什么是算法当我们要编写一个程序的时候，我们总要首先想好这个程序是干什么的？应该如何实现这些目标？应该先进行什么处理、后进行什么处理？所处理的数据的格式是是什么？遇到一些复杂的问题，我们可能还需要考虑采用什么数学方法。这一切都涉及一个专业名词——“算法”。所谓算法，就是程序处理问题的步骤与方法。很多时候，程序设计者所面临的问题就是寻找一个合适的算法。例如，一个熟练的程序员，要设计一个下“五子棋”的游戏程序，对他而言，C语言的编程规则已经清楚。他所面对

2、的核心问题是寻找一种可以模拟人下棋的算法。因此，算法在软件设计中具有重要的地位。正如著名的计算机科学家沃思（NikiklausWirth）所指出的如下公式：程序=数据结构+算法6.1.2算法的特性一个方法要成为我们可以在程序设计中所使用的算法，需要具备如下特征。1有穷性一个算法要在有限的步骤内解决问题（这里所说的步骤是指计算机执行步骤）。计算机程序不能无限地运行下去（甚至不能长时间地运行下去），所以一个无限执行的方法不能成为程序设计中的“算法”。例如，求某一自然树N的阶乘：N！=1*2*3*......*N这是一个算法。因为对任何一个自然数而言，

3、无论这个数多大，总是有限的。用这个公式计算N！总是需要有限的步骤。但是，以下计算公式则不能作为算法，因为其计算步骤是无限的：SUM=1+1/1+1/2+1/3+......+1/n+......事实上有穷性是指合理的范围之内，比如，设计了一个算法是有限的，但按照目前计算机发展的水平要计算1000年才能完成，这样的算法没有实际意义，可以不当作算法，可以视为无穷。实际上，在计算机的许多加密算法中，可以解密的方法不是不存在，而是要执行这样的解密算法需要极其大量的时间。这样就实现了保密。所谓保密就是让在一定的时间内信息不被他人知晓。当然，计算机技术的进步

4、回对算法有影响。对于现在的计算机1000年才能完成的算法可能几个月的功夫就能完成，到那时某些现在无穷性的方法将变成切实可行的算法。2确定性算法中操作步骤的顺序和每一个步骤的内容都应当是确定的，不应当是含糊不清的。它也不能有不同的解释存在，即不能具有“二义性”，不应当产生两种或多种以上的含义。3有零个或多个输入输入就是从外界取得必要的信息。一个算法可以有零个或多个输入，例如：输入一个年份，判断其是否是闰年。同时一个算法可以没有输入，例如：计算出5！是多少。4有一个或多个输出算法的目的就求解，“解”就是我们想要得到的最终结果。输出是同输入有着某些特定

5、关系的量。一个算法得到的最终结果就是输出。没有输出的算法是没有意义的。5可执行性一个算法应当是可以由计算机执行的，算法中描述的操作都是可以通过计算机的运行来实现。6.1.3算法设计的要求什么样的算法是好的算法呢？我们在设计算法时应向哪些方面努力呢？一般包括以下这几个方面。1正确性一个算法应当能够解决具体问题。其“正确性”可分为以下几个方面：不含逻辑错误；对于几组输入数据能够得出满足要求的结果；对于精心选择的典型、苛刻的输入数据都能得到要求的结果；对于一切合法的输入都能输出满足要求的结果；2可读性算法应该可以用能够被人理解的形式表示。太复杂的、不能

6、被程序员所理解的算法难以在程序设计中采用。3健壮性健壮性指算法具有抵御“恶劣”输入信息的能力。当输入数据非法时，算法也能适当的作出反应或进行处理，而不会产生莫明其妙的输出结果。例如，当输入三个边的长度值来计算三角形的面积时，一个有效的算法在三个输入数据不能构成一个三角形时，应报告输入的错误，应返回一个表示错误或错误性质的值并中止执行。4效率与低存储量的需求高效率和低存储量是优秀程序员追求的目标。效率指的是算法执行时间，对于一个问题如果有多个算法可以解决，执行时间短的算法效率高。存储量需求指算法执行进程所需要的最大存储空间。效率与低存储量需求这两者

7、都与问题规模有关。占用存储量最小、运算时间最少的算法就是最好的算法。但是，在实际中，运行时间和存储空间往往是一对矛盾。要根据具体情况选择更优先考虑哪一个因素。6.2算法的表示方法算法的实质是一种逻辑关系。对于这样一种关系，可以用多种方式来表达。常用的有自然语言、流程图（传统的流程图和结构化的流程图）、伪代码、N-S流程图、计算机语言等。6.2.1自然语言表示算法自然语言是相对于计算机语言而言的。就是指人们在日常生活中使用的语言，如汉语、英语、发语等。对于某些程序员来说，自然语言通俗易懂。但是，对于规模大、复杂的算法，使用自然语言来描述，往往很冗长

8、，不直观，而且容易发生歧义。比如对于以下这句话：如果A大于B，就给它加1。在理解时就可能出现歧义，是给A加1？还是给B加1。对于以上的一