第9章问题求解与算法基础大学计算机高等教育出版社

大学计算机Contents.目录第9章问题求解与算法基础9.1问题求解的基本步骤9.2算法及其描述9.3程序设计语言与程序设计方法9.4基于Python的程序实现9.5问题求解的常用算法

9.1问题求解的基本步骤第9章问题求解与算法基础程序设计要经过以下4个基本步骤。①分析问题，确定数学模型或方法。弄清要计算机“做什么”，然后建立数学模型或考虑对数据处理的需求和方法。②设计算法，画出流程图。明确要计算机“怎么做”，把问题的数学模型或处理需求转化为计算机解题的步骤。③选择编程工具，按算法编写程序。将该算法用程序设计语言编写成程序。④调试程序，分析输出结果。运行程序，排除程序中可能的错误。

9.2算法及其描述第9章问题求解与算法基础9.2.1算法的概念1．什么是算法算法就是解决特定问题所需要的一组操作序列。欧几里德（Euclid）算法求两个正整数m和n的最大公约数问题。第1步：比较m和n这两个数，将m设置为较大的数，n为较小的数。第2步：m除以n，得到余数r。第3步：若r等于0，则n就是最大公约数，否则将n赋值给m，r赋值给n，返回到第2步。

9.2算法及其描述第9章问题求解与算法基础9.2.1算法的概念2．算法的控制结构算法有3种控制结构，即顺序结构、选择结构和循环结构。3种控制结构具有共同特点：①只有一个入口和一个出口。②结构内的每一部分都有机会被执行。③结构中无死循环。

9.2算法及其描述第9章问题求解与算法基础9.2.2算法的特性算法应具有以下5个特性。①有穷性（finiteness）。算法中执行的步骤总是有限次数的，不能无止境地执行下去。②确定性（definiteness）。算法中的每一步操作都必须具有确切的含义，不能有二义性。③有效性（effectiveness）。算法中的每一步操作必须是可执行的，并应能得到一个明确的结果。

9.2算法及其描述第9章问题求解与算法基础9.2.2算法的特性算法应具有以下5个特性。④可以有零个或多个输入。输入是指在执行算法时从用户获得数据。当然，有时是不需输入的。⑤有一个或多个输出。没有输出的算法是没有意义的。

9.2算法及其描述第9章问题求解与算法基础9.2.3算法的描述1．用流程图描述算法流程图（flowchart）是用一些几何框图、流程线和文字说明表示各种类型的操作。一般用矩形框表示进行某种处理，有一个入口，一个出口。用菱形框表示判断，有一个入口，两个出口。在框内写上简明的文字或符号表示具体的操作，用带箭头的流向线表示操作的先后顺序。

9.2算法及其描述第9章问题求解与算法基础9.2.3算法的描述2．用伪代码描述算法借助某种高级语言但又不拘泥于严格的语言规则、自上而下逐行描述算法，书写方便，格式紧凑。

9.3程序设计语言与程序设计方法第9章问题求解与算法基础9.3.1程序设计语言的分类1．机器语言机器语言（machinelanguage）是以计算机能直接识别的0或1二进制代码组成的一系列指令。用机器语言编写的程序叫机器语言程序。利用机器语言编写程序，要求程序设计人员熟记计算机的全部指令，工作量大、容易出错又不容易修改，同时所编制的程序只适用于特定的计算机系统。

9.3程序设计语言与程序设计方法第9章问题求解与算法基础9.3.1程序设计语言的分类2．汇编语言汇编语言（assemblylanguage）用容易记忆的英文单词缩写代替约定的指令。用汇编语言编写的程序，称为汇编语言源程序。将汇编语言程序翻译成机器语言程序的程序通常称为汇编程序。翻译的过程叫做汇编。汇编语言仍然与具体的计算机硬件有着密切的关系，汇编语言指令与机器语言指令基本上是一一对应的。

9.3程序设计语言与程序设计方法第9章问题求解与算法基础9.3.1程序设计语言的分类3．高级语言高级语言（higher-levellanguage）是用更接近自然语言和数学表达式的一种语言，不依赖具体机器。用高级语言编写的程序易读易记，也便于修改、调试，大大提高了编制程序的效率，也大大提高了程序的通用性。用高级语言编写的程序叫做源程序（sourceprogram）。源程序必须经过“翻译”处理，计算机才能执行。

9.3程序设计语言与程序设计方法第9章问题求解与算法基础9.3.1程序设计语言的分类3．高级语言（1）解释方式。解释方式是通过解释程序（interpreter）对源程序进行逐句翻译，翻译一句执行一句，翻译过程中并不生成可执行