《计算机算法》刘汉英编著|(epub+azw3+mobi+pdf)电子书下载

图书名称：《计算机算法》

【作　者】刘汉英编著

【丛书名】普通高等教育“十三五”规划教材

【页 数】 209

【出版社】 北京：冶金工业出版社 , 2020.04

【ISBN号】978-7-5024-8504-7

【价 格】39.90

【分 类】电子计算机-算法理论-高等学校-教材

【参考文献】 刘汉英编著. 计算机算法. 北京：冶金工业出版社, 2020.04.

图书封面：

图书目录：

《计算机算法》内容提要：

本书介绍了算法的基本概念以及枚举、递推、递归、贪心法、回溯、动态规划、模拟等常用算法。对每一个算法，通过实例详细介绍算法的实施步骤，从问题描述、设计到实现、分析。所有问题都给出了CC++语言的算法实现，在VC++6.0环境下调试通过。本书大多实例代码均为作者设计，叙述详细具体，具有参考价值。

《计算机算法》内容试读

算法概述

扫一扫免费获取代码及课件

1.1算法的基本概念

1.1.1算法定义

算法是解题方案准确而完整的描述，是一系列解决问题的清晰指令。算法对于一定规范的输入，在有限的时间内能获得所要求的结果。

1.1.2算法的要素

1.1.2.1数据对象的运算和操作

在计算机系统中，基本的运算和操作有以下四类：

(1)算术运算，包括加、减、乘、除等：

(2)逻辑运算，包括与、或、非等；

(3)关系运算，包括等于、不等于、大于、小于、大于等于、小于等于等

(4)数据传输，包括输入、输出、赋值等。

1.1.2.2算法的控制结构

算法中各操作之间的执行顺序称为算法的控制结构，有三种基本控制结构：

(1)顺序结构。各运算和操作按先后顺序执行。

(2)选择结构（分支结构）。根据条件选择相应的运算或操作执行，放弃另一部分运算或操作的执行。

(3)循环结构。有规律的重复计算处理，根据循环判定条件对一组运算或操作重复执行多次。

有关控制结构的知识，本书不作详细叙述，请参看参考文献[1]。

1.1.2.3数据结构

算法处理的对象是数据。数据之间的逻辑关系、数据的存储方式与处理方式是数据结构。在Visual C++下运行以下程序：1 #include

//c111

2 void main()

4

inta=10000000000000:

5

int b=1;

6

printf("%d\n",a+b)

1

程序运行结果是1316134913，并不正确。原因是变量a的值超出了取值范围。将程序修改为：

】算法概述

2

1 #include

/cl_12

2 void main()3

4

int64a=10000000000000:

5

int b=1;6

printf("%164d\n",a+b);

7

将变量a改为有符号64位整数数据类型，可以获得正确的结果。

一个算法需要在某个特定的计算工具上执行，算法的执行受到计算工具的限制，数据需选择合理的存储方式。

1.1.3算法的特征

一个算法，应该具有以下五个基本特征。

(1)有穷性。算法必须在执行有限个步骤之后终止，不能终止的过程不是算法。在数学中，圆周率π可以用式(1-1)计算，当n→∞时为π的值，这不是计算机算法。算法和计算公式是有差别的，在设计一个算法时，根据精度只取有限项。

m=4-+-…+3+5

2n-1

(1-1)）

算法要在有限的时间内完成，超过了有限的时间将是没有意义的。

(2)确定性。算法的每一个步骤都有确切的定义，不允许抽象、含糊、模棱两可。在任何情况下，算法只有唯一的执行路径，对相同的输人只能得出相同的输出。不能让计算机执行“将a加上b或c”之类的操作。

(3)可行性。算法的每一个步骤都可以分解为基本的可执行的操作步骤。在算法中不能出现“除以0”之类的运算。

(4)输入项。一个算法有0个或多个输入，0个输入是算法自身进行了初始化。算法的执行结果往往与初始数据有关，不同的输入会有不同的输出结果，输入规模是指输人量的多少。

(5)输出项。一个算法有一个或多个输出，可以是屏幕输出，也可以是打印输出等。没有输出的算法是没有意义的。

1.2算法的描述方法

描述算法可以有多种方法。

1.2.1自然语言

自然语言是人们日常生活中使用的语言。用自然语言描述的算法通俗易懂，但容易产生歧义，当算法中循环和分支较多时，很难清晰地表示出来。

1.2.2流程图

流程图是用一些图框表示各种操作。用图形表示算法，直观形象、易于理解。但流程

1.3常用算法

图对流程线的使用没有严格限制，设计者可以不受限制地使流程随意地转来转去，使阅读者很难理解算法的逻辑。

1.2.3盒图

盒图将全部算法写在一个矩形框内，适于结构化程序设计，比文字描述直观、形象易于理解，但是盒图不易扩充，不易于描述大型复杂的算法。

1.2.4问题分析图（PAD图)

PAD图表示的算法是一个二维树形结构图，层次感强、嵌套明确，有清晰的控制流

程，但其录入不方便。

1.2.5伪代码

伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法的一种工具，不用图形符号，书写方便、格式紧凑、易于理解，但读者不易调试验证算法。

1.2.6计算机语言

用计算机语言表示的算法是计算机能够执行的算法，即程序。本书采用C/C++语言描

述算法。C/C++语言功能丰富、表达能力强、使用灵活方便、应用面广，既能描述算法所

处理的数据结构，又能描述算法过程，是大学阶段学习计算机程序设计的首选语言。：

有关各种描述方法的使用，本书不作详细叙述，请参看参考文献[1]，[2]。

1.3常用算法

计算机算法是对计算机上执行的计算过程的具体描述，以下介绍工程上常用的几种算法设计方法，在实际应用时，各种方法之间往往存在一定的联系。

1.3.1枚举

枚举，又称为穷举法、蛮力法、列举法，其基本思想是，根据提出的问题遍历所有可能的情况，用问题中给定的条件检查哪些是需要的，哪些是不需要的。枚举常用于解决“是否存在”“有多少可能”等类型的问题。

枚举的特点是算法比较简单，但当枚举的可能情况较多时，执行算法的工作量将会很大。

枚举是计算机算法中的一个基本算法，常与其他算法联合使用。

1.3.2递推

递推是从已知的初始条件出发，逐步推出中间结果和最后结果，一般初始条件由问题本身给定或通过对问题的分析确定，递推关系式通过对问题的分析与归纳得到。

递推算法常用在数值计算中。

】算法概述

1.3.3递归

递归是直接或间接地调用自己，分为直接递归和间接递归两种。工程实际中的许多问题和数学中的许多函数是用递归来定义的

有些问题，既可以使用递推算法，也可以使用递归算法来实现；递归算法比递推算法清晰易读、结构简练；设计递归算法比设计递推算法容易，但递归算法的执行效率比较低。

1.3.4贪心法

贪心法，又称贪婪算法，通过一系列的选择来构造问题的解，每一步都是对当前部分解的一个扩展，直到获得问题的完整解。

贪心法的每一个决策的选择都是最佳的，但这种启发式策略并不总能产生最优解，是

一种着眼于局部的简单而适应范围有限的策略。

1.3.5回溯

通过对问题的分析，找出一个解决问题的线索，沿着这个线索试探。若试探成功，得到问题的解，若试探失败，则逐步回退，换别的路线再试探。回溯法有递归回溯和迭代回潮，适用于问题规模较大、候选解比较多的问题求解。

1.3.6动态规划

动态规划将待求解问题分解成若干个相互联系的阶段，在每一个阶段做出决策，形成决策序列。动态规划主要用于求解多阶段决策最优化问题。

动态规划算法设计比较复杂，常与递推或递归联合起来使用。

1.3.7模拟

在自然界和日常生活中，有些问题很难建立确切的数学模型，可以试用模拟进行探索求解，计算机模拟分为决定性模拟和随机模拟。

以上简要介绍了几种常用算法，具体的设计过程请参看后面具体章节。

1.4算法设计方法

1.4.1面向对象方法

面向对象方法引入了对象、消息、继承、封装、抽象、多态性等机制。

在面向对象方法中，对象具有与现实世界的某种对应关系，可以利用这种关系对问题进行分析。

1.4.2结构化方法

面向对象方法在20世纪80年代已经得到了很大的发展，在计算机科学、信息科学、

1.5算法设计步骤

系统科学和产业界得到了有效的应用，显示出其强大的生命力，但在面向对象设计方法中仍要用到面向过程的知识，面向过程的程序设计通常由结构化程序设计实现。本书采用结构化设计方法。任何简单的或复杂的算法都可以由顺序、选择、循环三种结构组合而成，这三种结构是结构化程序设计必须采用的结构。

结构化方法的要点是：自顶向下、逐步求精、模块化设计、结构化编码。

自顶向下是从问题的全局出发，把一个复杂的问题分解成若干个子问题，然后对每个子问题再进行分解，直到每一个子问题都容易解决为止。

逐步求精是用模块描述子问题，再把每个模块的功能逐步分解细化为一系列具体步骤，直到能用某个基本控制语句实现。

模块化是把大程序按功能划分为若干个小程序，由一个主控模块和若干个子模块组

成，子模块可以再继续划分。在C语言中，主控模块是主函数，子模块是子函数，子函数

也可以调用子函数。

结构化编码是将设计好的算法用计算机语言表示，编译运行。

结构化设计方法的设计原则是：使每个模块尽可能只执行一个功能，每个模块用过程语句调用其他模块，模块间传送的参数作数据用，模块间共用的信息尽量少。

1.5算法设计步骤

算法是一系列解决问题的步骤的集合，在设计算法时，一般要经历以下过程。

1.5.1分析并建立数学模型

对于一个待求解的问题，首先要准确地理解问题，这是算法设计的关键，注意以下问题：

(1)问题所用术语的准确定义；

(2)列出已知（隐含）信息、条件，输入是什么；

(3)问题要求得到的结果、输出是什么，精度要求是什么；

(4)求解结果所需要的中间结果：

(5)建立模型，确定输人与输出的关系，探索由输人和已知条件得到结果所需要的计算步骤；

(6)设计测试用例，既包括合理的输入，也包括不合理的输入。

1.5.2算法设计

(1)选择合适的数据组织形式。选择数据的存储方式，确定问题中的信息、结果等用什么方式存储（简单变量、数组、链表、树、图），需要多少数组，规模多大，不同的数据结构将导致差异很大的算法。

(2)选择算法。考虑学过的方法是否可以借鉴，什么算法适合于此问题。

(3)描述算法。将设计的求解步骤记录下来，即描述算法。

(4)确定算法的正确性。用一个具体的输入实例手工执行算法，即跟踪算法，发现算法中的逻辑错误。

1算法概述

1.5.3实现算法、程序测试及调试

用计算机语言实现算法，用测试用例测试及调试程序。

1.5.4分析算法

研究算法的特性和好坏，分析算法效率，估算算法所需的内存空间和运行时间，比较同一类问题的不同算法

1.5.5结果整理和文档编制

整理算法设计结果，编制文档。编制文档的目的是让其他人理解编写的程序代码，用注释的方法在代码中标明一些信息，记录算法的流程图、程序测试用例、结果等。

1.6对算法的评价

一个问题可以用不同的算法解决，算法的质量优劣有以下几个质量指标：

(1)正确性。算法的正确性是评价一个算法优劣的最重要标准。算法对一切合法的输人数据应该能得到满足要求的结果。

(2)可读性。算法的可读性即可理解性，是一个算法可供阅读的容易程度。算法主要是给人们阅读和交流的，应该易于理解：难懂的算法易于隐藏错误且难于调试和修改。

(3)健壮性。算法的健壮性又称为容错性、稳健性、鲁棒性，是指一个算法对不合理数据输入的反应和处理能力。算法应该充分考虑可能的异常情况，返回一个错误表示或提示。

(4)时间复杂度。算法的时间复杂度是执行算法所需要的计算工作量，具体分析方法见1.7节

(5)空间复杂度。算法的空间复杂度是指算法需要消耗的存储空间，具体分析方法见

1.7节。

1.7算法的复杂度分析

算法的复杂度有时间复杂度和空间复杂度，算法分析是对算法执行时间和所需要空间的估算，定量地给出运行算法所需的时间数量级和空间数量级。通常可以利用实验对比和数学方法来分析算法。

(1)实验对比是在相同的环境下，比较能解决同一问题的算法哪个速度更快，哪个性能更优。实验对比必须在算法实现后才能进行。

(2)数学方法是在逻辑推理的基础上判断算法的优劣。通常用渐近分析的方法来分析算法的时间性能。渐近分析是忽略具体机器、编程语言和编译器的影响，只关注在输入规模增大时，算法运行时间的增长趋势。渐近分析可以降低算法分析的难度，从数量级的角度评价算法的效率。

···试读结束···