C语言程序设计2第六章算法初步.ppt

第6章 算法初步 6.1 算法的概念 6.2 算法的表示方法 6.3 结构化程序设计 6.1 算法的概念 6.1.1 什么是算法 当我们要编写一个程序的时候，我们总要首先想好这个程序是干什么的？应该如何实现这些目标？应该先进行什么处理、后进行什么处理？所处理的数据的格式是是什么？遇到一些复杂的问题，我们可能还需要考虑采用什么数学方法。这一切都涉及一个专业名词——“算法”。 所谓算法，就是程序处理问题的步骤与方法。 很多时候，程序设计者所面临的问题就是寻找一个合适的算法。 例如，一个熟练的程序员，要设计一个下“五子棋”的游戏程序，对他而言，C语言的编程规则已经清楚。他所面对的核心问题是寻找一种可以模拟人下棋的算法。因此，算法在软件设计中具有重要的地位。正如著名的计算机科学家沃思（Nikiklaus Wirth）所指出的如下公式： 程序=数据结构+算法 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 效率与低存储量的需求 高效率和低存储量是优秀程序员追求的目标。效率指的是算法执行时间，对于一个问题如果有多个算法可以解决，执行时间短的算法效率高。存储量需求指算法执行进程所