新编计算机导论课件作者周苏新编导论-第9章节算法 程序设计与数据结构.ppt

周 苏 教授 QQZS@ 即使对于一个并不打算成为程序员的人来说，学习计算机程序设计和软件开发的一般知识也是很有意义的。 首先，你在工作中可能会使用许多程序，你会发现，一个字处理软件就可能包含了几十万条程序指令，因此，其中存在一些错误是在所难免的。 同样，你会发现，一个人很难编写一个字处理软件，这通常是由专业的编程小组共同完成的。虽然现在一般用户已经不需要去专门编写自己想用的程序了，但仍然有可能会通过修改一些程序来满足某个特殊的要求，这时，你对计算机编程的了解将有助于拟订建设性的计划。 计算机程序就是告诉计算机如何解决问题的一系列指令的有序集合。但是，写程序比写信要难得多，计算机编程非常强调结构性和严谨，丝毫不能马虎。计算机程序设计首先从问题的描述开始，它是算法的基础，而算法则是程序的基础。计算机编程的基本概念包括：问题描述、算法设计、编码、控制结构、测试和建立文档等。 算法 编写计算机程序 测试和文档 编程语言的特点 选择编程语言 数据结构 9.1 算法 9.1.1 问题描述 9.1.2 算法的概念 9.1.3 三种结构 9.1.4 算法的框图表示 9.1.5 算法的定义 9.1 算法 算法，也就是分步解决问题的过程，其非正式定义是：算法是一种逐步解决问题或完成任务的方法。按照这种定义，算法完全独立于计算机系统，并且接收一组输入数据，并产生一组输出数据。 9.1.1 问题描述 提出问题才能解决问题，问题描述就是要说明一些能用来解决问题的要素。一个表达清晰的问题描述应该具备以下三个特征： 1) 能说明描述问题范畴的任何假设。 2) 罗列出已知的所有条件。 3) 具体说明需要解决什么问题。 在一个问题描述中，假设就是为了方便设计而假定地认为是正确的陈述。问题描述中的已知信息就是要计算机帮助解决问题时提供给它的信息。已知信息在问题描述中经常用“已知”来给出。在说明已知条件后，应该说明问题解决后该如何做决定，也就是想让程序输出什么信息。 9.1.2 算法的概念 我们先来分析一个算法的简单例子。假设要开发一个从一组正整数中找到其中最大整数的算法。这个算法应该能从一组任意的整数中 (例如5、1 000、10 000、1 000 000等) 找出其中的最大值，并且，这个算法必须具有通用性并独立于整数的个数。 要完成从许多整数中找到最大值的任务不可能 (由一个人或一台计算机) 只用一步完成，算法必须一个个地去测试每一个数。为此，可以用一种直接的方法，例如先对一组少量的数 (如5个) 进行分析，然后把解决方法扩大到任意多的整数。可以假设，即使是5个数的例子，算法也必须一个接一个地处理那些数。看到第一个整数时，它并不知道剩下的其他整数的值。等处理完第一个数，算法才开始处理第二个数，照此进行。 我们称这个算法为取最大值 (Find Largest) ，每个算法都有自己的名字。这个算法接收一组5个数 (作为输入) ，然后输出其中的最大值。 这个算法中，为找到最大值采取了下面5个步骤： 第一步：算法检查第一个整数 (12) 。因为还没有检查其他整数，所以当前的最大值就是第一个数。算法中定义了一个称为Largest的变量，并把第一个数的值 (12) 赋给它。 第二步：算法把上一步得到的最大值Largest (即12) 和第二个数 (8) 进行比较，发现目前的最大值大于第二个数，Largest中的数还是最大值，不需要改变。 第三步：新的数 (13) 大于Largest，最大值应该由第三个数 (13) 代替。算法把13赋给Largest。 第四步：当前Largest比第四个数 (9) 大，该步中最大值未改变。 第五步：当前Largest比第五个数 (11) 大，该步中最大值未改变。 最后，因为已经没有其他数需要处理，所以算法输出Largest的值 (13) 。 现在有两个问题： 首先，第一步中的动作与其他步骤中的不一样。 其次，第二步到第五步的程序功能一样，但程序描述语言不一样。 第一步不同于其他步是因为那时最大值Largest还没有初始化。如果一开始就把最大值Largest赋成0 (没有正整数比0小) ，那么第一步就可写成和其他步一样了。于是，增加一个新的步骤 (称为第0步，表明它要在处理任何其他数之前完成) 。再把其余程序段都写成“如果当前的数大于最大值Largest，那么它就成为最大值”。 这个算法可以泛化吗？假使要从N个正整数中找到最大值，N的值可能是l 000或1000 000，或者更多。当然，可以重复每一步。但是如果为程序改变算法，就必须编写N步动作。有一种更好的方法可以改进它。只要让计算机重复这个步骤N次。现在，在算法图