程序设计初步讲义.doc

第3章 程序设计初步 3.1 算法初步及其描述方法 3.1.1算法初步 1.什么是算法 算法是为解决一个特定问题而采取的特定的有限的步骤。广义地说，做任何事情都有算法，例如一张太极拳打法图解也可以看作是一个太极拳算法。因此，算法概念不限于算术问题，而是具有更广泛的含义。 从计算机应用的角度来说，算法是指完成一个任务所需要的具体步骤和方法（解决问题的方案）。也就是说给定初始状态或输入数据，经过计算机程序的有限次运算，能够得出所要求或期望的终止状态或输出数据。 古希腊数学家欧几里德给出的算法： 步骤1：如果p < q，交换p 和q 。 步骤2：求p/q的余数r 。 步骤3：如果r = 0则 q 就是所求的结果 。 否则反复做如下工作：令p = q，q = r，重新计算 p 和q 的余数r，直到r = 0为止，则 q 就是原来的两正整数的最大公因数。 算法常常含有重复的步骤和一些比较或逻辑判断。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。从原则上说，有了算法，人们就可以借助纸、笔和算盘等工具直接求解问题了。但如果问题比较复杂，计算步骤很多，则应通过编写计算机程序，使用计算机解决。 2.算法的特征 算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。 一个算法应该具有以下五个重要的特征： 有穷性：一个算法必须保证执行有限步之后结束。 确切性：算法的每一步骤必须有确切的定义。 输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定义了初始条件。 输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。 可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。 3.算法的类型和结构 ()算法的类型 算法可分为两大类：数值算法和非数值算法。 数值算法是为数学问题形成一个构造性解法的完备而确切的描述，并规定方法中仅允许使用加、减、乘、除等基本的算术运算。 非数值算法广泛应用在数据处理的场合。需要对大量的信息数据进行加工处理包括转换、分类、查找、排序和存储等。常用的算法有穷举、递推、顺序查找和冒泡排序等。 ()算法的结构 一个算法是由结构和原操作构成的。原操作包括：输入、输出、和比较等。的三种基本结构是：顺序结构结构和循环结构。用这三种基本结构可以表示任意一个复杂的算法。 顺序结构 顺序结构是指通过安排的排列顺序来决定流程的结构。在这种结构中，各个操作是依次执行的。顺序结构是由若干个依次执行的处理块组成，这是任何一个算法都离不开的基本主体结构。 分支结构 在绝大多数情况下，算法不会按部就班地从第一条操作执行到最后一条操作，往往由特定的条件决定执行哪，这就是分支结构。分支结构是以条件或情况的判断为起始点，它是人脑判断思维活动的抽象。最基本的分支结构是二分支结构，根据判断逻辑是否成立而决定选择一边的处理块去执行。 循环结构 循环结构是指在算法设计中，从某处开始有规律地反复执行某一处理块，这个处理块称为循环体。循环体的执行次数由一个控制循环条件决定。满足条件反复做，不满足则停止。 3.1.2算法的描述工具 设计一个算法可以根据问题的不同需要用某种语言符号来描述。目前最常用的几种算法工具有：自然语言、流程图、N-S图、伪代码等。 1.自然语言 自然语言就是人们日常使用的语言，可以是中文、英文等。用自然语言表示的算法通俗易懂，但一般篇幅较冗长，表达上不易准确，易引起理解上的歧义性（即对同一段文字，不同的人会有不同的理解）。输入3个数，求其最大数。分析：分支结构设num1num2，num3存放3个数，max存放其最大值。为求其最大数，只要对3个数进行比较，可按如下步骤去做：S1：输入3个数num1num2，num3； S2：先把第1个数num1的值赋给max； S3：将num2与max比较，如果num2>max，则把num2的值赋给max，否则，不做任何事情。 S4：将num3与max比较，如果num3>max，则把num3的值赋给max，否则，不做任何事情。 S5：输出max的值，即最大值。 【】…+100。分析：结构设存放…+100，可按如下步骤去做： S1：； S：S3：S4： S5：输出的值。2.流程图 流程图是用一组规定的图形符号、流程线和文字说明来表示算法直观形象，易于理解。流程图的特点是用流线给算法执行中的每一个步骤指定了逻辑上的顺序，因此能把程序执行的控制流表达得十