《大学信息技术基础》-第4 章

4.1问题求解与程序设计4.1.1一般问题的解决过程在日常生活中，我们会随时遇到各种各样的事情，面对各种各样的问题。家庭中的问题可能是正餐吃什么、今晚看什么电视节目、买哪一辆车等。工作中的问题可能是搞好同事关系、制定工作策略、处理好与客户的关系等。当我们面临一个需要解决的问题时，一般要经历下列几个步骤：明确问题、理解问题、寻找备选方案、从备选方案列表中找出最好的解决方案、列出所选择的解决方案的步骤、评价解决方案。1.明确问题下一页返回4.1问题求解与程序设计解决问题的第一步是明确问题。如果问题不明确，就不会知道该用什么方法去解决。2.理解问题分析并理解问题，了解问题所涉及的相关知识。也就是说，当为用户制定一套解决方案的时候，我们必须了解用户的知识范围和背景。3.寻找备选方案尽可能全面地列出可选方案。可以征求不同人的意见以找到不同的解决方案，当然这些方案必须是可行的。4.方案选择上一页下一页返回4.1问题求解与程序设计根据制定的评定标准对所有的方案进行评价，评价每种方案的利弊，并选出最佳方案。5.列出所选择的解决方案的步骤运用有限的、分步的指令来描述已选定的方案。问题的解决步骤是一系列的指令，按照这些指令才能达到最后的结果。任何人或机器无法理解的指令都不能使用，特别是在使用计算机进行工作时，这种限制就更加严格。6.评价解决方案通过执行方案，检查它的结果是否正确，是否令用户满意。如果结果错误或者不令人满意，就必须重新设计一个解决方案。上一页下一页返回4.1问题求解与程序设计4.1.2计算机求解问题的过程在计算机中，它是如何来处理问题的呢？计算机是没有智能的，它不能分析问题并产生问题的解决方案。用计算机求解任何问题，首先必须给出解决问题的方法和步骤，也就是算法，再按照某种语法规则编写成计算机可执行的指令即程序，然后让计算机执行这些指令，这个过程就是程序设计过程。该过程分为以下5个主要步骤。1.问题分析分析问题是第一步，也是最重要的步骤。上一页下一页返回4.1问题求解与程序设计在这个阶段，首先要明确和理解所要解决的问题是什么；已知条件和数据有哪些，如何获得这些数据；要输出的结果是什么，产生的结果以何种形式来输出；问题的定义中包含了哪些限制和约束；等等。只有在问题被准确定义并完全理解后才能研究问题的解决办法。2.算法设计在这个阶段，需要给出求解问题的一系列步骤，即确定解决问题的算法，并对算法的正确性进行验证。算法是根据问题分析结果得来的，是对问题处理过程的进一步细化，但它不是计算机可以执行的，只是编写程序前对处理思想的一种描述。上一页下一页返回4.1问题求解与程序设计算法设计往往是解决问题的过程中最难的一部分，一开始不要试图解决问题的每一个细节，取而代之的是采用自顶向下、逐步求精和模块化的设计方法。在自顶向下的设计中，首先列出需要解决的主要步骤，或称为子问题，之后通过求解每一个子问题来最后解决整个问题。这和我们撰写学期论文相似，开始编写论文提纲时，我们首先列出大标题的题目，之后为每一个大标题列出相应的小标题，一旦大纲完成，我们就开始为每一个小标题编写内容。3.实现算法问题分析和算法设计已经为程序设计规划好了蓝本，接下来的步骤是用计算机能够执行的形式实现算法。上一页下一页返回4.1问题求解与程序设计实现算法就是将一个算法描述正确地编写成计算机语言程序，即通常所说的“编码”。而程序设计语言的选择，可根据具体的问题和需求而定，需要考虑语言的适用性、问题求解的效率等。将用计算机语言编写的程序代码输入计算机中，必须保证程序没有语法错误。为了验证语法的正确性，需要通过编译器来运行代码。如果编译器产生了错误信息，则必须识别出代码中的错误并改正这些错误，然后再使用编译器来运行代码。4.测试和验证程序编译器只保证程序没有语法错误，并不能保证程序没有错误而正确运行。上一页下一页返回4.1问题求解与程序设计在程序执行期间，程序可能因为逻辑错误而异常终止，如0作为除数。即使程序正常结束，它仍然可能产生错误结果，比如我需要得到的结果是两个数的最大值，而程序得出的答案是最小值。这就需要测试程序来验证所有的需求功能是否正确实现。在实际应用中，不要仅仅依赖于一个测试用例，而要多选择一些典型的数据运行程序，确保每一种情形都正确工作。5.维护和更新程序维护和更新程序重点放在修改程序来去除以前没有检测到的错误或者根据用户需要升级改进程序。上一页下一页返回4.1问题求解与程序设计正如所看到的，当人们要应用计算机求解问题时，需要编写出使计算机按人们意愿工作的程序。编程本质上就是为解决问题而设计算法，并实现算法使计算机能理解它们。算法设计直接影响计算机求解问题的成功与否。上一页返回4.2算法基础4.2.1算法的定义与特征任何解决问题的过程都是由一定的步骤组成的，把解决问题所采取的方法和步骤称为算法。例如，烘烤巧克力夹心饼干的配方就是一个算法。任何一个人只要熟悉一点烹饪方法，就能仔细按照操作说明，烘烤出一炉可口的饼干。一首歌曲的乐谱，也可以称为该歌曲的算法，因为它指定了演奏该歌曲的每一个步骤，按照它的规定就能演奏出预订的曲子。同样地，为某人提供到你家的路线时，你定义的就是一个算法，遵循该算法他就能到达指定的目的地。在现代社会，算法十分普遍，因为我们经常面对一些不熟悉的任务，如果没有指令就不可能完成。下一页返回4.2算法基础你可能不知道如何组装一辆自行车，所以自行车附带的组装说明书提供的算法能够指导你完成这些任务。利用计算机解决问题的关键就在于设计出合适的算法。也就是说，在一台计算机可以运行一个任务之前，必须给它一个算法来准确地告诉它要做什么。算法表达了解决问题的核心步骤，反映的是程序的解题逻辑。本书所关心的是用计算机语言描述的，并能在计算机上可执行的各种算法，如计算1到100以内的奇数的乘积、将100个学生的考试成绩由高到低进行排序等。有的问题虽然可由计算机求解，但手工算法与计算机算法大不相同。上一页下一页返回4.2算法基础针对计算机算法，我们给出如下定义：算法是一组明确步骤的有序集合，它产生结果并在有限的时间内终止。计算机算法应该具备以下特征。（1）有穷性。一个算法必须保证在执行有限运算步骤后终止。在实际应用中，算法的有穷性还应该包括执行时间的合理性。（2）确定性。算法中的每一个步骤必须有确切的定义，不允许有模棱两可的解释，也不允许有多义性。上一页下一页返回4.2算法基础（3）有零个或多个输入。这里的输入是指在算法开始之前所需要的初始数据。对于要处理的数据，大多数通过输入得到，输入的方式可以通过键盘或文件等。一个算法也可以没有输入，如求5！，在执行算法时不需要输入任何信息。（4）有一个或多个输出。算法的目的是为了求解，“解”就是输出。一个没有输出的算法是毫无意义的。因此，当执行完算法之后，一定要有输出的结果。（5）有效性。上一页下一页返回4.2算法基础算法中的每一个步骤都应当能够被有效地执行，并得到确定的结果。如算法执行过程中出现x/0、负数开方等操作将导致算法无法执行。用精确的步骤来解答问题需要经验、创造力以及缜密的思维。一旦想好求解问题的算法，任何人只要遵循算法步骤就可以求解这一特定的问题。对于一般最终用户来说，他们并不需要在处理每一个问题时都要自己设计算法和编写程序，可以使用现成的算法和程序，用户只需根据已知算法的要求给予必要的输入，就能得到输出的结果。4.2.2程序的基本结构一个完整的源程序一般包含两大结构，即数据结构和控制结构。上一页下一页返回4.2算法基础源程序中数据结构大部分由说明语句来标识，这是一些编译后不生成目标代码的语句，称之为“非执行语句”；控制结构是由一些指挥计算机产生动作的可执行语句组成。（1）程序中的数据结构。计算机程序的处理对象是描述客观事物属性的数据，由于客观事物的多样性，数据有不同的形式，如整数、实数、字符，以及所有计算机能够接受、存储和处理的符号集合。在程序中，形式不同的数据采用数据类型来标识。整数、实数、字符等都是数据类型，都是在数据的基础上，抽象出它们本质上的共有特征而得到的。上一页下一页返回4.2算法基础每种不同类型的数据，在计算机内部都有不同的表示方式，而且都有相应的存储方式和取值范围。源程序中数据结构基本上由说明语句来标识，说明语句是一些编译后不生成目标代码的语句，仅为编译程序提供编译信息，程序被执行时也不产生机器动作和执行结果，所以称之为“非执行语句”。所有数据类型不仅定义了一组形式相同的数据集，也定义了对这组数据可施行的一组操作集。（2）程序中的控制结构。①顺序结构。上一页下一页返回4.2算法基础程序就是语句的有序集合。通常情况下，计算机按照程序员指定的顺序执行每一条指令。第一条语句先执行，接下来是第二条……一直到程序末尾。下面是一段用C语言编写的程序，用以输出“Thisisthefirstline.”和“Thisisthesecondline.”。printf（＂Thisisthefirstline.＂）；printf（＂Thisisthesecondline.＂）；虽然大部分现在的编程语言不需要写行号，但有些旧的编程语言则要标注行号，如下面这段用BASIC最初版本写的程序：100PRINT＂Thisisthefirstline.＂200PRINT＂Thisisthesecondline.＂上一页下一页返回4.2算法基础如果程序中标了行号，计算机就会从行号最小的语句开始执行，接着是次小的。图4−1中的流程图表述了一段小的顺序指令。②选择结构。选择控制结构也称为决定结构或分支，告诉计算机根据所列条件的正确与否选择执行路径。比较简单的选择结构是if−else语句。下面这段程序使用if−else结构判断输入的数字是否大于10。若大于10，打印“Thatnumberisgreaterthan10!”否则，打印“Thatnumberis10orless.”。intNumber;printf("Enteranumberfrom1to10:");上一页下一页返回4.2算法基础scanf("%d",&Number);if(Number>10)printf("Thatnumberisgreaterthan10!");elseprintf("Thatnumberis10orless.");图4−2用流程图描述了计算机如何执行这种结构。③循环结构。循环结构又称为重复控制结构或迭代结构，可以重复执行一条或多条指令直到满足退出条件。一般，高级程序设计语言有两种形式的循环结构：一种是先判断条件是否满足，如果满足就反复执行指令，我们称之为“当型循环”；另一种是先执行指令再判断条件是否满足，满足就再次执行指令，我们称之为“直到型循环”。上一页下一页返回4.2算法基础图4−3分别表示出这两种结构。4.2.3算法的表示强调算法和它的表示的区别是非常重要的，这就好像一个故事和一本书的分别。一个故事本质上是抽象的，一本书是一个故事的物理表示。如果一本书被翻译成其他语言，仅仅是故事的表示改变了，而故事本身并没有变化。表示算法的方法有多种，常用的方法包括自然语言、流程图、伪代码和计算机语言等，不同的表示方法有不同的特点和作用。1.自然语言表示算法上一页下一页返回4.2算法基础自然语言就是人们日常使用的语言，可以是汉语、英语或其他语言等。例如，我们用自然语言来描述“A、B为整数，求A除以B的商”这一算法。（1）输入A、B的值；（2）如果B为零则说明这是非法的除法运算，所以无法得到余数，输出“除数为零”报错信息，算法结束；否则转去执行步骤（3）；（3）计算A除以B的商；（4）输出计算出的商，算法结束。上一页下一页返回4.2算法基础从上面的例子可以看出，用自然语言表示的算法通俗易懂，但是，该方式的主要问题是冗长、语义容易模糊，很难准确地表示复杂的、技术性强的算法。2.流程图表示算法流程图是算法的图形表示法，它用规定的一系列图形、流程线及文字说明来表示算法中的基本操作和控制流程。美国国家标准化协会ANSI（AmericanNationalStandardsInstitute）规定了一些常用的流程图符号，已为世界各国程序工作者普遍采用。常用的流程图基本符号及其含义如表4−1所示。上一页下一页返回4.2算法基础其中，判断框的作用是对一个给定的条件进行判断，根据给定的条件是否成立决定如何执行其后面的操作。判断框有一个入口，两个出口，两个出口分别表示条件成立和不成立时的执行顺序，通常标注Yes和No或True和False或“真”和“假”等字样。图4−4给出了三种基本结构的流程图表示。3.伪代码表示算法伪代码是一种介于自然语言和计算机语言之间的表示形式。它比自然语言简单，又比计算机语言灵活，没有严格的语法规则，但很容易转换成计算机语言程序。上一页下一页返回4.2算法基础4.计算机语言表示算法用自然语言、流程图和伪代码表示的算法，计算机都是不能直接识别的。计算机语言是算法的最终表示形式，任何算法只有采用计算机语言编写程序才能被计算机识别和执行。用计算机语言表示算法必须严格遵循所用语言的语法规则，这是和伪代码不同的地方。4.2.4基本算法有一些算法在计算机科学中的应用非常普遍，我们称之为基本算法。本节将对一些基本算法进行讨论。讨论只是概括性的，具体的实现则取决于所采用的程序设计语言。上一页下一页返回4.2算法基础1.求和计算机科学中经常用到的一种算法是求和。求和问题的思路比较简单，无非是将所有的数累加起来。对于两个或三个数相加，我们可以很容易实现。但是，如果求和的数比较多，我们怎样才能实现呢？对于求和问题，一般在循环中使用加法操作来实现（见图4−6）。求解此类问题的基本步骤，可以概括如下：（1）首先将和sum初始化。（2）循环，每次将一个新数加到和sum上。（3）退出循环后返回结果。上一页下一页返回4.2算法基础2.乘积另一个常用算法是求出一系列数的乘积，如求1×2×3×4。对于乘积问题，一般在循环中使用乘法操作来实现（见图4−7）。求解此类问题的基本步骤，可以概括如下：（1）首先将乘积product初始化。（2）循环，每次将一个新数与乘积product相乘。（3）退出循环后返回结果。3.最大和最小上一页下一页返回4.2算法基础求最大或最小值是我们在日常生活中经常会遇到的事情，比如在参加计算机考试的所有同学中找出成绩最高者和最低者，在一屋子人中找出年龄最大者和最小者，在温度列表中找出每天的最高温度和最低温度，等等。解决这类问题，我们通常采用的方法是进行比较。在计算机科学中，寻找最大值和最小值也是我们经常使用的算法之一。现在，我们考虑如何从一组任意的正整数中找出其最大值的算法，这个算法必须具有通用性并且与整数的个数无关。要解决这个问题，先用少量的一组正整数求其最大值，然后将这种解决方法扩大到任意多的正整数。图4−8给出了从6个正整数（18、23、9、36、12、67）中寻找最大值的方法。上一页下一页返回4.2算法基础（1）首先检查第一个整数18。因为还没有检查其他的整数，所以当前的最大值就是第一个数。算法中定义了一个称为Largest的变量，并把第一个数18赋给了它。（2）把上一步得到的最大值Largest和第二个数23比较。第二个数23大于最大值18，将23赋值给Largest，然后进入下一步。（3）该步中最大值没有改变，因为当前Largest比第三个数9大。（4）目前的最大值是23，但是新的数36大于Largest。把36赋给Largest，然后进入下一步。（5）该步中最大值没有改变，因为当前Largest比第五个数12大。上一页下一页返回4.2算法基础（6）目前的最大值是36，但是新的数67大于Largest。Largest应该由第六个数67代替，把67赋给Largest。分析上面给出的方案，可以看出第一步中的动作与其他步骤中的不一样。第一步，把最大值Largest设为第一个数。第二步到第六步，依次把当前处理的数与最大值Largest进行比较。如果当前处理的数大于最大值Largest，则把它赋给Largest，成为最大值。在算法设计中，可以通过判断结构找到两个数的较大值。再把这个结构放在循环中，就可以得到一组数中的最大值。我们将这个算法泛化，给出从n个正整数中寻找最大值的基本步骤：（1）将第一个数置为最大值Largest。上一页下一页返回4.2算法基础（2）循环，每次将一个新数与最大值Largest比较，如果大于Largest，将Largest置为当前数。（3）退出循环后返回结果。求解一组数中的最小值和上面的方法相似，不同之处在于用判断结构找出两个数中的较小值。4.排序排序问题要求按照某种顺序重新排列数据项，如对学生成绩从高到低排序、电子邮件列表按照日期排序、通讯录中朋友的姓名按照字母顺序排列，等等。上一页下一页返回4.2算法基础在计算机领域，把无序列表转化成有序列表是很常见的操作，目前已有几十种排序算法，本节主要介绍三种排序方法：选择排序、冒泡排序和插入排序。（1）选择排序。选择排序算法可能是最容易的排序算法，因为它反映了如何手动地对列表中的值进行排序的过程。设想如果交给你一份由数字元素组成的列表,要求按照由小到大的顺序进行排序,我们可以采用如下的方法：①找到最小的数字，把它写到另一张纸上。②从原始列表中删除这个数字。上一页下一页返回4.2算法基础③继续这一循环，直到原始列表中的所有数字都被删除，写入了第二个列表，此时第二个列表就是有序的。这个算法虽然简单，但有缺陷，它需要两个完整列表的空间。即使不考虑内存空间，复制操作显然也很费时。不过对这种手动方法稍作修改，可以免除复制空间。当从原始列表删除一个数字后，就空出了一个位置，因此不必把最小值写入第二个列表，把它与应该所在的位置处的当前值交换即可。整个排序过程分成比较和交换两个大步骤。在选择排序中，数字列表被分为两个子列表，即未排序部分和已排序部分，它们通过假想的一堵墙分开。上一页下一页返回4.2算法基础找到未排序子列表中最小的元素并把它和未排序数据中的第一个元素进行交换。经过每次选择和交换，两个子列表中假想的这堵墙向前移动一个元素，这样每次排序列表中将增加一个元素，而未排序列表中将减少一个元素，每次把一个元素从未排序列表移到已排序列表就完成了一次分类扫描。一个含有n个元素的列表需要n−1次扫描来完成数据的重新排列。图4−9给出了对7个整数进行排序的步骤，其中灰色表示已排序部分。该图显示出了在已排序列表和未排序列表之间的那堵墙在每次扫描中是如何移动的。上一页下一页返回4.2算法基础选择排序算法使用两重循环，外层循环每次扫描时迭代一次。内层循环在未排序列表中寻找最小的元素。图4−10给出了选择排序的流程图。（2）冒泡排序。冒泡排序是最为常用的一种排序方法，其基本思想是：在要排序的一组数据中，对当前还未排好序的范围内的全部数，自下而上对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的数往上冒。即每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。上一页下一页返回4.2算法基础在冒泡排序法中，数字列表被分为两个子列表：已排序的和未排序的。在未排序的子列表中，最小的元素通过冒泡的方法选出来并移到已排序的子列表中。当把最小的元素移到已排序列表后，将墙向前移动一个元素，使得已排序的元素个数增加1个，而未排序的元素个数减少1个。每次元素从未排序子列表中移到已排序子列表中，便完成一次分类扫描。含有n个元素的列表，冒泡排序需要n−1次扫描来完成数据排列。图4−11给出了每次经过扫描后墙移动一个元素的过程，其中灰色部分表示已经排好序的元素。上一页下一页返回4.2算法基础第一次扫描，从52开始并把它与78比较，因为52小于78，这两个元素进行位置交换。继续下一个元素，52和22进行比较，位置未发生改变。继续22和7进行比较，也未发生变化，直到7和40进行比较，由于7比40小，这两个元素进行位置交换。继续下一个元素，因为7向左移动一个元素，它现在和72比较，显然这两个元素需交换位置。最后，7和16比较并交换位置。经过一系列交换7被放置在第一的位置，并且墙向前移动了一个位置。注意在墙到达列表的末端之前，我们已经停止了，因为列表已经是有序的了。上一页下一页返回4.2算法基础冒泡排序也使用两重循环，外层循环每次扫描过程中迭代一次；每次内层循环则将某一元素冒泡至顶部（左部）。（3）插入排序。插入排序是常用的排序技术之一，经常在扑克牌游戏中使用。游戏人员将每张拿到的牌插入手中合适的位置，以便手中的牌以一定的顺序排列。插入排序的特点就是将待排序的元素一个个插入已经排好序的列表里去，而这涉及插入位置的确定。显然，要确定一个元素的插入位置，需要将待排序的元素与已排序好的元素进行比较。在插入排序中，和本章中讨论的其他两种排序方法一样，排序列表被分为两部分：已排序和未排序的。上一页下一页返回4.2算法基础在每次扫描过程中，未排序子列表中的第一个元素被取出，然后转换到已排序的子列表中，并且插入合适的位置。可以看到，含有n个元素的列表至少需要n−1次排序。图4−12演示了7个数进行插入排序的过程。每次扫描过程中，当从未排序子列表中移动一个元素到已排序子列表时，墙便向前移动一个位置。插入排序算法的设计类似于选择排序算法和冒泡排序算法的模式。外层循环每次扫描迭代一次，内层循环则寻找插入的位置。我们将流程图留给读者作为练习。上一页下一页返回4.2算法基础上述讨论的三种排序算法是最简单的算法，容易理解和分析，它们是更高效算法的基础。除了这三种，还有其他的排序算法，如快速排序、堆排序、希尔排序、合并排序等，大多数高级排序算法在数据结构方面的书中有所讨论。5.查找查找是我们在日常生活中经常要做的一项工作。例如，在学生名单中查找一名特定的学生，在图书馆的藏书中找某一本书，在互联网上搜索一个特定的术语，在最节省燃料的情况下寻找货车投递包裹的最佳路线等。上一页下一页返回4.2算法基础在计算机科学领域，计算机经常要存储和维护大量信息，并且需要从数据中检索特定的值。在计算机科学里有一种常用的算法叫作查找，是一种在列表中确定目标所在位置的算法。如果目标值在列表中，我们认为查找成功，反之则认为查找失败。对于列表有两种基本的查找方法：顺序查找和折半查找。顺序查找可以在任何列表中查找，折半查找则要求列表是有序的。（1）顺序查找。上一页下一页返回4.2算法基础为了进入这个问题，想象我们如何在一个大概有20条记录的来宾表中寻找一个特定的姓名。在这种情况中，我们可以从头开始扫描整个表，将每一条记录与目标姓名进行比较。如果我们找到了目标姓名，那么查找就将以成功结束。当然，如果我们到达表的最后仍然没有找到目标，我们的查找就以失败告终。这种查找就是所谓的顺序查找。顺序查找是从表头开始查找，当找到目标元素或确信查找目标不在列表中时（因为已经查找到列表的末尾了），查找过程结束。图4−13演示了查找数值29的步骤。这种算法很简单，而且只要目标项在当前列表中，就一定能找到，但这种算法执行起来比较费时。上一页下一页返回4.2算法基础如果目标项在列表末尾，或者根本不在列表中，那么采用这种算法，在返回结果之前，将不得不搜索列表中的每一项。顺序搜索10或100项的列表还看不出有什么区别，但如果列表中有成千上万项，这种方法就不切实际了。（2）折半查找。折半查找是从一个列表中间的元素来测试的，如果列表的中间项就是我们要查找的元素，那么我们就可以说查找成功了。否则，如果中间项大于目标项，将可能范围缩小到中间项左边部分；如果中间项小于目标项，将可能范围缩小到中间项右边部分。换句话说，可以通过判断排除一半的列表。上一页下一页返回4.2算法基础重复这个过程直到找到目标或是目标不在这个列表里。图4−14给出了查找目标31的过程，其中使用了三个变量：first、mid、last。①开始时，first为1，last为12。使mid在中间的位置，（1+12）/2或6。现在比较目标数31与在位置6的数22。目标数比它大，所以忽略前半部分。②将first移动到mid的后面，即位置7，使mid在第二个一半的中间，（7+12）/2或9，现在比较目标数31与位置9的数66。目标数比它小，所以忽略数66以后的数。上一页下一页返回4.2算法基础③将last移动到mid的前面，即位置8。重新计算mid为（8+7）/2或7。比较目标数31与位置7的数31。由于找到了目标数据，此时算法结束。折半查找算法需要设计成找到元素或如果目标不在列表中算法停止。从这个算法也能看出：当目标不在列表中时，last的值就变成小于first的值，这个不正常的条件让我们知道什么时间退出循环。上一页返回4.3程序设计语言4.3.1程序设计语言的演化如前所述，计算机解决问题的过程实质上是机械地执行人们为它编制的指令序列的过程。为了告诉计算机应当执行什么指令，就需要一种意义清晰、人使用起来方便、计算机能理解的描述方式。也就是说，需要一种描述程序的语言。供人编写计算机程序的语言就是程序设计语言，也常称为编程语言。程序设计语言经过多年的发展已经从机器语言演化到高级语言。1.机器语言下一页返回4.3程序设计语言本质上计算机只能识别“0”和“1”这样的二进制信息，在计算机内部，一切信息都以二进制编码的形式存在，计算机存储并执行的程序也不例外。在计算机发展的早期，唯一的程序设计语言是机器语言。机器语言的程序全部由“0”和“1”表示出来，是计算机硬件唯一能理解的语言。用机器语言写出的程序称为机器语言程序。用机器语言编写的程序，计算机可以直接识别，同时由于机器语言程序是直接针对计算机硬件的，因此它的执行效率比较高，能充分发挥计算机的速度和性能优势。但它至少有两个缺点：首先，机器语言是与机器有关的，特定的机器语言只能用在特定的一类机器上，不是通用的。上一页下一页返回4.3程序设计语言其次，人们用这种语言编写程序很不方便，非常烦琐，工作效率极低，写出的程序难于理解，不论是阅读程序还是调试程序都非常困难。因此，除非特殊情况，一般我们不采用机器语言直接编程。2.汇编语言为了解决机器语言难以记忆、理解和阅读等问题，人们设计出第二代语言——汇编语言。汇编语言不再使用机器语言中所使用的用数字编码来代表操作码和操作数的方法。最终，为各种操作码分配各种助记符，比如，用“ADD”代表加操作，用“SUB”代表减操作，用“LOAD”表示将主存中的数据装入寄存器，用“STORE”表示将寄存器中的数据传输到主存等。上一页下一页返回4.3程序设计语言这些助记符的使用增加了汇编语言的可读性。对于操作数而言，则由程序员为存储器中的位置分配描述性的名字符号以在存储器中定位，并且使用这些符号代替在指令中的存储器单元地址。用指令助记符及地址符号书写的指令称为汇编指令，而用汇编指令编写的程序称为汇编语言程序。虽然编写汇编语言程序对程序员来说难度降低了很多，但是很遗憾，汇编语言程序不能为计算机硬件直接识别与执行，必须经过称为汇编程序的特殊程序将汇编语言代码“翻译”为机器语言才能被硬件执行。通常，将汇编语言程序称为源程序，汇编后得到的机器语言程序称为目标程序。上一页下一页返回4.3程序设计语言尽管汇编语言与机器语言相比有不少的优势，但它还是有一些不足。汇编语言与机器语言一般是一一对应的，因此，汇编语言也是与具体使用的计算机有关的，程序设计人员仍然需要从机器语言的角度去思考。这种情况类似于房屋设计——我们毕竟还是要根据木板、钉子和砖块等来设计。确实，在实际的房屋建造中，最后的确还需要一个基于这些基本元素的描述，但是如果我们考虑根据诸如房间、窗户和门等的更大一些的单元来设计，设计过程会更简单一些。3.高级语言汇编语言虽然相比机器语言有了很大进步，但仍然需要程序员在所用的硬件上花费大部分精力。上一页下一页返回4.3程序设计语言用符号语言编程也很枯燥，因为每条机器指令都得单独编码。为了提高程序员效率以及从关注计算机转到关注要解决的问题，导致了高级语言的发展。高级语言吸收了人们熟悉的自然语言和数学语言的某些成分，它由表达各种意义的“词”“数学公式”及特定的语法规则组成。高级语言适用于许多不同的计算机，使程序员能够将精力集中在应用程序上，而不是计算机的复杂性上。数年来，人们开发了各种各样的高级语言，如FORTRAN、BASIC、Pascal、COBOL、C、C++和Java等。但不管是哪种高级语言写的源程序必须经过“翻译”生成机器语言程序，才能被计算机执行。上一页下一页返回4.3程序设计语言在应用领域中，执行速度是关键，为了优化内存和指令序列的使用，现代程序员有时仍然要使用汇编语言和机器语言。4.3.2翻译通过上面的介绍，我们对什么是低级语言和什么是高级语言应该有了一定的了解，而且应该认识到计算机只能读懂机器语言。为了在计算机上运行程序，使用高级语言编写的程序必须被翻译成目标计算机的机器语言。将一种语言的程序转换成另一种语言的程序的过程就是翻译。高级语言程序被称为源程序，被翻译成的机器语言程序称为目标程序。高级语言的翻译有两种方式：解释和编译。上一页下一页返回4.3程序设计语言1.解释解释方式是按照源程序中语句的执行顺序，逐条翻译语句并立即予以执行。即由事先置入计算机中的解释程序将高级语言源程序的语句逐条翻译成机器指令，翻译一条执行一条，直到程序全部翻译执行完为止。解释程序几乎是实时生成结果，因为它是逐条读取并执行指令，这种实时性尤其适用于高度交互式应用程序。事实上，JavaScript就是按照这种方式执行的。然而解释型语言的缺点是执行速度慢。解释程序必须花时间翻译每一条语句，因而每条语句在执行时都会有短暂延迟。上一页下一页返回4.3程序设计语言解释方式类似于不同语言的口译工作。假设将一段演讲从中文翻译成英文，通常是演讲者说一句中文，翻译人员立即将它翻译成英文。即使演讲者后来说了同样的话，翻译人员还是要重新翻译。实际上，翻译人员变成了原始演讲者的替身，在短暂延迟之后，用不同的语言重复演讲者的话，这种方式的优点是提供了实时翻译。2.编译编译方式是先由编译程序把整个源程序翻译成目标程序，然后再由计算机执行目标程序，得到计算结果。编译的特点是“一劳永逸”，整个源代码一旦编译完毕，今后就可以在任何时候多次执行目标代码。而且一旦编译完毕，程序的执行速度就非常快。上一页下一页返回4.3程序设计语言C++这类语言就是用编译程序翻译的。然而，编译型语言的缺点是，程序员每次修改了程序，都必须花时间重新编译整个程序。编译方式类似于不同语言的笔译工作。我们同样将一段演讲从中文翻译成英文，如果没有必要提供同声传译，翻译人员可以在事后翻译全部讲话，并生成一个英文录音。虽然这种方式不如同声传译及时，而且更费时，但它一个重要的优点是，一旦翻译完毕，听众就可以听很多遍，不用重复翻译。另外，听众在听讲话内容时不必经受延迟。上一页返回4.4程序质量的基本要求和程序设计风格4.4.1对源程序质量的基本要求对源程序最基本的质量要求是正确性和可靠性。早期的计算机运行速度慢、存储容量小，因此早期的程序以时间和空间的效率作为程序好坏的重要标准。随着计算机性能的与日俱增，时间和空间的矛盾得到很大的改善。而随着软件规模的越来越大，使用计算机的人越来越多，如何方便地使用软件和如何提高开发和维护软件的效率成了主要的问题。因此，除了一些对时间和空间有很高要求的软件仍把效率作为程序质量的重要标准外，现在人们更注重软件的易使用性、易维护性和可移植性。（1）易使用性。下一页返回4.4程序质量的基本要求和程序设计风格易使用性主要指操作是否简便以及用户花在学习使用软件上的时间多少。（2）易维护性。易维护性包括易测试性和易修改性。由于一个软件有较长的使用寿命，当软件需要维护时，维护人员往往不是原先的开发人员，原先的开发人员可能已不在，即使原先的开发人员还在，也可能由于相隔时间太久，对原来开发的软件细节已遗忘。因此在开发软件时，应使程序具有良好的程序结构，易于阅读，便于理解。同时当软件在使用过程中发现了隐藏的错误时，程序应是容易测试的，以便及时找出错误。上一页下一页返回4.4程序质量的基本要求和程序设计风格当需要改正错误或程序功能需要扩充或完善时，程序应是易于修改的。（3）可移植性。可移植性是指程序从某一环境移植到另一环境的能力。采用信息隐藏原则和尽量不用语言标准文本以外的语句都有利于程序的移植。4.4.2程序设计的基本风格1.源程序中的内部文档在源程序中可包含一些内部文档，以帮助阅读和理解源程序。内部文档主要包括选择标识符的名字、适当的注解和程序的视觉组织。（1）选择标识符的名字。上一页下一页返回4.4程序质量的基本要求和程序设计风格①选择含义明确的名字，使它能正确提示标识符所代表的实体。②名字不宜太长，太长会增加打字量，且容易出错。③不用相似的名字，如EM、EN、EMM、ENN、EMN，因为相似的名字容易混淆，不易发现错误。④不用关键字作标识符。⑤同一个名字不要有多个含义。⑥名字中避免使用易混淆的数字，如数字0与字母O，数字1与字母I，数字2与字母Z等。（2）注解。上一页下一页返回4.4程序质量的基本要求和程序设计风格源程序中的注解用来帮助人们理解程序。注解可分为序言性注解和功能性注解。序言性注解位于每个模块的起始部分，它主要描述下列问题：①模块的功能。②模块的接口，包括调用格式、所有参数的解释、该模块需调用的其他子模块名。③重要的局部变量，包括用途、约束和限制条件。④开发历史，包括模块的设计者、评审者和评审日期、修改日期以及对修改的描述。上一页下一页返回4.4程序质量的基本要求和程序设计风格功能性注解嵌在源程序体内，主要描述程序段的功能，书写功能性注解时应注意下列问题：①注解要正确，错误的注解比没有注解更坏。②为程序段作注解，而不是为每个语句作注解。③使用空行或缩进，使注解和代码容易区分。④注解应提供一些从程序本身难以得到的信息，而不是重复语句。（3）程序的视觉组织。通过在程序中添加一些空格、空行和缩进等技巧，帮助人们从视觉上看清程序的结构。上一页下一页返回4.4程序质量的基本要求和程序设计风格通过缩进技巧，使if语句的结构一目了然。在多重嵌套的情况下，这种缩进技巧不仅能看清嵌套的层次，而且容易发现遗漏endif的错误。2.数据说明在程序中都有数据说明，为使数据说明便于理解，可采用下列书写数据说明的风格：（1）显式地说明一切变量。有些程序设计语言（如FORTRAN）允许变量不作显式说明。用这种语言书写的程序往往由于缺省了类型说明而产生计算时的误差。因此提倡显式地说明一切变量。上一页下一页返回4.4程序质量的基本要求和程序设计风格（2）数据说明的次序应规范化，如先常量说明，再简单类型说明，然后构造类型说明。（3）当多个变量出现在同一个说明语句中时，变量名应按字母顺序排序，以便于查找。（4）在定义一个复杂的数据结构时，应通过注解来说明该数据结构的特点。3.语句构造在编码过程中，最主要的工作就是书写语句。有关书写语句的原则有几十种，总体来说都是希望每条语句尽可能简单明了，能直截了当地反映程序员的意图。下面列出一些常用的规则：上一页下一页返回4.4程序质量的基本要求和程序设计风格（1）不要在同一行中写多个语句。（2）避免使用测试条件“非”。（3）避免使用复杂的条件测试。（4）使用括号清晰地表达出逻辑表达式和算术表达式的运算次序。（5）利用添加空格来清晰地表示语句的成分。（6）尽量不用或少用GOTO语句。（7）尽量不用或少用标准文本以外的语句，以利于提高可移植性。（8）尽量只采用三种基本控制结构来编写程序。4.输入和输出上一页下一页返回4.4程序质量的基本要求和程序设计风格输入和输出是每个程序都不可缺少的部分。在编写输入和输出程序段时可考虑下列原则：（1）对所有的输入数据都进行校验，以确保输入数据的有效性。（2）检查输入项的重要组合的合理性，如金额等于单价乘以数量。（3）保持输入格式的简单和操作的简单。（4）使用数据结束标记（如数据文件结束标记），而不应要求用户指定输入数据的个数。上一页下一页返回4.4程序质量的基本要求和程序设计风格（5）明确提示交互式输入的请求，详细说明可用的选择或边界值。（6）当程序设计语言对输入格式有严格要求时，应保持输入格式与输入语句要求的一致性。（7）设计良好的输出报表。上一页返回4.5程序设计中的计算思维程序设计是将分析和解决问题的思维活动转化成计算机程序的过程。因此以计算思维的方式分析和解决问题是程序设计成败的关键所在。4.5.1穷举和迭代在现实生活中要想解决一些问题，进行反复试验是很有用的。比如说数学中最小公倍数的问题，如果知道最小公倍数的定义，我们可以使用试验的方法来找到答案。假如要求出两个数a和b的最小公倍数，可以从这两个数中较大的那个数开始（假设a较大），先判断a是否是两个数的公倍数，如果不是再考察a+1是不是公倍数、a+2是不是公倍数……如此进行下去找到的第一个满足a、b两个数的公倍数一定是最小公倍数。下一页返回4.5程序设计中的计算思维这就是计算机程序设计中使用的穷举法。了解到这种方法的解题思路后，有人会认为这种方法虽然能有效地解决问题，但是在现实中人工去实施还是不太合适，因为要耗费大量的时间。但是计算机不一样，作为一种计算工具，它进行重复试验的速度是很快的，这样的穷举对于计算机来说是很容易的。因此在程序设计过程中，不能以常识认为穷举是一种“笨方法”，而是充分利用计算机的计算速度、具有计算思维的好方法。迭代与穷举的基本原理类似，也是充分利用了计算机的计算速度快这一特点。4.5.2排序上一页下一页返回4.5程序设计中的计算思维几乎所有计算机中的序列都是被排过序的。电子邮件列表按照日期排序，最新的邮件被放置在最顶端；播放器中的歌曲按照名字或歌手名排列在一起，以便你快速查找到最喜欢的那首；文件名则往往是按照字母顺序排列的。那么计算机是如何进行排序的呢？为了理解计算机的排序原理，我们可以先来考虑一下在现实生活中是如何排序的。在一次考试结束后，同学们把试卷都交上来了，老师为了便于评阅试卷和登记成绩，需要将试卷按学生的学号顺序排列好。假如你被老师安排来完成这项试卷排序的工作，你会怎么做呢？上一页下一页返回4.5程序设计中的计算思维最通常的做法是：首先从这摞试卷中随便取出一份放在一边作为排好序的试卷，然后再从未排序的试卷中依次移出每张试卷将它们插入排好序的试卷中的正确位置（这里所说的正确位置是指插入后始终保持这摞整理好的试卷是按学号排好序的）。每成功插入一次，即意味着未排序的试卷减少了，排好序的试卷增加了，直到所有试卷被完全排列好。扑克牌玩家通常也是使用这种方法来理牌的。我们把这种方法称为直接插入排序法，这也是最简单的排序方法。该算法的重点在于如何将数值放入左侧序列（即已排好序的序列）中的正确位置上，而不是去考虑该在右侧的序列要挑出哪一个数值。上一页下一页返回4.5程序设计中的计算思维另一种常用的排序方法也可以这样去做。考虑10个小朋友排队，