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

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

【作　者】刘洪波编著

【页 数】 181

【出版社】 大连：大连海事大学出版社 , 2020.11

【ISBN号】7-5632-4054-8

【分 类】计算机算法

【参考文献】 刘洪波编著. 计算机算法. 大连：大连海事大学出版社, 2020.11.

图书目录：

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

本书介绍了计算机算法，内容涉及算法分析基础，循环与递归，算法与数据结构，算法优化的基本技巧与模型，主代法，蛮力法，贪婪法，分治法，动态规划，图搜索，启发式搜索，集合算法，自然随机启发式算法。

《计算机算法》内容试读

第1章算法概述

第1章算法概述

§1.1问题求解

1.1.1问题求解与计算机算法

有问题就需要求解，计算机算法设计与分析为问题求解提供了一条有效途径。

1.1.2计算机算法求解问题的步骤

计算机算法求解问题的步骤如下：

(1)描述问题

描述问题时需注意：①未经加工的原始表达是否明确？②问题本身提供了哪些信息？③是否有潜在的信息？④这些信息有什么用？⑤要求得到什么结果？⑥已经做了哪些假设？还需哪些假设？⑦中间结果有哪些？哪些中间结果需要记录，哪些不需要记录？⑧最终结果如何评价？

(2)建立数学模型

建立数学模型时需注意：①最适合此问题的数学模型是什么？②是否有已经解决了的类似问题可借鉴？③模型中的符号是否已明确定义？④模型是否可以转换、简化？⑤模型是否揭示了什么规律和属性？

(3)算法设计的基本结构与策略

算法设计的基本结构有：①顺序：②循环：③条件。

算法设计的策略主要有：①枚举：②随机：③迭代；④贪心；⑤分治；⑥动态规划；⑦图搜索；

⑧自然启发。

(4)算法分析

算法分析主要有：①正确性；②收敛性：③稳定性：④复杂度。

(5)算法表示

算法表示主要有：流程图（见图1.1）和伪码。

①流程图

流程图的优缺点如下：

·优点：便于考虑算法的控制流程。

·缺点：模块划分不明显：数据结构不明确。

一1

计算机算法

开始

M=0,N=0,i=1

产生01的两个随机数，分别赋给x,头

2+2≤1？否

是

M=M+1

N=N+1

i=i+1

否1>10002>

是

输出M,N

结束

图1.1流程图

②伪码

Algorithm 1 Power algorithm

Input:n≥O

>输入一个大于0的整数

Output:y x"1:y←-1

2:X←-x

3:N←n

4:while N≠0do5:if N is even then

6:X←X×X

7:N←-N/2

8:else[N is odd]9:yy×X

10:N←N-1

11:end if12:end while

伪码的优缺点如下：

·优点：书写方便：格式紧凑；数据清晰。

·缺点：可视化程度低。

-2-

第1章算法概述

(6)算法实现

需注意书写规范，做必要注释，并思考：①有哪些变量，它们是什么类型？②输出的次序和格式是什么？③需要多少数组，规模有多大？④用什么结构来组织数据？⑤所需内存容量为多少？⑥运算速度多少？如何？

面的大且测

(7)程序调试

程序调试主要有：①白盒测试，即对算法的各个分支进行测试：②黑盒测试，即检验对给定的输入是否有指定输出。

(8)文档编制

文档编制主要有：①问题描述；②模型说明；③算法表示：④算法分析；⑤规范代码；⑥测试结果；⑦使用指南。

§1.2算法基础

1.2.1算法的定义

算法就是解决目标问题的方法和步骤及其描述。

1.2.2算法的要素

算法由数据结构、控制结构、操作三要素组成。

数据结构是一门单独的课程，相关的数据结构将在本书中结合实例进行讲解。控制结构有顺序、循环、条件（或者说分支）三种基本结构。

操作主要有：①算术运算：加、减、乘、除：②关系比较：大于、小于、等于、不等于；③逻辑运算：与、或、非；④数据传送：输入、输出、赋值。

1.2.3算法的地位

算法是计算机学科中最具有方法论性质的核心概念，也被誉为计算机学科的灵魂。

1.2.4算法的特征

算法的特征主要有：①输入；②输出：③有穷性：④确定性；⑤可行性。

§1.3算法设计的基本方法

703

力y:g

算法设计的基本方法主要有：①结构化方法：②面向对象方法：③涌现法。

y:50u0

-3-

计算机算法

1.3.1结构化方法

结构化方法的指导思想是自顶向下、逐步求精，使问题分解与功能模块化。①自顶向下：将复杂且大的问题划分为较小问题，找出问题的关键和重点；②逐步求精：将复杂问题经若干步精化处理，最后细化到用三种基本结构及基本操作去描述算法。

优越性：①符合思维习惯；②层次结构清晰：③模块参数传递。

1.3.2面向对象方法

主要步骤：①在给定的抽象层次上识别类和对象；②识别这些类和对象的语义；③识别类和对象之间的关系；④实现类和对象。

优越性：①抽象化；②封装性；③多态性；④继承性；⑤重用性。

1.3.3涌现法

主要步骤：①设计简单个体；②赋予简单属性和互动规则；③在简单个体互动中探索问题解，并给出适应值。

优越性：①实现简单：②去中心化。③具有涌现性，虽然简单个体只能实现简单的任务，多个个体却能完成复杂的任务。

§1.4算法示例

影在发个

1.4.1:求两个正整数的最大公约数

(1)问题分析：两个正整数，最大公约数；

(2)数学模型：a>0,b>0的整数，求c,c能整除a,b,且a/c与b/c互质；

(3)算法设计：理解人工求解两数的最大公约数过程，通过“枚举尝试”可以“试出”a,b有哪些公约数，并将这些公约数“累乘”，就能得到最大公约数；

(4)具体设计：①用or循环枚举可能的因数，并将枚举所得的因数进行累乘；②注意到因数2在“4,8”两个数据中出现两次。所以，测试某因数是否是所给数据的因数时，应该用循环语句，而不是条件语句。

1.4.2最大公约数求解的算法

Algorithm 2 greatest common divisor

Input:int a,b

Output:c

1:c←1

—4

第1章算法概述

2:for (i=2;i<=a and i<=b;i++)do

。=,限，塘周是播d序。景

3:while a mod i =0 and b mod i=0 do

8的一粒于数年要只$日斜，西细分

4:

c←c*i

5:

a←-a/i

(

6:

b←-b/i

名清牌点果烟

7:end while

:(暖的的

8:end for

牌。现城

9:return c

1.4.3 Euclid最大公约数定理

定理1.1不失一般性，假设a>b>0,则有gcd(a,b)=gcd(b,a mod b)。证明：a>b>0,.a=kb+r,这里k,r为正整数，则r=a mod b。

假设d是a,b的一个公约数，则有dla,d1b,而r=a-b,也有dlr,因此d是(b,amodb)的公约数。

同样地，假设d是(b,a mod b)的公约数，则d1b,dIr,由于a=b+r,因此d也是(a,b)的公约数。

因此，(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等。证毕！

1.4.4 Euclid算法

Algorithm3 Euclid algorithm(辗转相除法)

Input:int a,b

Output:a

1:while b！=0do2:r←-b

21

3:

b←-a%b

4:a←r5:end while6:return a

1.4.5 Stein最大公约数原理

,

gcd(a,a)=a;

gcd(ka,b)=k·gcd(a,b),也就是最大公约数运算和倍乘运算可以交换，特殊的，当k=2时，说明两个偶数的最大公约数必然能被2整除。

有了上述规律就可以给出Stein算法，具体如下：设置a1=a,b,=b和c1=1;

-5

计算机算法

如果a,和b:都是偶数，则a1=an/2,bn1=bn/2,c+1=2c(注：乘2只要把整数左移一位即可，除以2只要把整数右移一位即可)；

如果a:是偶数，b:不是偶数，则a+1=a/2,b41=b,c1=c,(显然成立，因为2不是奇数的约数)；

如果b,是偶数，a:不是偶数，则b1=b,/2,a1=a,c1=c,(显然成立，因为2不是奇数的约数)；

如果a,和b,都不是偶数，则a1=|a-b:l,b+1=min(a,b:),c+1=c。如果a=0,b是最大公约数，算法结束；如果b=0,a是最大公约数，算法结束。

1.4.6 Stein算法

Algorithm 4 Stein algorithm1:int ged(int a,int b)2:{

3:if (a ==0)then4:return b5:end if

6:if (==0)then7:return a8:end if

9:if(a%2==0&&b%2==0)then10:return 2gcd(a >1,b >1)11:else if (a%2 ==0)then12:return gcd(a >1,b)13:else if (b%2 ==0)then14:return gcd(a,b >1)15:else

16:return ged(abs(a -b),min(a,b))17:end if18:}

算法分析：

Euclid算法与Stein算法的最大迭代次数几乎是相等的。但是，需要注意的是，对于大素数，Euclid算法求模试商的方式将使每次迭代都更复杂，Stein算法将更有优势，因为该算法抛弃除法和取模，只有整数的移位和加减法。

一6

···试读结束···