《新编计算机导论 教学课件 ppt 作者 张丽娜 周苏 王文 金海溶 第11章 算法与程序设计》由会员分享，可在线阅读，更多相关《新编计算机导论 教学课件 ppt 作者 张丽娜 周苏 王文 金海溶 第11章 算法与程序设计（70页珍藏版）》请在金锄头文库上搜索。
1、,新编计算机导论,周苏 教授, QQ: 81505050 手机：13805784515 / 694515 博客: http:/ 算法与程序设计,第11章,第11章 算法与程序设计,第11章,第11章 算法与程序设计,即使对于一个并不打算成为程序员的人来说，学习计算机程序设计和软件开发的一般知识也是很有意义的。首先，你在工作中可能会使用许多程序，你会发现，一个文字处理软件就可能包含了几十万条程序指令，因此，其中存在一些错误是在所难免的。同样，还会发现，一个人很难编写一个文字处理软件，这通常是由专业的编程小组共同完成的。虽然现在一般用户已经不需要去专门编写自己想用的程序了，但仍然有可能会通过修改一
2、些程序（例如宏和二次开发）来满足某个特殊的要求，这时，你对计算机编程的了解将有助于拟订建设性的计划。,第11章 算法与程序设计,计算机程序就是告诉计算机如何解决问题的一系列指令的有序集合。但是，写程序比写信要难得多，计算机编程非常强调结构性和严谨，丝毫不能马虎。计算机程序设计首先从问题的描述开始，它是算法的基础，而算法则是程序的基础。计算机编程的基本概念包括：问题描述、算法设计、编码、控制结构、测试和建立文档等。,11.1 算法,算法，也就是分步解决问题的过程，其非正式的定义是：算法是一种逐步解决问题或完成任务的方法。按照这种定义，算法完全独立于计算机系统，并且接收一组输入数据，和产生一组输出
3、数据。,11.1.1 问题描述,提出问题才能解决问题，问题描述就是要说明一些能用来解决问题的要素。一个表达清晰的问题描述应该具备以下三个特征。 1) 能说明描述问题范畴的任何假设。 2) 罗列出已知的所有条件。 3) 具体说明需要解决什么问题。,11.1.1 问题描述,在一个问题描述中，“假设”就是为了方便设计而假定为正确的陈述。问题描述中的已知信息就是要计算机帮助解决问题时提供给它的信息。已知信息在问题描述中经常用“已知”来给出。在说明已知条件后，应该说明问题解决后该如何做决定，也就是想让程序输出什么信息。,11.1.2 算法的概念,我们先来分析一个算法的简单例子。假设要开发一个从一组正整数
4、中找到其中最大整数的算法。这个算法应该能从一组任意的整数中找出其中的最大值，并且，这个算法必须具有通用性并独立于整数的个数。,11.1.2 算法的概念,要完成从许多整数中找到最大值的任务不可能 (由一个人或一台计算机) 只用一步完成，算法必须一个个地去测试每一个数。为此，可以用一种直接的方法，例如先对一组少量的数 (如五个) 进行分析，然后把解决方法扩大到任意多的整数。假设即使是五个数的例子，算法也必须一个个地处理这些数。看到第一个整数时，它并不知道剩下的其他整数的值。等处理完第一个数，算法才开始处理第二个数，照此进行。图11-1表示了解决这个问题的一种方法。,图11-1 在5个整数中找出最大
5、值,11.1.2 算法的概念,我们称这个算法为取最大值，每个算法都有自己的名字。这个算法接收一组五个数 (作为输入) ，然后输出其中的最大值。 这个算法中，为找到最大值采取了下面五个步骤。 第一步：算法检查第一个整数 (12) 。因为还没有检查其他整数，所以当前的最大值就是第一个数。算法中定义了一个称为Largest的变量，并把第一个数的值 (12) 赋给它。 第二步：算法把上一步得到的最大值Largest (即12) 和第二个数 (8) 进行比较，发现目前的最大值大于第二个数，Largest中的数还是最大值，不需要改变。,11.1.2 算法的概念,第三步：新的数 (13) 大于Largest
6、，最大值应该由第三个数 (13) 代替。算法把13赋给Largest。 第四步：当前Largest比第四个数 (9) 大，该步中最大值未改变。 第五步：当前Largest比第五个数 (11) 大，该步中最大值未改变。 最后，因为已经没有其他数需要处理，所以算法输出Largest的值 (13) 。,11.1.2 算法的概念,现在有两个问题：首先，第一步中的动作与其他步骤中的不一样。其次，第二步到第五步的程序功能一样，但程序描述语言不一样。 第一步不同于其他步是因为那时最大值Largest还没有初始化。如果一开始就把最大值Largest赋成0 (没有正整数比0小) ，那么第一步就可写成和其他步一样
7、了。于是，增加一个新的步骤 (称为第0步，表明它要在处理任何其他数之前完成) 。再把其余程序段都写成“如果当前的数大于最大值Largest，那么它就成为最大值”。,11.1.2 算法的概念,这个算法可以泛化吗？假使要从N个正整数中找到最大值，N的值可能是l 000或1000 000，或者更多。当然，可以重复每一步。但是如果为程序改变算法，就必须编写N步动作。有一种更好的方法可以改进它。只要让计算机重复这个步骤N次。现在，在算法图形表示中就包括了这个特性，如图11-2所示。,图11-2 最大值算法的泛化,11.1.3 三种结构,20世纪70年代，E. Dijkstra首先提出了结构化程序设计 (
8、Structured Programming，SP) 方法，主张只用顺序、选择和重复三种基本控制结构来嵌套连接成具有复杂层次的“结构化程序”，每种基本控制结构只有一个入口和一个出口，并完成单一的操作。 在顺序结构中，算法 (最终是程序) 都是指令的序列，指令可以是简单指令或是其他两种结构之一。,11.1.3 三种结构,有些问题只用顺序结构是不能够解决的，需要检测条件是否满足。假如测试的结果为真，即条件满足，则可以继续顺序执行指令；假如结果为假，即条件不满足，程序将从另外一个指令序列继续执行。这就是所谓的选择 (判断) 结构。 在有些问题中，相同的一系列顺序指令需要重复，那么就可以用循环结构来解
9、决这个问题。从指定的数据集中找出最大数的算法就是这种结构的例子。,11.1.3 三种结构,已经证实其他结构都是不必要的，仅仅使用这三种结构就可以使程序或算法容易理解、调试或修改，如图11-3所示。,图11-3 顺序、判断、循环结构,11.1.4 算法的框图表示,框图 (又称“流程图”) 是算法的图形表示方法之一，它使用图的形式掩盖了算法的细节，只显示算法从开始到结束的整个流程。三种结构的框图表示如图11-4所示。,图11-4 三种结构的框图表示,11.1.5 算法的定义,下面，我们给出算法的正式定义：算法是一组明确步骤的有序集合，它产生结果并在有限的时间内终止。 解释如下。 1) 有序集合。算
10、法必须是一组定义完好且排列有序的指令集合。 2) 明确步骤。算法的每一步都必须有清晰明白的定义。如某一步是将两数相加，那么必须定义相加的两个数和加法运算，同一符号不能在某处用作加法符号，而在其他地方用作乘法符号。,11.1.5 算法的定义,3) 产生结果。算法必须产生结果，否则该算法就没有意义。结果集可以是被调用的算法返回的数据或其他效果 (例如打印) 。 4) 在有限的时间内终止。算法必须能够终止。如果不能 (例如，无限循环) ，说明不是算法。可解问题的解决方法为可终止的算法。,11.1.5 算法的定义,采用三种基本结构可以为任何可解的问题创建算法。结构化编程的原则要求把算法分成几个单元，我
11、们称之为子算法 (又称子程序、子例程、过程、函数、方法和模块等) 。每个子算法又分为更小的子算法。这个过程持续到子算法变为最本质的 (可被立即理解) 。 有一些算法在计算机科学中的应用非常普遍，称之为基本算法。例如，一些最常用的算法包括：求和、乘积、最大和最小、排序 (选择排序、冒泡排序、插入排序等) 和查找 (顺序查找和折半查找等) 。,11.2 编写计算机程序,问题描述和算法通常写在程序说明书 (例如详细设计说明书) 中，它们是程序设计必不可少的蓝图。完成程序说明书后，就可以编写程序了。编写程序就是用某种程序设计语言把算法程序化，编写程序的人称为程序员。对于大部分程序设计语言来说，编程就是
12、输入命令；有些程序设计语言只需要选择对象和属性或编写对象的脚本即可。,11.2.1 程序顺序,所谓顺序执行，就是计算机按照程序员指定的顺序执行每一条指令。第一条语句先执行，接下来是第二条，一直到程序末尾。图11-5中的流程图表述了一段小的顺序指令：1) 开始；2) 打印；3) 打印；4) 结束。,图11-5 顺序程序执行,11.2.1 程序顺序,一些算法给出的执行顺序和程序中写的不同，例如在某些情况下跳过一些指令或重复执行某些指令等。这里，控制结构控制着程序执行的顺序。一般有三种控制结构，即顺序控制、选择控制和循环控制。,11.2.2 顺序结构,顺序控制结构能改变计算机执行的顺序，使得在执行一
13、条指令之后转而执行其他的指令。 下面这段QBASIC程序中，使用GOTO语句告诉计算机直接跳往标号为“Widget”的语句执行。这样，语句“PRINT This is the second line. ”将永远不会被执行。 PRINT “This is the first line.” GOTO Widget PRINT “This is the second line.” Widget: PRINT “All Done!” END,11.2.2 顺序结构,图11-6表示的流程图说明了计算机先按标号顺序执行，然后在 GOTO语句的作用下跳往其他语句。虽然GOTO结构很简单，但过多的使用会使程序
14、的可读性和可维护性很差，所以熟练的程序员忌讳使用它。有经验的程序员喜欢用除GOTO语句以外的顺序控制结构，把程序改写成一个个的子程序、过程、模块或函数，这些都是程序的一段代码，但不包含在主程序的顺序路径内。,图11-6 执行GOTO语句,11.2.3 选择结构,选择控制结构也称为分支，用来告诉计算机根据所列条件的正确与否选择执行路径。比较简单的选择结构是IF.THEN.ELSE语句。,11.2.3 选择结构,下面这段程序使用IF. THEN. ELSE结构来判断输入的数字是否大于10。若大于10，打印“That number is greater than 10.”，否则，打印信息“That
15、number is greater than 10.”。 INPUT “Enter a number from 1 to 10:”, Number IF Number10 THEN PRINT “That number is greater than 10!” ELSE PRINT “That number is 10 or less.” END,11.2.3 选择结构,图11-7用流程图描述了计算机根据菱形框中的判断结果来选择执行路径。,图11-7 选择结构示例,11.2.4 重复结构,重复控制结构又称为循环结构，可以重复执行一条或多条指令直到满足退出条件为止。 在许多程序设计语言中，最常用
16、的循环结构是FORNEXT和WHILEWEND结构。下面的例子用FORNEXT结构打印一条信息三次。图11-8的流程图描述了计算机如何执行循环结构。 FOR N=1 TO 3 PRINT “Theres no place like home.” NEXT N END,图11-8 循环结构示例,11.3 测试和文档,在编制程序的同时应当编写文档，以记录和解释程序的工作过程。编程完成后，必须测试代码的每一段来确定其可以正确地工作。,11.3.1 测试程序,一个计算机程序必须对其进行测试以保证程序能正确工作。测试通常是输入测试数据来看看程序是否能够产生正确结果。如果没有产生正确结果，程序员必须查找程序中的错误，修改错误，再测试程序。这个过程可能需要相当长的时间，但是，测试是程序设计中的关键步骤。,11.3.1 测试程序,在程序中发现的错误可能是语法错误，也可能是运行时的错误。语法错误是由于指令没有按照程序设计语言的语法规则编写所致；运行时错误是指程
