《新编计算机文化基础》09 程序设计基础

第9章程序设计基础124339.1程序与程序设计语言9.2算法9.3结构化程序设计9.4面向对象程序设

9.1程序与程序设计语言9.1.1程序概述如果我们需要计算机完成某种工作，如何告诉计算机我们希望它做什么，怎么做？因为计算机是按照计算机指令执行规定的操作，所以，首先按特定顺序安排若干条计算机指令，以描述解决问题的运算步骤，并把这些指令存放在计算机的内存中，然后向计算机发出执行命令。计算机就会按顺序自动逐条执行这些指令所规定的操作，从而得到预期的结果。这种可以被连续执行的一条条指令的集合称为计算机的程序。计算机程序是供计算机执行并完成特定功能的有序指令集合。编制程序的工作就是为计算机安排指令序列。著名计算机科学家沃思（ＮｉｋｌａｕｓＷｉｒｔｈ）提出了关于程序的公式：下一页返回9.1程序与程序设计语言程序＝数据结构＋算法程序中包含与问题相关的数据结构和解决该问题的算法的描述。算法指定操作的具体步骤，而数据结构指定适合问题求解的数据组成形式（如数据类型）。例如，计算半径为狉的圆面积的程序应包括：（１）算法（计算步骤）：①输入半径r的值；②按公式s＝πr２计算圆面积s；③输出圆面积s。（２）数据结构：半径狉和圆面积s采用实型数。上一页下一页返回9.1程序与程序设计语言9.1.2程序设计人与计算机交流的语言称为计算机语言。程序用计算机语言描述待解问题的数据和处理该问题的方法和步骤。这个描述的过程就称为程序设计。因此，计算机语言通常被称为“程序设计语言”。对于程序设计的初学者来说，首先要学会设计一个正确的程序。正确的程序是指符合程序设计语言的语法，且对正确的输入，程序能产生所期望的输出。编制出正确的程序是程序设计的最低要求。一个“好”的程序，除正确性以外，程序还应具有良好的结构、可读性好、可靠性高、便于维护等特点。为此，应采用良好的程序设计方法，才能保证程序具有这些好特性，同时也要借助高效的开发环境（语言、工具）提高程序设计的效率。上一页下一页返回9.1程序与程序设计语言9.1.3程序设计语言程序设计语言的发展经历了机器语言、汇编语言和高级语言３个阶段。其中依赖于特定计算机的机器语言和汇编语言称为低级语言，低级语言难学、难记、编程效率低，只适合专业人员使用。而高级语言独立于具体计算机，易学、易用、编程效率高，便于非专业人员使用，高级语言为计算机普及和应用起了积极推动作用。１．机器语言上一页下一页返回9.1程序与程序设计语言人们最初用计算机指令形式告诉计算机要执行的操作，因此，计算机指令就是计算机语言，称为机器语言。计算机能直接识别机器语言并执行。机器语言与计算机同时诞生，用“０”和“１”的二进制代码组合表示计算机指令，不同的计算机具有不同的计算机指令系统。用机器语言编写程序，必须了解计算机的内部结构，而且可读性差，难识别，不便记忆，读写困难，编程效率极低。例如，计算６＋８，若累加器Ａ中有数６，则指令：

11000110

00001000表示将８与累加器Ａ中的６相加，结果仍放在累加器Ａ中。２．汇上一页下一页返回9.1程序与程序设计语言２．汇编语言为了克服机器语言的缺陷，人们研制出汇编语言，它采用英文缩写符号来表示计算机指令，比二进制形式的计算机指令更容易识别和记忆。例如计算６＋８的机器指令可以用如下汇编语言的语句表示：

ADD

A，8汇编语言的实质和机器语言基本相同，汇编语言的大部分语句仍然与机器指令一一对应。用汇编语言编写程序，必须熟悉计算机系统的内部结构，如累加器、寄存器等。而且与机器语言一样，汇编语言也是针对特定的计算机或计算机系统设计的，对计算机依赖性很强，是面向计算机的语言。上一页下一页返回9.1程序与程序设计语言由于计算机只能识别机器语言，因此，用汇编语言编写的程序文件必须翻译成机器语言的目标文件，并用连接程序将其转换成可执行文件后才能执行。完成自动翻译的程序称为汇编程序，翻译的过程称为汇编，如图９-１所示。汇编语言在识别和记忆方面比机器语言前进了一步，但编写较大程序时仍很繁琐。于是人们又研制出简单、易学、易掌握的高级语言。３．高级语言高级语言采用类似自然语言和数学表达式的形式描述问题的数据和处理过程。例如，计算６＋８，用高级语言可以写成：ａ＝６＋８；上一页下一页返回9.1程序与程序设计语言显然，与机器语言和汇编语言相比，高级语言简单、易学、易理解、易掌握。１９５４年，ＩＢＭ公司的巴科思（Ｊ．Ｂａｃｋｕｓ）设计出第一个高级语言Ｆｏｒｔｒａｎ（ＦＯＲｍｕｌａＴＲＡＮｓｌａｔｏｒ）语言，主要用于科学计算。巴科思因此获得１９７７年度的“图灵奖”。２０世纪６０年代中期，美国达特默斯学院的凯梅尼门（Ｊ．Ｋｅｍｅｎｙ）和卡茨（Ｔ．Ｋｕｒｔｚ）认为应当提供一种更简单的语言，以便非计算机专业的学生也能通过这种语言学会使用计算机。于是，他们对Ｆｏｒｔｒａｎ语言进行简化，研制出适合初学者使用的Ｂａｓｉｃ语言（Ｂｅｇｉｎｎｅｒ’ｓａｌｌｐｕｒｐｏｓｅＳｙｍｂｏｌｉｃＩｎｔｒｕｃｔｉｏｎＣｏｄｅ），Ｂａｓｉｃ语言很快成为最流行的语言之一。上一页下一页返回9.1程序与程序设计语言１９７１年，著名计算机科学家沃思（ＮｉｋｌａｕｓＷｉｒｔｈ）发明了Ｐａｓｃａｌ语言，它语法严谨，层次分明，可读性好，是第一个结构化程序设计语言。最初用于帮助学生学习计算机编程，也可以用来开发应用软件。沃思还写作了大量有关程序设计、算法和数据结构的著作，并获得１９８４年度的“图灵奖”。著名的Ｃ语言由美国贝尔实验室的李奇（Ｄ．Ｒｉｔｃｈｉｅ）和汤姆森（Ｋ．Ｔｈｏｍｐｓｏｎ）于１９７２年共同发明的。他们在开发著名的ＵＮＩＸ操作系统过程中，感觉汇编语言开发效率太低，高级语言虽好，但不具备开发系统软件的功能。于是结合汇编语言和高级语言的优点发明了Ｃ语言，并用Ｃ语言改写ＵＮＩＸ。上一页下一页返回9.1程序与程序设计语言由于Ｃ语言兼具低级语言和高级语言的优点，成为软件工程师最宠爱的语言之一。李奇和汤姆森因此获得１９８３年度的“图灵奖”。１９８３年，美国贝尔实验室的斯楚士舒普（Ｂ．Ｓｔｕｏｕｓｔｒｕｐ）把Ｃ语言扩展成面向对象的程序设计语言Ｃ＋＋。１９９５年，《ＢＹＴＥ》杂志将他列为计算机工业２０个最有影响的人之一。高级语言只要求人们向计算机描述问题的求解过程，而不关心计算机的内部结构，所以把高级语言称为“面向过程语言”，它易读、易记，也便于修改和调试，大大提高了编制程序的效率。因为高级语言基于自然语言和数学表达式，易于被人们理解和接受，使非计算机专业人员也能轻松使用和交流，从而极大地推动了计算机的普及和应用。上一页下一页返回9.1程序与程序设计语言典型的面向过程语言有Ｂａｓｉｃ、Ｆｏｒｔｒａｎ、Ｃｏｂｏｌ、Ｃ、Ｐａｓｃａｌ等。用高级语言编写的程序称为源程序。由于计算机只能识别和执行机器语言程序，所以高级语言源程序文件也需要翻译成机器语言的目标文件。有两种翻译方式：即编译方式和解释方式。编译方式是利用事先编好的编译程序将源程序文件自动翻译成机器语言的目标文件，并通过连接程序生成可执行文件。解释方式则对源程序逐句地边翻译边执行。编译方式将源程序整个翻译成目标程序，目标程序效率较高，一旦形成可执行文件，以后不需要再翻译，可反复执行。编译是高级语言实现的主要方式，如Ｃ、Ｆｏｒｔｒａｎ、Ｐａｓｃａｌ等均采用编译方式。编译方式如图９-２所示。上一页下一页返回9.1程序与程序设计语言解释方式是翻译一句执行一句，速度较慢，再次执行时还需要重新翻译。但解释方式也有好处，例如可以随时调试源程序并执行，而编译方式下源程序一旦修改，必须重新编译、连接后才能执行。早期的Ｂａｓｉｃ语言采用解释执行方式。解释方式如图９-３所示。随着计算机技术的迅猛发展，应用软件的规模持续高速增长，由此引起的复杂性用“面向过程”的方法已难于解决。于是出现了非过程语言，使用这种语言，不必描述处理过程，只要说明工作目标和条件，就能得到所要的结果。面向过程的语言告诉计算机“怎么做”，而非过程语言则告诉计算机“做什么”。例如，关系数据库的ＳＱＬ语言可以在学生表（ｓｔｕｄｅｎｔ）中检索出满足指定条件（ｓｃｏｒｅ＜６０）的学生姓名和成绩（ｎａｍｅ，ｓｃｏｒｅ）：上一页下一页返回9.1程序与程序设计语言

SELECT

name，score

FROM

student

WHERE

score<60２０世纪８０年代出现了“面向对象的程序设计”（ｏｂｊｅｃｔｏｒｉｅｎｔｅｄｐｒｏｇｒａｍｍｉｎｇ，ＯＯＰ）方法。它认为我们所处的世界是由许多彼此相关并相互通信的实体组成，这些实体称为对象。对象具有自己的属性（数据）和操作方法，对象之间的通信产生消息。消息驱动对象进行操作，从而改变对象的某些属性。面向对象的程序设计就是通过对象之间的消息通信，驱动对象执行一系列操作，从而完成某种任务的程序设计。上一页下一页返回9.1程序与程序设计语言面向过程的程序设计采用过程（或函数）来描述对数据的操作过程，但数据和操作数据的过程却是分离的。而“面向对象”的思想则认为，过程及过程操作的数据关系密切、不可分割，特定的过程往往操作特定的数据，所以对象中包括数据及对该对象数据的操作，是两者的“封装”。通过“消息”来驱动运行封装在对象中的操作程序。例如，按钮就是一个对象，它本身含有数据及操作，通过鼠标单击它传递消息，使按钮对象执行它所包含的特定操作。面向对象的程序设计语言主要有ＢｏｒｌａｎｄＣ＋＋、Ｖｉｓｕａｌ＋＋、ＶｉｓｕａｌＢａｓｉｃ等。上一页下一页返回9.1程序与程序设计语言9.1.4程序设计步骤初学者往往把程序设计理解成只是编写程序，这是不全面的。程序设计反映了利用计算机解决问题的全过程，编写程序只是其中一个方面。如何进行程序设计呢？下面是一般程序设计包含的４个步骤。（１）分析问题，建立数学模型。使用计算机解决具体问题时，首先要对问题进行充分的分析，确定问题的要求。针对所要解决的问题，找出已知的数据和条件，确定所需的输入、处理及输出对象，并用数学语言描述出来，即建立解决问题的数学模型。需要注意的是，有许多问题的数学模型是显然的或者简单的，以至于我们没有感觉到需要模型。但是有更多的问题需要靠分析问题来构造计算模型，模型的好与坏、对与错，在很大程度上决定了程序的正确性和复杂程度。上一页下一页返回9.1程序与程序设计语言（２）确定数据结构和算法。数学模型的建立，明确了“做什么”，接着要解决的是“怎么做”。根据建立的数学模型，对指定的输入数据和预期的输出结果，确定存放数据的数据结构。针对所建立的数学模型和确定的数据结构，选择合适的算法加以实现。这里的“合适的算法”是指正确而高效的算法。同一问题也许存在不同的算法，但不同算法的效率也不同，应选择高效算法。注意，这里所说的“算法”泛指解决某一问题的方法和步骤，而不仅仅是指“计算”。（３）编制程序。因为我们要利用计算机解决问题，所以必须告诉计算机“怎么做”。根据确定的数据结构和算法，选择合适的程序设计语言把这个解决方案正确地描述出来，也就是编写出程序代码，以便计算机执行程序，解决问题。上一页下一页返回9.1程序与程序设计语言（４）调试程序。编写的程序不一定完全符合实际问题的要求，通常情况下还存在这样那样的错误。因此，必须在计算机上用实际的输入数据运行该程序，以测试程序，并不断排除程序中出现的错误，才能得到正确的结果。这个过程称为调试。调试中，对所得到的运行结果进行分析，如果有错，应判断可能的错误及其位置，并对程序进行修改和调整，然后再一次上机调试，直至获得预期的结果。由此可见，一个完整的程序要涉及４个方面的问题：数据结构、算法、编程语言和程序设计方法。这４个方面的知识都是程序设计人员所必须具备的，其中算法是至关重要的一个方面。上一页下一页返回9.1程序与程序设计语言9.1.5程序设计的风格计算机程序除了要求具有正确性，能够在计算机上正确执行，还必须便于阅读和理解，这就要求在编写程序时，应当遵循一定的编程原则，养成良好的程序设计习惯，形成自己的编程风格。好的编程风格有助于提高程序的正确性、可读性和可维护性。要使程序具有良好的风格，概括起来可以分为４个部分：源程序文档化、数据说明、语句结构、输入输出的设计。１．源程序文档化源程序文档化主要是指以下几个方面：标识符命名、规范化注释以及程序的视觉组织等。上一页下一页返回9.1程序与程序设计语言１）标识符命名标识符即符号名，包括变量名、模块名、常量名、标号名、函数名、数据区名和缓冲区名等。由于程序中可能存在众多的标识名，特别是大型的程序，如果不加以规范化的话，很容易因为命名的混乱而降低程序的可读性。以下是标识符命名的几个基本原则：（１）标识符的命名要清晰、明了，有明确含义，同时使用完整的单词或大家基本可以理解的缩写，避免使人产生误解。较短的单词可通过去掉“元音”形成缩写；较长的单词可取单词的头几个字母形成缩写；一些单词有大家公认的缩写。如下单词的缩写能够被大家基本认可。上一页下一页返回9.1程序与程序设计语言ｔｅｍｐ可缩写为ｔｍｐ；ｆｌａｇ可缩写为ｆｌｇ；ｓｔａｔｉｓｔｉｃ可缩写为ｓｔａｔ；ｉｎｃｒｅｍｅｎｔ可缩写为ｉｎｃ；ｍｅｓｓａｇｅ可缩写为ｍｓｇ。（２）对于变量命名，禁止取单个字符（如ｉ、ｊ、ｋ…），建议除了要有具体含义外，还能表明其变量类型、数据类型等，但ｉ、ｊ、ｋ作局部循环变量是允许的。比如局部变量名ｉｎｔｌｉｖ＿Ｗｉｄｔｈ，其变量名解释如下：上一页下一页返回9.1程序与程序设计语言ｌ局部变量（Ｌｏｃａｌ）（其他：ｇ全局变量（Ｇｌｏｂａｌ）…）ｉ数据类型（Ｉｎｔｅｒｇｅｒ）ｖ变量（Ｖａｒｉａｂｌｅ）（其他：ｃ常量（Ｃｏｎｓｔ）…）Ｗｉｄｔｈ变量含义这样可以防止局部变量与全局变量重名。（３）自己特有的命名风格，要自始至终保持一致，不可来回变化。（４）在同一软件产品内，应规划好接口部分标识符（变量、结构、函数及常量）的命名，防止编译、链接时产生冲突。２）规范化注释上一页下一页返回9.1程序与程序设计语言注释是程序员与程序读者之间交流通信的重要工具，用自然语言或伪代码描述。它用于辅助说明程序的功能，对理解程序提供了明确指导。编写注释的基本原则是有助于对程序的阅读理解，在该加的地方都加了，注释不宜太多也不能太少，注释语言必须准确、易懂、简洁。注释分为序言性注释和功能性注释。序言性注释一般用于每个程序段的开头部分，给出程序的整体说明，用来引导读者理解程序，主要包括说明文件头、源文件头和函数头。功能性注释一般置于程序体中，用于描述其后的语句或程序段的功能。编写规范化的注释常有以下几个原则：上一页下一页返回9.1程序与程序设计语言（１）说明性文件（如头文件．ｈ文件、．ｉｎｃ文件、．ｄｅｆ文件、编译说明文件．ｃｆｇ等）头部应进行注释，注释必须列出：版权说明、版本号、生成日期、作者、内容、功能、与其他文件的关系、修改日志等，头文件的注释中还应有函数功能简要说明。（２）源文件头部应进行注释，列出：版权说明、版本号、生成日期、作者、模块目的／功能、主要函数及其功能、修改日志等。（３）函数头部应进行注释，列出：函数的目的／功能、输入参数、输出参数、返回值、调用关系（函数、表）等。（４）一般情况下，源程序有效注释量必须在２０％以上。一行程序以小于８０个字符为宜，不要写得过长。注释与所描述内容进行同样的缩排。上一页下一页返回9.1程序与程序设计语言３）程序的视觉组织对程序的排版进行合理编辑，形成一目了然的视觉效果，可以使程序层次清晰，便于理解。可以按照以下的几个原则来编辑程序。（１）采用松散方式编写代码，其目的是使代码更加清晰。（２）可采用留空格的方式增强代码的可读性，但它所产生的清晰性是相对的，所以，在已经非常清晰的语句中没有必要再留空格，如果语句已足够清晰则括号内侧（即左括号后面和右括号前面）不需要加空格，多重括号间不必加空格，因为在Ｃ／Ｃ＋＋语言中括号已经是最清晰的标志了。（３）在长语句中，如果需要加的空格非常多，那么应该保持整体清晰，而在局部不加空格。给操作符留空格时不要连续留两个以上空格。上一页下一页返回9.1程序与程序设计语言（４）注意运算符的优先级，并用括号明确表达式的操作顺序，避免使用默认优先级。（５）源程序中关系较为紧密的代码应尽可能相邻。２．数据说明任何软件都是对数据进行处理，为此，软件设计者就必须很好地组织待处理的数据。为了使程序中数据说明更易于理解和维护，必须注意以下几点。（１）数据说明的次序应当规范化，使数据属性容易查找。通常来说，数据说明在次序上时可以随意，但是便于阅读和规范化，可以约定某种固定的次序，如按以下顺序说明：常量说明、类型说明、全程量说明和局部量说明等。上一页下一页返回9.1程序与程序设计语言（２）当在一个语句中说明多个变量时，应当对这些变量按字母的顺序排列。（３）对于复杂的数据结构，应当使用注释来说明在程序中使用时应注意的特点。３．语句结构在软件的设计阶段完成了软件逻辑结构的设计，但最终要实现则依靠单个语句，这是就是编码阶段的任务。语句构造力求简单，直接，不能为了片面追求效率而使语句复杂化，要做到清晰第一，效率第二。（１）在一行内只写一条语句，并且采取适当的移行格式，使程序的逻辑和功能变得更加明确。上一页下一页返回9.1程序与程序设计语言（２）程序编写首先应当考虑清晰性，不要刻意追求技巧性，使程序编写得过于紧凑。（３）尽可能使用库函数，避免使用临时变量而使可读性下降，使用括号来清晰地表达算术表达式和逻辑表达式的运算顺序。（４）避免不必要的转移，有限地使用ＧＯＴＯ语句；尽量只用３种基本的控制结构来编写程序；应避免过多的循环嵌套和条件嵌套。（５）尽可能用通俗易懂的伪码来描述程序的流程，然后再翻译成必须使用的语言。（６）代码应模块化，使模块功能尽可能单一化，模块间的耦合能够清晰可见；利用信息隐蔽，确保每一个模块的独立性。上一页下一页返回9.1程序与程序设计语言（７）经常将自己换位为代码阅读者，来衡量自己编写的代码是否能被别人看懂。４．输入和输出（Ｉ／Ｏ）输入和输出是用户与软件交互以及结果显示的重要方式，交互界面的设计应当尽可能人性化，符合用户的习惯，一个软件系统能否被用户接受，有时就取决于输入和输出的风格。因此，在软件需求分析阶段和设计阶段，就应基本确定输入和输出的风格，应当考虑下列原则。（１）应对输入数据进行有效性及其组合方式的检验，从而识别错误的输入，以保证每个数据的有效性上一页下一页返回9.1程序与程序设计语言（２）应使输入的步骤和操作尽可能简单，并保持简单的输入格式，应允许使用自由格式输入，应允许默认的默认值。（３）在以交互式输入／输出方式进行输入时，要在屏幕上使用提示符明确提示交互输入的请求，指明可使用选择项的种类和取值范围。同时，在数据输入的过程中和输入结束时，也要在屏幕上给出状态信息。（４）充分利用联机帮助手段，对于不熟练的用户，提供对话式服务，对于熟练的用户，提供较高级的系统服务，改善输入／输出的能力。（５）给所有的输出加注释，并设计输出报表格式。上一页返回9.2算法9.2.1算法概述１．算法的概念人们要做某件事，一般都按照一定的规则和步骤，一步一步地进行。例如，要考研究生，首先要决定报考的学校和专业，然后报名并缴纳相应的费用，拿到准考证。根据准考证上规定的时间和考场，按时赴考场参加考试。如果接到录取通知书，就可以按录取通知书上的规定到校报到并注册。这些步骤是按一定顺序进行的，次序不能颠倒，也不能随意省略某些步骤。下一页返回9.2算法任何解决问题的过程都是由一定的步骤组成的，为了解决问题而采用的方法和有限步骤称为算法。著名计算机科学家Ｄ．Ｅ．Ｋｎｕｔｈ在他撰写的《ＴｈｅＡｒｔｏｆＣｏｍｐｕｔｅｒＰｒｏｇｒａｍｍｉｎｇ》一书中写到：“一个算法，就是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。”简单地说，为解决问题而采取的方法和步骤就是算法。２．算法的特征算法是一个有穷规则的集合，这些规则确定了解决某类问题的一个运算序列。对于该类问题的任何初始输入值，它都能机械地一步一步地执行计算，经过有限步骤后终止计算并产生输出结果。归纳起来，算法具有以下基本特征。上一页下一页返回9.2算法（１）有穷性。一个算法必须在执行有限个操作步骤后终止，而且每一步都在有限时间内完成，不能无止境地执行下去。例如，计算圆周率π的公式为：π＝４（１－１／３＋１／５－１／７＋…）。公式中的项数是无穷的，必须设定条件（如结果精确到第６位），使之计算有限项后终止。（２）确定性。算法中每一步的含义必须是确切的，不可出现任何二义性。例如，“犖被一个整数除，得余数犚，犖被哪个整数除？”这样描述不确切。（３）有效性。算法中的每一步操作都能有效执行，一个不可执行的操作是无效的。例如，一个数被０除的操作就是无效的。上一页下一页返回9.2算法（４）有零个或多个输入。这里的输入是指在算法开始之前所需要的初始数据。输入的多少取决于特定的问题。例如，求１０个数中最大值的算法中必须输入这１０个数。而求解一元二次方程ax２＋bx＋c＝０根的算法中需要输入系数a、b、c。若将初始数据直接写入算法，则算法也可以没有输入。（５）有一个或多个输出。所谓输出是指与输入有某种特定关系的量，在一个完整的算法中至少会有一个输出。如求１００个数中最大值的算法中应输出最大值，求解一元二次方程的算法中应输出方程的根。没有输出的算法将毫无意义。上一页下一页返回9.2算法9.2.2评价算法的标准算法设计时只满足算法的基本特征是远远不够的，解决问题的算法可能有多个，但算法有优劣之分。高质量的算法才能产生高质量的程序，程序质量主要有以下标准。１．正确性对于一切合法的输入数据都能得出满足要求的正确结果。２．可读性算法应该具有良好的可读性，易理解，便于交流与维护。采用科学、规范的程序设计方法（如结构化方法）有助于提高算法的可读性。３．健壮性上一页下一页返回9.2算法算法的高效率通常是指算法执行速度快，运行时间短，且占用内存少。算法效率的度量包括时间度量与空间度量两个方面。１）时间度量算法执行时间大致等于计算机执行一种简单操作所需平均时间与算法中进行简单操作次数的乘积。因为计算机执行一种简单操作所需平均时间因计算机而异，与算法无关，所以只需讨论算法中进行简单操作次数即可。通常，将算法中进行简单操作次数的多少称为算法的时间复杂度。若问题规模为n，则算法的时间复杂度就是问题规模nn的函数f(n)，用Ｏ（f（n））表示算法的时间复杂度。如，计算n阶方阵犃各元素用如下公式计算：上一页下一页返回9.2算法aij＝i＋j（i＝１，２，…，n

j＝１，２，…，n）显然，共进行n２次加法操作，所以该算法的时间复杂度为Ｏ（n２）。它表示随问题规模n的增大，算法执行时间的增长率与n２的增长率相同。常见的算法时间复杂度有Ｏ（１）、Ｏ（ｌｏｇ２n）、Ｏ（n２）、Ｏ（n３）和Ｏ（２n）。２）空间度量一个算法的实现所占用的存储空间由如下３部分组成。（１）存储算法指令本身占用的空间（与算法长度有关）。（２）算法输入／输出占用的空间（与算法无关）。（３）执行算法时需要的临时空间（与算法有关）。上一页下一页返回9.2算法其中，执行算法时需要的临时空间是度量算法空间的主要因素，称为算法的空间复杂度。常见的空间复杂度有Ｏ（１）、Ｏ（ｌｏｇ２n）、Ｏ（n２）、Ｏ（n３）和Ｏ（２n）。空间复杂度与时间复杂度是相互矛盾的，降低算法执行时间要以增加空间为代价，要减少空间就可能增加执行的时间，只能根据实际情况有所侧重。高效率与可读性也是矛盾的。早期计算机硬件水平较低时，不得不考虑微小的内存和缓慢的速度，算法往往优先保证在小内存情况下复杂问题的求解，因此效率优先于可读性。目前在计算机运行速度快、内存大的情况下，应首先保证算法的可读性，效率已经处于次要地位。上一页下一页返回9.2算法9.2.3算法的表示原则上说，算法可以用任何形式的语言和符号来描述，通常有自然语言、程序语言、流程图、Ｎ-Ｓ流程图、伪代码等。流程图、Ｎ-Ｓ流程图是表示算法的形工具，其中，流程图是最早提出的用图形表示算法的工具，所以也称为传统流程图。它具有直观性强、便于阅读等特点，具有程序无法取代的作用。Ｎ-Ｓ流程图克服了传统流程图的不足，符合结构化程序设计要求，是软件工程中强调使用的图形工具。用流程图等图形工具描述的算法必须用合适的程序设计语言转换成程序。自然语言、程序语言和伪代码直接使用语言工具描述算法。用自然语言描述算法容易产生模糊和二义性，一般不宜采用。上一页下一页返回9.2算法程序语言不宜直接描述复杂的算法，一般先用图形工具描述，再用程序语言转换成程序。伪代码用英语和类程序语言混合描述算法，优点是便于转换成程序。因为流程图便于交流，又特别适合于初学者使用，对于一个程序设计工作者来说，会看会用流程图是完全必要的。１．用自然语言描述算法用自然语言描述算法通俗易懂，但描述不简洁，含义不严谨，容易产生模糊和二义性，一般不宜采用。例如，在“老张告诉老李他的孩子考上了大学”的描述中，考上大学的究竟是老张的孩子还是老李的孩子？难以判断。上一页下一页返回9.2算法２．用流程图描述算法用图形表示事物往往直观形象，容易理解和接受。流程图就是用规定的一系列图形、流程线和文字来说明算法中的基本操作和控制流程。常用的有传统流程图和Ｎ-Ｓ流程图。（１）传统的流程图。传统的流程图又称为框图，用它表示算法的优点是形象直观、简单易懂、便于交流。美国国家标准化协会ＡＮＳＩ（ＡｍｅｒｉｃａｎＮａｔｉｏｎａｌＳｔａｎｄａｒｄＩｎｓｔｉｔｕｔｅ）规定了一些常用的符号，表９-１中分别列出了标准的流程符号的名称、符号表示和功能。这些符号已被世界各国的广大程序设计工作者普遍接受和采用。上一页下一页返回9.2算法①起止框：用于表示算法的开始或结束。每个算法流程图中必须有且仅有一个开始框和一个结束框，开始框只能有一个出口，没有入口，结束框只有一个入口，没有出口，其用法如图９-４（ａ）所示。②输入／输出框：表示算法的输入和输出操作。输入操作是指从输入设备上将算法所需要的数据传递给指定的内存变量；输出操作则是将存放在内存中的计算结果传递到输出设备上。输入／输出框中填写需输入或输出的各项列表，它们可以是一项或多项，多项之间用逗号分隔。输入／输出框只能有一个入口，一个出口，其用法如图９-４（ｂ）所示。上一页下一页返回9.2算法③处理框：算法中各种计算和赋值的操作均用处理框表示。处理框内填写处理说明或具体的算式。也可在一个处理框内描述多个相关的处理。但是一个处理框只能有一个入口，一个出口，其用法如图９-５（ａ）所示。④判断框：表示算法中的条件判断操作。判断框说明算法中产生了分支，需要根据所给条件的成立与否来确定下一步的执行路线。判断框内填写判断条件，一般用关系比较运算或逻辑运算来表示。判断框一般有一个入口和两个出口，这两个出口分别表示条件成立和条件不成立时的执行路线。其用法如图９-５（ｂ）所示。上一页下一页返回9.2算法⑤注释框：表示对算法中的某一操作或某一部分操作所作的必要的说明。这是专为作者或读者准备的对操作或计算公式的备注说明，以增加可读性。因为它不反映流程和操作，所以不是流程图中必要的部分。注释框没有入口和出口，框内一般是简明扼要的注释文字。其用法如图９-６所示。⑥流程线：表示算法的走向，流程线箭头的方向就是算法执行的方向。事实上，这条简单的流程线是很灵活的，它可以到达流程的任意处。然而，这种无限制的任意转向是有害的，因为它容易使软件的可读性、可维护性降低。所以在Ｎ-Ｓ图形工具中取消了流程线。上一页下一页返回9.2算法但是对于程序设计的初学者来说，传统流程图有其显著的优点，流程线非常明确地表示了算法的执行方向，便于读者对程序控制结构的学习和理解。⑦连接点：表示不同地方的流程图的连接。有时较复杂算法的流程图必须在多个页面上才能表达，两个页面之间算法的连接关系可以用连接点表达。例９-１求给定半径犚的圆面积和圆周长。算法：①输入圆半径犚；②根据圆面积公式：S＝πR２计算圆面积S；上一页下一页返回9.2算法③根据圆周长公式：L＝２πR计算圆周长L；④输出圆面积S和圆周长L。表示该算法的流程图如图９-６所示。（２）３种基本结构。传统流程图用流程线表示算法的执行顺序，然而并没有对流程线加以限制，以至流程可以随意地转到任何地方，甚至大幅度地转来转去，使流程图结构杂乱无章。人们花了很大精力去追踪跳来跳去的流程，仍不得要领，难以理解。随意转移的流程线降低了可读性，不利于交流和维护。为了提高算法的质量，人们设想算法结构中限制流程的任意转向，甚至禁止使用流程线，使算法总是顺序执行。考虑到算法中难免出现判断选择和循环执行的非顺序结构。上一页下一页返回9.2算法１９６６年，Ｂｏｈｍ和Ｊａｃｏｐｉｎｉ提出了３种基本结构，即顺序结构、选择结构和循环结构，并证明任何简单或复杂的算法都可以由顺序结构、选择结构和循环结构这３种基本结构组合而成。３种基本结构就像积木，可以用它们搭建成任何复杂的顺序执行的算法结构。顺序结构是最简单的结构，顺序结构中的操作按顺序依次进行。如图９-７所示，Ｓ１和Ｓ２分别代表某个或某些操作，先执行Ｓ１然后执行Ｓ２。整个顺序结构只有一个入口点ａ和一个出口点ｂ。这种结构的特点是：从入口点ａ开始，顺序执行所有操作，直到出口点ｂ处，所以称为顺序结构。如图９-６所示的算法就是由顺序结构组成的。上一页下一页返回9.2算法选择结构又称为分支结构。结构中要通过判断给定条件的成立或不成立来决定执行何种操作。选择结构有单选择结构和双选择结构两种。如图９-８所示的是单选择结构，当条件成立时（标注Ｙ的分支），执行引操作，然后退出选择结构；当条件不成立时（标注Ｎ的分支不执行任何操作，直接退出选择结构）。如图９-９所示的是双选择结构，当条件成立时，执行引操作，然后退出选择结构。否则执行Ｓ２操作后退出选择结构。注意：无论条件是否成立，只能执行Ｓ１或Ｓ２操作之一，而且均通过ｂ点退出选择结构。上一页下一页返回9.2算法循环结构也称为重复结构。在循环结构中，当满足给定条件时重复执行某些操作，不满行的部分称为循环体。循环结构又分为当型循环和直到型循环两种。如图９-１０（ａ）所示的是当型循环结构。首先判断条件是否成立，若成立，则执行循环体Ｓ然后再判断条件，若仍然成立，再执行循环体Ｓ。如此反复执行循环体Ｓ，直到循环控制条件不成立时退出循环。足给定条件时，退出循环结构。给定条件称为循环控制条件，重复执循环体Ｓ，直到循环控制条件不成立时退出循环。上一页下一页返回9.2算法如图９-１０（ｂ）所示的是直到型循环结构。与当型循环结构不同，它首先执行循环体Ｓ，然后再根据条件决定是重复执行循环体Ｓ或退出循环。若条件不成立，再执行循环体Ｓ，如此反复执行循环体Ｓ，直到条件成立时退出循环。以上３种基本结构都具有唯一入口和唯一出口，结构内不存在永远不能执行的操作，也不会出现无终止的“死循环”。单入口和单出口使基本结构之间形成顺序执行关系，相互之间接口关系简单，结构清晰，不存在无规律的转向。由３种基本结构组成的算法是“结构化”的算法，它可以表示任何复杂的算法结构。下面就３种基本结构算法分别举例说明。上一页下一页返回9.2算法例９-２一个酱油瓶中错装了醋，另一醋瓶中错装了酱油，如何恢复酱油瓶装酱油且醋瓶装醋？设酱油瓶为x，醋瓶为y，另增加一个空瓶并设为k。恢复酱油瓶装酱油且醋瓶装醋就是实现x、y小瓶内容的互换。怎样才能实现x、y小瓶内容的互换？若用x→y和y→x实现，则达不到目的。因为执行x→y后小瓶的内容（酱油）已经丢失，由x瓶的内容（醋）取而代之。再执行y→x时，装入x瓶的不是y瓶原来的内容（酱油），而是y瓶的新内容（醋），所以，执行后x、y的内容均为醋。上一页下一页返回9.2算法失败的原因在于执行x→y时y瓶内容的丢失。因此，应该先把y瓶的内容保存在k瓶中，即y→k，执行x→y时，虽然y瓶的内容被x瓶的内容取代，但y瓶的内容事先已经保存在k瓶中，所以用k→x就可以把原y瓶的内容赋给x瓶。从而实现x小瓶内容的互换。算法流程如图９-１１所示，这是典型的顺序结构算法，按算法步骤顺序执行即可。例９-３求给定整数的绝对值。求x绝对值的算法很简单，若x≥０，则x即为所求；若x＜０，则－x为x的绝对值。因此，算法中要通过条件判断才能决定执行何种操作获得给定整数的绝对值。显然，这是选择结构算法。算法流程如图９-１２所示。上一页下一页返回9.2算法算法中用y表示x的绝对值。首先输入整数x的值，判断x是否小于０，若x＜０，则x的绝对值为－x，将－x赋给y。若x≥０，则x的绝对值就是x本身，将x赋给y。然后输出结果x及x的绝对值y。例９-４求s＝１＋２＋３＋…＋n求１＋２＋３＋…＋n可以采用两种算法（以n＝６为例）：方法一：１＋２＋３＋４＋５＋６→s方法二：s→０s＋１→ss＋２→ss＋３→ss＋４→s上一页下一页返回9.2算法s＋５→ss＋６→s第一种方法虽然简单明了，但有明显不足。当n很大时，把n个数依次写在算式中是不现实的。第二种方法中，累加是分开执行的，可以将累加过程归纳为如下算法。①输入n的值；②０→s，１→k；③s＋k→s，k＋１→k；④若k≤n则转③，否则转⑤；⑤输出结果s。上一页下一页返回9.2算法算法中，在满足k≤n的情况下，操作s＋k→s是反复执行的，因此，可用循环结构实现该算法，无论n是多少，算法过程不变。从而解决n很大的求和问题。具体算法的流程如图９-１３所示。（３）Ｎ-Ｓ流程图。结构化程序设计方法主张自顶向下、逐步求精和模块化设计。Ｎ-Ｓ流程图就是结构化程序设计方法中用于表示算法的图形工具之一。传统流程图由于任意转向的流程线而无法保证自顶向下的设计方法，也使模块之间的调用关系难以表达。为此，两位美国学者Ｎａｓｓｉ和Ｓｈｎｅｉｄｅｒｍａｎ于１９７３年提出了一种新的流程图形式，并用他们名字的第一个字母命名，即Ｎ-Ｓ流程图。上一页下一页返回9.2算法Ｎ-Ｓ流程图的基本单元是矩形框，它只有一个入口和一个出口，并且完全去掉了带有方向的流程线。顺序结构、选择结构和循环结构分别用３种不同的矩形框表示，将这些矩形框进行组装就可表示全部算法。这种流程图从表达形式上就排除了使用随意转向的可能性，限制了不良程序结构的产生。与图９-７对应的顺序结构Ｎ-Ｓ流程图如图９-１４所示，按顺序先执行Ｓ１操作，再执行Ｓ２操作。上一页下一页返回9.2算法与图９-８对应的单选择结构Ｎ-Ｓ流程图如图９-１５（ａ）所示，当条件成立时（即条件为“Ｙ”），执行Ｓ１操作，否则（即条件为“Ｎ”）什么也不做。而与图９-９对应的双选择结构Ｎ-Ｓ流程图如图９-９所示，当条件成立时，执行Ｓ１操作，否则执行Ｓ２操作。与图９-１０（ａ）对应的当型循环结构Ｎ-Ｓ流程图如图９-１６（ａ）所示，当条件成立时反复执行循环体Ｓ，直到条件不成立时为止并退出循环。而与图９-１０（ｂ）对应的直到型循环结构Ｎ-Ｓ流程图如图９-１６（ｂ）所示，首先做循环体Ｓ，然后判断条件，条件不成立时反复做循环体Ｓ，直到条件成立为止并退出循环。上一页下一页返回9.2算法在Ｎ-Ｓ流程图中，流程总是从矩形框的上面开始，一直执行到矩形框的下面，这就是流程的入口和出口。这种形式使流程只能自上而下、顺序执行，不可能出现随意转向。在３种基本结构Ｎ-Ｓ流程图中的Ｓ、Ｓ１、Ｓ２框可以是简单的操作，也可以是３个基本结构之一，即基本结构中可以嵌套另一基本结构。图９-１７为求１０个数中最小值算法的Ｎ-Ｓ流程图，在循环结构的循环体中，嵌套了选择结构（“x＜ｍｉｎ？”）和顺序结构（“输入x”，“j＋１→j”）在图９-１７和图９-１８中分别给出了求１０个数中最小值算法的Ｎ-Ｓ流程图和传统流程图。对比之下可以看到，用Ｎ-Ｓ流程图表示算法，比用文字描述更直观、形象、易于理解；比传统流程图紧凑易画；上一页下一页返回9.2算法更重要的是Ｎ-Ｓ流程图完全取消了流程线，无法随意转向，整个算法结构是由各基本结构按顺序构成，执行的顺序与Ｎ-Ｓ流程图的上下顺序一致。符合结构化程序设计方法的“自顶向下，逐步求精”的思想。大大方便了结构化程序的设计，有效提高了算法设计的质量和效率。Ｎ-Ｓ流程图是表达结构化算法的重要图形工具之一。３．伪代码传统流程图或Ｎ-Ｓ流程图均为描述算法的图形工具，其优点是直观、易懂，但图形绘制比较费时费事。设计算法时，免不了反复修改，而修改图形也十分麻烦。因此流程图适合表示算法，但设计算法过程中，由于需要反复修改，使用流程图并不理想。为了克服流程图的缺点，出现一种称之为伪代码的算法表示工具。上一页下一页返回9.2算法伪代码是介于自然语言和计算机语言之间的算法描述工具。它采用文字和符号来描述算法，按算法步骤一行一行、自上而下地描述算法。由于不涉及图形，因此，书写方便，格式紧凑，修改容易，而且由于伪代码类似计算机语言，使之便于转换成计算机语言程序。用伪代码描述算法，并无固定的、严格的格式或规则，重要的是表达清楚和易读易懂。文字部分既可以采用英语也可以采用汉语。用伪代码描述算法的一般结构如下。算法开始：ｂｅｇｉｎ算法组成：赋值ｊ＋１→ｊ输入ｉｎｐｕｔｘ输出ｐｒｉｎｔｘ上一页下一页返回9.2算法双选择ｉｆ（条件）ｔｈｅｎＳ１ｅｌｓｅ（条件）Ｓ２ｅｎｄｉｆ单选择ｉｆ（条件）ｔｈｅｎＳ１ｅｎｄｉｆ循环ｗｈｉｌｅ（循环条件）｛循环体｝ｅｎｄｗｈｉｌｅ算法结束：ｅｎｄ例９-５用伪代码描述求最小值的算法。

begin（算法开始）上一页下一页返回9.2算法

input

x

x→min

2→j

while(j≤10)

{

inputx（或：输入x）if(x<min)

thenx→minendifj+1→j

}

endwhile

上一页下一页返回9.2算法print

min（或：输出min）在本算法中采用当型循环，ｗｈｉｌｅ（j≤１０）表示当j≤１０时反复执行循环体（即｛｝中的操作），ｅｎｄｗｈｉｌｅ表示循环结束。循环体中有单选择结构，“ｉｆ（x＜ｍｉｎ）ｔｈｅｎx→ｍｉｎ”表示“如果x＜ｍｉｎ，则执行x→ｍｉｎ操作（即将x值赋给ｍｉｎ）”，ｅｎｄｉｆ表示选择结构的结束。由于伪代码中采用了类似高级程序设计语言的表达方法，所以伪代码表示的算法很容易转换成计算机语言程序。例如，上例伪代码表示的求最小值算法可以方便地转换为下列Ｃ语言程序。上一页下一页返回9.2算法

main()

{

intx，j，min；

scanf("%d"，&x)；/*input

x**/

min=x；/*x→min

*/

j=2；/*2→j*/

while(j<=10)/while(j≤10)/

{

scanf("%d"，&x)；/*inputx

*/

if(x<min)/*if(x<min)thenx→min*/上一页下一页返回9.2算法

{

min=x；

}

j=j+1；/*j+1→j*/

}/*endwhile

*/

printf("min=%d\n"，min)；/printmin

/

}其中，／*和*／之间的内容是程序语句对应的伪代码表示，对比之下，可以发现程序设计语言表示的算法与伪代码表示的算法在形式上非常相似，这就是为什么伪代码容易转换成计算机语言程序的原因。上一页下一页返回9.2算法用伪代码表示算法，显然书写方便、格式紧凑、修改容易和便于转换成计算机语言程序，但也存在明显的缺点，例如，不直观，而且不易发现逻辑错误。４．计算机语言设计算法的目的是利用计算机解题，前面介绍的流程图、伪代码只能描述算法，它们描述的算法无法被计算机所识别。因此，这些工具描述的算法必须转换成计算机语言程序，才能在计算机上解题。上一页下一页返回9.2算法如果直接用计算机语言描述算法，就不必进行转换程序的工作。不过，用计算机语言描述算法，必须严格遵循该计算机语言的语法规则。对简单的算法，直接用计算机语言表示并不困难。然而，较复杂的算法却难于用计算机语言直接表达，这是因为计算机语言不直观，描述时容易产生逻辑错误，而且不易发现。所以，对较复杂的算法，可以先用流程图等直观图形工具描述算法，再转换为计算机语言程序。例９-６用Ｃ语言表达图９-６所示的求圆面积和圆周长的算法。上一页下一页返回9.2算法

main()

{

floatr，s，l，pai=3．14159；

scanf("%f"，&r)；

s=pai*r*r；

l=2*pai*r；

printf("s=%f，l=%f\n"，s，l)；上一页下一页返回9.2算法9.2.4常用算法这里只介绍几个常用典型算法．使读者了解一些解题的基本思想和方法，了解如何设计算法。在后续程序设计课程中。会进一步讨论算法的设计。１．穷举法穷举法的基本思想是，首先确定影响答案的因素，并预估这些因素变化的可能范围，然后在此范围内列举它们所有可能的搭配，并进行逐一验证，若某种搭配使验证符合题目的全部条件，则该搭配为本题的一个答案可能存在一个或多个答案。若全部验证结果均不符合题目的全部条件，则说明该题无答案。上一页下一页返回9.2算法为了列举所有可能的搭配可以采用多重循环结构实现。什么是多重循环，多重循环是指循环苏会结构即循环的循环体中又出现另一循环结构。图９-１９（ａ）是单循环结构在Ａ循环体中不包含另一循环结构。而图９-１９（ｂ）是二重循环结构，在Ａ循中又出现了Ｂ循环结构（图中阴影部分）。若Ｂ循环体中还包含Ｃ循环结构则形成三重循环结构。以此类推。多重循环结构是如何执行的，以图９-１９（ｂ）的二重循环结构为例说明如下。Ａ＝１，输出１Ｂ＝１，输出１Ｂ＝２，输出２Ｂ＝３，输出３上一页下一页返回9.2算法Ａ＝２，输出２Ｂ＝１，输出１Ｂ＝２，输出２Ｂ＝３，输出３Ａ＝３，输出３Ｂ＝１，输出１Ｂ＝２，输出２Ｂ＝３，输出３上一页下一页返回9.2算法从以上执行情况可以看出Ｄ层Ａ循环的每一个Ａ（１，２，３），内层Ｂ循环约执行一个完整循环（Ｂ从１循环到３）。这是因为Ｂ循环是Ａ循环循环体的一部分。所以对Ａ的每一次循环，循环体总是完整地执行一遍。这个例子列举了Ａ、Ｂ的所有可能的搭配：（１，１），（１，２），（１，３）（２，１），（２，２），（２，３）（３，１），（３，２），（３，３）例９７输出２０以内（含２０）所有完全平方数Ｃ９满足Ｃ２＝Ａ２＋Ｂ２。上一页下一页返回9.2算法据题意可知，影响答案的因素有Ａ、Ｂ、Ｃ，最简单的解题方法是：假设一组Ａ、Ｂ、Ｃ的值，直接带入关系式Ｃ２＝Ａ２＋Ｂ２，若满足，则得到一组解（例如，Ａ＝３，Ｂ＝４，Ｃ＝５）。要得到全部可能的解，需要检测全部可能的Ａ、Ｂ、Ｃ组合。Ａ、Ｂ、Ｃ的取值范围均为ｌ～２０。分别穷举Ａ、Ｂ、Ｃ可能的值，并使它们逐一搭配，只要满足条件Ｃ２＝Ａ２＋Ｂ２，就是一组解。这样，对Ａ、Ｂ、Ｃ的每种搭配进行检测，输出所有满足条件Ｃ２＝Ａ２＋Ｂ２的Ａ、Ｂ、Ｃ组合即可。ＡＢＣ１１１上一页下一页返回9.2算法１１２……１２１……２１１……３４５满足５２＝３２＋４２……１２１６２０满足２０２＝１２２＋１６２……上一页下一页返回9.2算法描述该算法的Ｎ-Ｓ流程图如图９-２０所示。可见，利用穷举法解题步骤如下。（１）分析题口，确定答案的大致范围。（２）确定列举方法。常用的列举方法有：顺序列举，排列列举和组合列举。（３）遍历所有情况进行检测。（４）输出与题目要求完全一致的一组或多组答案，也可能没有答案。上一页下一页返回9.2算法穷举法的特点是算法简单，容易理解，但运算量较大（通过对具体问题的分析，可以缩小穷举范围，从而减小运算量）对于可确定取值范围但又找不到其他更好的算法时，就可以用穷举法。穷举法大多以循环控制结构实现。２．迭代法迭代法是一种数值近似求解的方法。在科学计算领域中，许多问题需要用这种方法解决。例如求解高次方程或微分方程等。迭代法的特点是：把一个复杂问题的求解过程转化为相对简单的迭代算式，然后重复执行这个简单的算式，直到得到最终解。上一页下一页返回9.2算法我们以求解方程f（x）＝０为例说明迭代法的基本方法。首先把求解方程变换成为迭代算式x＝g（x），然后由估计的一个根的初始近似值初X０出发，应用迭代计算公式xk＋１＝g（xk）求出另一个近似值X１，再由X１确定X２，…，最终构造出一个序列X０，X１，…，Xn，…，就可逐次逼近方程的根。例９-８用迭代法求正数a的算术平方根。设f（x）＝x－＝０则求a的算术平方根的迭代公式如下：

xn＝０．５*（xn－１＋a／xn－１）上一页下一页返回9.2算法迭代步骤如下：（１）先确定a的平方根的初值x０。例如x０＝０．５a，并代入迭代公式计算，所得的x１是a的平方根的首次近似值。（２）把x１作为x０，再代入迭代公式计算，得到新得的x１，此次的x１比上次的x１，即本次的x０更接近a的平方根。上一页下一页返回9.2算法（３）当｜x１－x０｜≥ε时，表示近似值的精度不够，转步骤（２）继续迭代。当｜x１－x０｜＜ε时，表示x１就是a的平方根的近似值（近似程度与ε有关）。ε是一个很小的正数，用来控制误差，ε越小，误差越小，但迭代次数也越多。描述该算法的Ｎ-Ｓ流程图如图９-２１所示。３．递推这是程序设计中常用的算法，最常见的例子是计算级数，一般给出数列后项与前项的递推公式，从已知的递推初始条件出发，根据递推公式就可以逐项递推各数据项。上一页下一页返回9.2算法例如：等差数列（首项为１，公差为２）的递推公式如下。g（n）＝２＋g（n－１）g（１）＝１（递推初始条件）g（１）＝１，g（２）＝３，g（３）＝５，g（４）＝７…著名的Ｆｉｂｏｎａｃｃｉ数列递推公式：f（n）＝f（n－１）＋f（n－２）f（１）＝１，f（２）＝１（递推初始条件）f（１）＝１，f（２）＝１，f（３）＝２，f（４）＝３，f（５）＝５…上一页下一页返回9.2算法例９-９用递推法求Ｆｉｂｏｎａｃｃｉ数列的前２０项（１，１，２，３，５，８，１３，２１，３４，…）。可以用如下递推公式求它的第n项：fn＝１，n＝１，n＝２

fn－１＋fn－２

n＞２首先f１＝１，f２＝１，由递推公式fn＝fn－１＋fn－２（n＝３，４，…，２０），可以计算Ｆｉｂｏｎａｃｃｉ数列的前２０项，这个过程可用循环实现。具体算法如图９--２２所示。又如，求阶乘f（n）＝n！也可以用递推法求解。其递推公式为：上一页下一页返回9.2算法fn＝１，（n＝１）递推初始条件

n*f（n－１）（n＞１）要计算１０！，可以从递推初始条件f（１）＝１出发，应用递推公式f（n）＝n*f（n－１）逐步求出f（２），f（３），…，f（１０），即由简到繁逐次递推，直到最后求出f（１０）的值。f（１）＝１f（２）＝２*f（１）＝２f（３）＝３*f（２）＝６f（１０）＝１０*f（９）上一页下一页返回9.2算法４．递归递推法是利用递推公式，由简到繁逐次递推求解。递归法也是利用递推公式，所不同的是，它是根据递归公式，由繁逐次化简，用简单的问题和已知的操作运算来解决复杂的问题。例９-１０用递归法求f（n）＝n！。由于n！＝n（n－１）！，（n－１）！＝（n－１）（n－２）！，…，２！＝２１！，１！＝１，所以其递归公式为：fn＝１（n＝１）递推初始条件

n*f（n－１）（n＞１｛）上一页下一页返回9.2算法与递推求解不同，递归法先从f（n）开始，逐步化简：f（n）＝n*（n－１）！＝n*f（n－１）f（n－１）＝（n－１）*（n－２）！＝（n－１）*f（n－２）

……f（３）＝３*２！＝３*f（２）f（２）＝２*１！＝２*f（１）f（１）＝１！＝１由复杂的f（n）逐步递推化简到f（１）在化简的过程中，f（n－１），f（n－２），…仍为未知量，直到化简到f（１）时，由于f（１）＝１已知，化简到此为止，故f（１）＝１称为递归终止条件。上一页下一页返回9.2算法f（n）便可由递归终止条件f（１）＝１推出f（２）＝２*１＝２，由f（２）＝２推出f（３）＝３*２＝６，…，最后由f（n－１）推出f（n）＝n*f（n－１）上述过程包含两个部分。（１）由繁到简的递归化简（f（n）逐步化简到f（１））。（２）由已知值f（１）＝１回归到所求f（n）。上一页下一页返回9.2算法如果f（n）是求n！的算法过程，则f（n－１）是求（n－１）！的算法过程，它们的算法过程完全相同，只是参数不一样罢了。由于f（n）＝n*f（n－１），所以在计算f（n）过程中，要计算f（n－１），这就形成了一个过程又调用了它自身的现象，称为递归。递归的定义是：如果一个过程直接或间接地有限次数地调用了它自身，则称个过程是递归的。用递归法求f（n）＝n！的算法如图９-２３所示。上一页返回9.3结构化程序设计

由于硬件的限制，早期的程序规模通常较小，程序设计的优劣以速度快和占用内存少为主要标准。随着计算机硬件的迅猛发展，速度和存储容量不断提高，但要解决的问题却变得更加复杂，程序规模也越来越大。大型软件的工作量远非一个程序员的能力所能承担，必须多个程序员合作才能完成。过去各自为战的程序设计方法很少考虑程序员之间的协作和交流，编写的软件错误随软件规模的增大而快速增加，使调试成本迅速上升，甚至软件尚未发布便因故障率太高而宣布报废。出现了所谓“软件危机”。下一页返回9.3结构化程序设计１９６８年，Ｄｉｊｋｓｔｒａ提出“ｇｏｔｏ语句有害”。ｇｏｔｏ语句又称无条件转向语句，它对应的是传统流程图中随意转向的流程线。它破坏了程序的静动一致性，使程序难于调试和维护，限制了代码优化。“ｇｏｔｏ语句有害”的观点引起了人们对程序设计方法讨论的普遍重视，在长达数年的争论基础上，产生了结构化程序设计方法。结构化程序设计方法是一种完成复杂任务时避免混乱的技术。它主张程序结构要规范化，避免使用破坏程序结构的ｇｏｔｏ语句，按人的大脑容易理解的方式组织复杂问题的求解过程将复杂问题分解成若于易于解决的简单问题。不以速度和节省内存为目标而是以结构清晰、可读性好、易于分工合作编写和调试维护为目标。上一页下一页返回9.3结构化程序设计9.3.1结构化程序设计方法的基本思想结构化程序设计方法的基本思想主要有３点。（１）模块化。大型复杂程序控功能分解成一些规模较小、相互独立的功能模块并按层次关系组织这些模块。模块可以是一条语句也可以是一段程序通常实现一个单一功能。（２）采用“自顶向下，逐步求精”的方法实施层次化、模块化的程序结构。从宏观到微观自顶向下将复杂问题分解成若干子问题。若干问题仍然复杂则再继续分解成较简单的问题。这样逐层分解直到功能单一、编写代码方便为主。上一页下一页返回9.3结构化程序设计（３）任何复杂问题的程序都可以用顺序结构、选择结构和循环结构这３种基本结构组成。３种基本结构之间形成顺序执行关系。程序只能由这３种基本结构或它们的组合嵌套组成，以保证程序结构的规范化。３种基本结构具有如下特点：只有一个入口和一个出口，结构中不存在如图９-２４所示的死循环和死语句。循环控制条件为j≤１０，j的初值为１，而循环结构中不存在修改j的值，因此j恒为１，循环控制条件j≤１０永远为真，所以该循环结构是死循环。语句k＋k→k仅k＞１０时才执行。而k的初值为１，以后从未修改k的值。所以k＞１０永远为假，即永远不会执行语句k＋k→k，它是死语句。基本结构中不能出现死循环和死语句。上一页下一页返回9.3结构化程序设计9.3.2结构化程序由顺序结构、选择结构和循环结构这３种基本结构或它们的组合嵌套组成的程序称为结构化程序。结构化程序中的各基本结构之间形成顺序执行关系。关于顺序结构、选择结构和循环结构的概念和组成在§９．２节已经叙述，这里不再赘述。在结构化程序设计中，应当遵循一些基本的原则：（１）仅使用顺序结构、选择结构和循环结构来表示程序逻辑。（２）选用的控制结构只准许有一个入口和一个出口。（３）复杂结构应该用３种基本结构组合嵌套而实现。（４）严格限制使用ｇｏｔｏ语句。上一页下一页返回9.3结构化程序设计9.3.3自顶向下逐步求精结构化程序设计方法的基本思想是采用“自顶向下，逐步求精，模块化”的程序设计方法和一个入口、一个出口的控制结构。对复杂问题从全局入手，把复杂问题分解为若干相互独立的子问题，然后对每个子问题再作进一步分解，直到每个子问题很容易解决为止。每个子问题对应一个模块，由于每个模块功能单一、逻辑简单、模块之间相互独立，使完成模块的程序设计工作变得简单而明确。一个复杂的问题就转化成一系列简单模块的设计。用这些分解的模块就可以按层次关系像搭积木一样搭成完整的程序系统，并且为扩展系统功能提供了方便。上一页下一页返回9.3结构化程序设计上述细化过程一般可以分为３种。１）分割技术分割技术的第一步要把问题分成互不相交的子问题，直到可以用复合语句描述为止。其次依次解决分割后的子问题。２）递推技术有些问题在求解过程中一次仅能做出有限进展，故需要循环语句进行递推。由于有些问题很复杂，需要重复进行递推，直到问题最终完成为止。３）分析技术分析技术是对某一问题采用分析的方法逐步细化，直到问题可以用条件语句描述为止。上一页下一页返回9.3结构化程序设计例９-１１以求一元二次方程ax２＋bx＋c＝０的根为例，说明“自顶向下，逐步求精”的结构化程序设计方法。对一元二次方程ax２＋bx＋c＝０，要考虑其系数a、b、c各种可能的取值情况。若a为０，则原方程蜕化为一元一次方程bx＋c＝０，所以当b不为０时，x＝－c／b；当a不为０时，有两个根（实根或复根）：若b２－４ac≥０，有两个实根：上一页下一页返回9.3结构化程序设计若b２－４ac＜０，有两个共轭复根：“自顶向下，逐步求精”的程序设计方法先全局后局部。先整体后细节，先抽象后具体，其优点在于问题考虑全面，程序结构清晰，层次分明，可读性好。一般而言，求解本问题的程序可以分成３部分：输入部分、计算处理部分和输出部分。输入部分负责输入必要的原始数据，计算处理部分根据问题的算法求解，得到的结果由输出部分显示或打印。因此，本题的顶层设计就是把问题划分为３个模块：Ｍ１、Ｍ２和Ｍ３。上一页下一页返回9.3结构化程序设计Ｍ１模块用来输入方程的系数a、b、c；Ｍ２模块的功能是计算方程的根；Ｍ３模块负责输出结果。它们的执行顺序是Ｍ１，Ｍ２，Ｍ３，如图９-２５所示。对这些模块还可以“逐步求精”进行细化。对Ｍ１模块，功能是输入方程的三个系数，比较简单，不必再细分了。Ｍ２模块的功能是求根，当二次项系数a为０时，方程蜕化成一次方程，bx＋c＝０，x＝－c／b，求根方法不同于二次方程。可见Ｍ２模块比较复杂，需要进一步细化。Ｍ２模块可以再细分成Ｍ２１和Ｍ２２两个模块，Ｍ２１模块的功能是一次方程的求根，无须细分。Ｍ２２模块的功能是二次方程的求根，如图９-２６所示。上一页下一页返回9.3结构化程序设计实际上，Ｍ２２模块还可以再分解为求实根和求复根两个子模块，这里就不再细分了，因为求实根和求复根在同一个模块中处理并不复杂。Ｍ２２模块如图９-２７所示。对Ｍ３模块，由于结果的３种可能性（一次方程的根x１，二次方程的实根x１＋x２、x１－x２；二次方程的复根x１＋x２、x１－x２犻），所以模块中根据情况不同分别输出方程的根。Ｍ３模块如图９-２８所示。现在可以把各模块流程图按如图９-２５所示的顺序组装成完整的流程图，如图９-２９所示。根据流程图就可以选择合适的计算机语言编写程序了。上一页返回9.4面向对象程序设采用结构化程序设计方法，使程序结构规范，模块内部均由３种基本结构组成，模块之间关系简单清晰。因此程序可读性好，容易理解，便于设计、便于测试和便于维护。由于采用“自顶向下，逐步求精，模块化”设计方法，可以有效组织人力，发挥团队的优势，提高编程工作的效率，有利于软件工程化开发。结构化程序设计方法也存在如下不足。（１）数据和对数据的操作分开设计，不利于程序的修改和维护。因为数据操作过程是一段程序，该程序往往针对某种固定数据结构进行操作，一旦数据结构修改，该程序必须修改，增加程序维护成本。实际上，数据和对数据的操作关系密切，设计时应统一考虑。将数据和对数据的操作人为地分开设计，只会增加程序开发难度，不利于程序的调试和维护。下一页返回9.4面向对象程序设（２）程序代码可重用性差。从事软件编程工作既辛苦又复杂，因此人们当然希望自己设计的程序具有可重用性，即把特定程序作为一个个软件部件，需要时选择某些部件就可以组装成新的系统而不必每个系统都要重新编程。采用结构化程序设计不法，难于实现“代码重用”。随着硬件性能的不断提高和图形用户界面的流行，软件规模待续高速增长。（２）程序代码可重用性差。从事软件编程工作既辛苦又复杂，因此人们当然希望自己设计的程序具有可重用性，即把特定程序作