搜档网
当前位置:搜档网 › 算法设计与分析9

算法设计与分析9

顺序算法分析的基本方法

算法分析的原则

正确性、工作量、占用空间

简单性、最优性(问题复杂度)

简单性最优性问题复杂度

算法分析的实例

搜索有序表

排序

选择

1

算法分析的原则

正确性

概念在给定有效输入后, 算法经过有限时间的计

在给定有效输入后算法经过有限时间的计

算并产生正确的答案, 就称算法是正确的.

正确性证明的内容:

正确性证明的内容

方法的正确性证明——算法思路的正确性.

证明系列与算法的工作对象有关的引理定

证明一系列与算法的工作对象有关的引理、定

理以及公式.

程序的正确性证明——证明所给出的一系列指令

程序的正确性证明证明所给出的系列指令确实做了所要求的工作.

2

--时间复杂性分析计量工作量的标准: 对于给定问题,该算法所执行工作量时间复杂性分析

的基本运算的次数.

基本运算的选择:根据问题选择适当的基本运算问题

基本运算

在表中查找x 比较实矩阵相乘实数乘法排序

比较遍历二叉树置指针

两种时间复杂性:

3

最坏情况下的复杂性W (n )平均情况下的复杂性A (n )

占用空间--空间复杂性分析

空间复杂性分析

两种占用:

存储程序和输入数据的空间

存储中间结果或操作单元所占用空间--额外空间

影响空间的主要因素:

存储程序的空间一般是常数(和输入规模无关)

存储程序的空间般是常数(和输入规模无关)

输入数据空间为输入规模O(n)

空间复杂性考虑的是额外空间的大小

如果额外空间相对于输入规模是常数, 称为原地

工作的算法.

工作的算法

两种空间复杂性:

最坏情况下的复杂性和平均情况下的复杂性.

4

简单性

含义:算法简单,程序结构简单.

好处:容易验证正确性

便于程序调试

便程序试

简单的算法效率不定高. 要在保证

简单的算法效率不一定高要在保证

一定效率的前提下力求得到简单的算法.

5

最优性

含义指求解某个问题的算法类中效率最高的算法

两种最优性

设A是解某个问题的算法如果最坏情况下最优:设 A 是解某个问题的算法, 如果

在解这个问题的算法类中没有其它算法在最坏情况下的时间复杂性比 A 在最坏情况下的时间复杂性低, 则称

A在最坏情况下的时间复杂性低则称

A 是解这个问题在最坏情况下的最优算法.

平均情况下最优:设 A 是解某个问题的算法, 如果

设是解某个问题的算法如果

在解这个问题的算法类中没有其它算法在平均情况下的时间复杂性在均情的时间复杂性低则称

时间复杂性比 A 在平均情况下的时间复杂性低, 则称

A 是解这个问题在平均情况下的最优算法.

6

寻找最优算法的途径

设计算法A, 求W(n).相当于给出最坏情况下的一个上界.

寻找函数F(n), 使得对任何算法都存在个规模为n 的输

)使得对任何算法都存在一个规模为n

入并且该算法在这个输入下至少要做F(n)次基本运算. 相

当于对问题给出最坏情况下所需基本运算次数的个下界.当于对问题给出最坏情况下所需基本运算次数的一个下界如果W(n)=F(n), 则A是最优的.

)

如果W(n)>F(n), A不是最优的或者F(n)的下界过低.

改进A或设计新算法A’使得W’(n)

重新证明新下界F’(n)使得F’(n)>F(n).

)

重复以上两步,最终得到W’(n) = F’(n)为止.

7

例1在n个不同的数中找最大的数基本运算: 比较

基本运算比较

算法findmax

输入数组L, 项数n≥1

输出L中的最大项MAX

1. MAX←L(1);i←2;

2. while i≤n do

3. if MAX

4. i←i+1;

行3的比较进行n-1次, 故W(n) = n-1.

8

问题类复杂度

定理

在n n 个数的数组中找最大的数, 并以比较

作为基本运算的算法类中的任何算法最坏情

次较

况下至少要做n-1 次比较.

,

证因为MAX是唯一的, 其它的n-1个数必

须在比较后被淘汰. 一次比较至多淘汰一个数,

所以至少需要n 1 次比较.

-1

结论:findmax 算法是最优算法.

9

下界证明法判定树

下界证明法一:判定树

?判定树:作为某个算法类的模型,根据算法类的性质给出判定树作为某个算法类的模型根据算法类的性质给出判定树的构造规则

–棵判定树对应个算法

一棵判定树对应一个算法

–一片树叶(或到某个结点的一条路径)代表一个输入

–从根到某片树叶的路径代表算法对这个输入的工作量

–树深代表最坏情况的工作量,平均路径长度代表平均工作量

?算法类的最坏情况下时间复杂度下界:所有的树中深度最算法类的最坏情况下时间复杂度下界所有的树中深度最浅的树的树深.

算法类的平均情况下时间复杂度下界所有的树中平均深?算法类的平均情况下时间复杂度下界:所有的树中平均深度最浅的树的树深.

10

下界证明法二:构造最坏输入任意给定一个算法A,A对于任意输入x 都存在一个确定的操作序列τ

?τ中的操作分成两类:

–决定性的:能够对确定输出结果提供有效信息

–非决定性的:对确定结果没有帮助的冗余操作

?A构造某个输入实例x,使得A对x的根据算法

操作序列τ包含尽量多的非决定性操作.

?给出冗余操作+必要的操作的计数公式

11

下界证明法三:归约

条件

?已知问题Q最坏情况下时间复杂度下界为F(n),即求解Q 的任何算法A 最坏情况的时间≥F(n)

?需要确定问题P 的算法类最坏情况下的时间复杂度下界

方法

?Q 算法A,A调用任意解P 的算法B(复杂度p(n)).

设计解Q P

(n)= t1(n)+p(n)+t2(n):t1为把Q 的实例I 转换到P 时间为T

A

实例f(I) 的时间,t

为把P 的解s转换成Q 的解的时间)的时间P Q

2

?若t1(n),t2(n)=O(p(n)),|f(I)|=O(n),则T A(n)=Θ(p(n)) p(n)=Θ(T A(n))=Ω(F(n))

结论

P至少与Q一样难

样难

12

算法分析的实例

搜索有序表

顺序搜索、二分搜索

最优性的分析

排序

快速排序与归并排序、堆排序

快速排序与归并排序堆排序

最优性的分析

选择

选择最大、选最大和最小、选第二大、选中位数

最优性分析

13

搜索有序表

问题: 按递增顺序排列的数组L, 项数n ≥1. 数x

如果x 在L 中, 输出x 的下标; 否则输出0

L

算法1 顺序搜索

算法1顺序搜索

输入: L, x

输出: j

:j

1. j←1

2. while j≤n and L(j)≠x do j←j+1

2while n and do+1

3. if j>n then j←0

分析:设x 在L中每个位置和空隙的概率都是1/(2n+1) W(n)=n

A(n)=[(1+2+...+n)+n(n+1)]/(2n+1)≈3n/4.

14

二分法搜索

算法3 二分搜索

算法3二分搜索

1. k←1;m←n

2while

2. while k≤m do

3. j←?(k+m)/2?

4. if x L(j) then return

4if=)then return

5. if x

6. else k←j+1

6else

7. j←0

复杂度W(n) = 1+W(?n/2?)n>1

W(1) = 1

()

15

判定树

设A是个搜索算法, 对于给定输入规模n, A的棵判定是一个搜索算法,,的一棵判定

树是一棵二叉树, 其结点被标记为1, 2, ... , n, 且标记规则:

是:

1. 根据算法A,首先与x 比较的L 的项的下标标记为树根.

2. 假设某结点被标记为i,

(1) i 的左儿子是当x

的下标;i 的右儿子是当x>L(i)时,算法A下一步与x比较的项的下标

.

(2) 若xL(i) 时

算法A 停止, 则i 没有右儿子.

A i

19

实例

n =15改进顺序搜索算法和二分搜索算法的判定树,n 15

1

8

2

3

4

12

14

15

2

6

10

14

给定输入1

3579111315

, 算法A 将从根开始, 沿一条路径前进, 直到某个结点为止. 所执行的基本运算次数是这条路径的结点+1

20

个数. 最坏情况下的基本运算次数是树的深度+1.

中科院陈玉福计算机算法设计与分析期末简答题答案

1. 贪心算法和动态规划算法有什么共同点和区别?它们都有那些优势和劣势? 共通点:动态规划和贪心算法都是一种递推算法,均有局部最优解来推导全局最优解 区别:贪心算法中,作出的每步贪心决策都无法改变,每一步的最优解一定包含上一步的 最优解,而上一部之前的最优解则不作保留。 动态优化算法,全局最优解中一定包含某个局部最优解,但不一定包含前一个局部最优解,因此需要记录之前的所有最优解 动态规划算法利用子问题重叠性质,对每一个子问题只计算一次,将其解保存在一个表格中。不同的子问题个数随着输入问题的规模呈多项式增长,因此,动态规划算法通常只需要多项式时间,从而获得较高的解题效率。但它需要计算之前所有情况花费,更加耗费空间。 贪心算法所作的选择依赖于以往所作过的选择,但决不依赖于将来的选择,这使得算法在编 码和执行过程中都有一定的速度优势。贪心算法是只是找局部最优解,不一定是全局最优解。 2. 试比较回溯法与分枝限界算法,分别谈谈这两个算法比较适合的问题? 二者都是在解空间树里搜索问题的可靠解或最优解,但是搜索的方式不同,回溯法采用深 度优先的方式,直到达到问题的一个可行解,或经判断沿此路径不会达到问题的可行解或最优解时,停止向前搜索,并沿原路返回到该路径上最后一个还可扩展的节点,然后,从该节点出发朝新的方向纵深搜索。分枝限界法采用的是宽度优先的方式,它将活节点存放在一个特殊的表中,其策略是,在扩展节点处,首先生成其所有的儿子节点,将那些导致不可行解或导致非最优解的儿子节点舍弃,其余儿子节点加入活节点表中,然后,从活节点中取出一个节点作为当前扩展节点,重复上述节点中扩展过程。可以看出,回溯法一般用于求问题的一个可行解,而分枝限界可以用于求出问题的所有可行解。 3. 何谓最优化原理?采用动态规划算法必须满足的条件是什么?动态规划算法是通过什 么问题的什么特性提高效率的? 一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。最优子结构性质,子问题重叠性质是计算模型采用动态规划算法求解的两个基本要素。 动态规划算法利用子问题重叠性质,对每一个子问题只计算一次,将其解保存在一个表格中。不同的子问题个数随着输入问题的规模呈多项式增长,因此,动态规划算法通常只需要多项式时间,从而获得较高的解题效率 4. 什么是多项式时间算法? 若存在一个常数C,使得对于所有n>=0,都有|f(n)| <= C*|g(n)|,则称函数f(n)是O(g(n))。时间复杂度是O(p(n))的算法称为多项式时间算法,这里p(n)是关于n的多项式。 时间复杂度为O(nlog(n))、O(n^3)的算法都是多项式时间算法,时间复杂度为O(n^log(n))、O(n!)、O(2^n)的算法是指数时间算法。 一个优化问题如果已经找到了多项式时间算法,则称该问题为多项式时间可解问题,并 将这类问题的集合记为P,因此多项式时间可解问题就称为P类问题。。

算法设计与分析考试题及答案

算法设计与分析考试题 及答案 Company number:【WTUT-WT88Y-W8BBGB-BWYTT-19998】

一、填空题(20分) 1.一个算法就是一个有穷规则的集合,其中之规则规定了解决某一特殊类型问题的一系列运算,此外,算法还应具有以下五个重要特性:确定性 有穷性 可行性 0个或多个输入 一个或多个输出 2.算法的复杂性有时间复杂性 空间复杂性之分,衡量一个算法好坏的标准是 时间复杂度高低 3.某一问题可用动态规划算法求解的显着特征是 该问题具有最优子结构性质 4.若序列X={B,C,A,D,B,C,D},Y={A,C,B,A,B,D,C,D},请给出序列X 和Y 的一个最长公共子序列{BABCD}或{CABCD}或{CADCD } 5.用回溯法解问题时,应明确定义问题的解空间,问题的解空间至少应包含一个(最优)解 6.动态规划算法的基本思想是将待求解问题分解成若干_子问题 ,先求解_子问题 ,然后从这些子问题 的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法 背包问题的回溯算法所需的计算时间为o(n*2n ) ,用动态规划算法所需的计算时间为o(min{nc,2n }) 9.动态规划算法的两个基本要素是最优子结构 _和重叠子问题 10.二分搜索算法是利用动态规划法实现的算法。 二、综合题(50分) 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质;②构造最优值的递归关系表达式; ③最优值的算法描述;④构造最优解; 2. 流水作业调度问题的johnson 算法的思想。 ①令N 1={i|a i =b i };②将N 1中作业按a i 的非减序排序得到N 1’,将N 2中作业按b i 的非增序排序得到N 2’;③N 1’中作业接N 2’中作业就构成了满足Johnson 法则的最优调度。 3. 若n=4,在机器M1和M2上加工作业i 所需的时间分别为a i 和b i ,且 (a 1,a 2,a 3,a 4)=(4,5,12,10),(b 1,b 2,b 3,b 4)=(8,2,15,9)求4个作业的最优调度方案,并计算最优值。 步骤为:N1={1,3},N2={2,4}; N 1’={1,3}, N 2’={4,2}; 最优值为:38 4. 使用回溯法解0/1背包问题:n=3,C=9,V={6,10,3},W={3,4,4},其解空间有长度为3的0-1向量组成,要求用一棵完全二叉树表示其解空间(从根出发,左1右0),并画出其解空间树,计算其最优值及最优解。 解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1), (1,1,0),(1,1,1)}。 解空间树为: 该问题的最优值为:16 最优解为:(1,1,0) 5. 设S={X 1,X 2,···,X n }是严格递增的有序集,利用二叉树的结点来存储S 中的元素,在表示S 的二叉搜索树中搜索一个元素X ,返回的结果有两种情形,(1)在二叉搜索树的内结点中找到X=X i ,其概率为b i 。(2)在二叉搜索树的叶结点中确定X ∈(X i ,X i+1),其概率为a i 。在表示S 的二叉搜索树T 中,设存储元素X i 的结点深度为C i ;叶结点(X i ,X i+1)的结点深度为d i ,则二叉搜索树T 的平均路长p 为多少假设二叉搜索树T[i][j]={X i ,X i+1,···,X j }最优值为m[i][j],W[i][j]= a i-1+b i +···+b j +a j ,则m[i][j](1<=i<=j<=n)递归关系表达式为什么 .二叉树T 的平均路长P=∑=+n i 1 Ci)(1*bi +∑=n j 0 dj *aj

算法设计与分析实验报告

本科实验报告 课程名称:算法设计与分析 实验项目:递归与分治算法 实验地点:计算机系实验楼110 专业班级:物联网1601 学号: 05 学生姓名:俞梦真 指导教师:郝晓丽 2018年 05月 04 日 实验一递归与分治算法 实验目的与要求

1.进一步熟悉C/C++语言的集成开发环境; 2.通过本实验加深对递归与分治策略的理解和运用。 实验课时 2学时 实验原理 分治(Divide-and-Conquer)的思想:一个规模为n的复杂问题的求解,可以划分成若干个规模小于n的子问题,再将子问题的解合并成原问题的解。 需要注意的是,分治法使用递归的思想。划分后的每一个子问题与原问题的性质相同,可用相同的求解方法。最后,当子问题规模足够小时,可以直接求解,然后逆求原问题的解。 实验题目 1.上机题目:格雷码构造问题 Gray码是一个长度为2n的序列。序列无相同元素,每个元素都是长度为n的串,相邻元素恰好只有一位不同。试设计一个算法对任意n构造相应的Gray码(分治、减治、变治皆可)。 对于给定的正整数n,格雷码为满足如下条件的一个编码序列。 (1)序列由2n个编码组成,每个编码都是长度为n的二进制位串。 (2)序列中无相同的编码。 (3)序列中位置相邻的两个编码恰有一位不同。 2.设计思想: 根据格雷码的性质,找到他的规律,可发现,1位是0 1。两位是00 01 11 10。三位是000 001 011 010 110 111 101 100。n位是前n-1位的2倍个。N-1个位前面加0,N-2为倒转再前面再加1。 3.代码设计: 归式,就是如何将原问题划分成子问题。 2.递归出口,递归终止的条件,即最小子问题的求解,可以允许多个出口。 3.界函数,问题规模变化的函数,它保证递归的规模向出口条件靠拢(2)递归与非递归之间如何实现程序的转换? (3)分析二分查找和快速排序中使用的分治思想。 答: 1.一般根据是否需要回朔可以把递归分成简单递归和复杂递归,简单递归一般就是根据递归式来找出递推公式(这也就引申出分治思想和动态规划)。 2.复杂递归一般就是模拟系统处理递归的机制,使用栈或队列等数据结构保存回朔点来求解。 (4)分析二次取中法和锦标赛算法中的分治思想。 二次取中法:使用快速排序法中所采用的分划方法,以主元为基准,将一个表划分为左右两个子表,左子表中的元素均小于主元,右子表中的元素均大于主元。主元的选择是将表划分为r

算法设计与分析试卷(2010)

算法设计与分析试卷(A 卷) 一、 选择题 ( 选择1-4个正确的答案, 每题2分,共20分) (1)计算机算法的正确描述是: B 、D A .一个算法是求特定问题的运算序列。 B .算法是一个有穷规则的集合,其中之规则规定了一个解决某一特定类型的问题的运算序列。 C .算法是一个对任一有效输入能够停机的图灵机。 D .一个算法,它是满足5 个特性的程序,这5个特性是:有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 (2)影响程序执行时间的因素有哪些? C 、D A .算法设计的策略 B .问题的规模 C .编译程序产生的机器代码质量 D .计算机执行指令的速度 (3)用数量级形式表示的算法执行时间称为算法的 A A .时间复杂度 B .空间复杂度 C .处理器复杂度 D .通信复杂度 (4)时间复杂性为多项式界的算法有: A .快速排序算法 B .n-后问题 C .计算π值 D .prim 算法 (5)对于并行算法与串行算法的关系,正确的理解是: A .高效的串行算法不一定是能导出高效的并行算法 B .高效的串行算法不一定隐含并行性 C .串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 (6)衡量近似算法性能的重要标准有: A A .算法复杂度 B .问题复杂度 C .解的最优近似度 D .算法的策略 (7)分治法的适用条件是,所解决的问题一般具有这些特征: ABCD A .该问题的规模缩小到一定的程度就可以容易地解决; B .该问题可以分解为若干个规模较小的相同问题; C .利用该问题分解出的子问题的解可以合并为该问题的解 D .该问题所分解出的各个子问题是相互独立的。 (8)具有最优子结构的算法有: A .概率算法 B .回溯法 C .分支限界法 D .动态规划法 (9)下列哪些问题是典型的NP 完全问题: A .排序问题 B .n-后问题 C .m-着色问题 D .旅行商问题 (10)适于递归实现的算法有: C A .并行算法 B .近似算法 C .分治法 D .回溯法 二、算法分析题(每小题5分,共10分) (11)用展开法求解递推关系: (12)分析当输入数据已经有序时快速排序算法的不足,提出算法的改进方案。 ???>+-==1 1)1(211)(n n T n n T

算法设计与分析第2版 王红梅 胡明 习题答案

精品文档习题胡明-版)-王红梅-算法设计与分析(第2答案 1 习题)—1783Leonhard Euler,17071.图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉(提 出并解决了该问题。七桥问题是这样描述的:北区一个人是否能在一次步行中穿越哥尼斯堡(现东区在叫加里宁格勒,在波罗的海南岸)城中全部岛区的七座桥后回到起点,且每座桥只经过一次,南区是这条河以及河上的两个岛和七座桥的图1.7 1.7 七桥问题图草图。请将该问题的数据模型抽象出来,并判断此问题是否有解。 七桥问题属于一笔画问题。 输入:一个起点 输出:相同的点一次步行1,经过七座桥,且每次只经历过一次2,回到起点3,该问题无解:能一笔画的图形只有两类:一类是所有的点都是偶点。另一类是只有二个奇点的图形。)用的不是除法而是减最初的欧几里德算法2.在欧几里德提出的欧几里德算法中(即法。请用伪代码描述这个版本的欧几里德算法 1.r=m-n r=0 循环直到2.m=n 2.1 n=r 2.2 r=m-n 2.3 m 输出3 .设计算法求数组中相差最小的两个元素(称为最接近数)的差。要求分别给出伪代3++描述。C码和 采用分治法// //对数组先进行快速排序在依次比较相邻的差//精品文档. 精品文档 #include using namespace std; int partions(int b[],int low,int high) { int prvotkey=b[low]; b[0]=b[low]; while (low=prvotkey)

计算机算法设计与分析期末考试复习题

1、二分搜索算法是利用( A )实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是( A )。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是( A )的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、最长公共子序列算法利用的算法是( B )。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 5. 回溯法解TSP问题时的解空间树是( A )。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6.下列算法中通常以自底向上的方式求解最优解的是( B )。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是(C )。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是(D )。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是( A )。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、实现最长公共子序列利用的算法是( B )。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法11.下面不是分支界限法搜索方式的是( D )。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 12.下列算法中通常以深度优先方式系统搜索问题解的是( D )。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的( B )。 A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解14.广度优先是( A )的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15.背包问题的贪心算法所需的计算时间为( B )。

算法设计与分析考试题及答案

1.一个算法就是一个有穷规则的集合,其中之规则规定了解决某一特殊类型问题的一系列运算,此外,算法还应具有以下五个重要特性:_________,________,________,__________,__________。 2.算法的复杂性有_____________和___________之分,衡量一个算法 好坏的标准是______________________。 3.某一问题可用动态规划算法求解的显著特征是 ____________________________________。 4.若序列X={B,C,A,D,B,C,D},Y={A,C,B,A,B,D,C,D},请给出序列X 和Y的一个最长公共子序列_____________________________。 5.用回溯法解问题时,应明确定义问题的解空间,问题的解空间至少应包含___________。 6.动态规划算法的基本思想是将待求解问题分解成若干____________,先求解___________,然后从这些____________的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为_____________。 8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。 9.动态规划算法的两个基本要素是___________和___________。 10.二分搜索算法是利用_______________实现的算法。 二、综合题(50分) 1.写出设计动态规划算法的主要步骤。 2.流水作业调度问题的johnson算法的思想。

算法设计与分析第2版 王红梅 胡明 习题答案

习题1 1. 图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉(Le on har d Eul er,1707 —1783)提出并解决了该问题。七桥问题就是这样描述的:一个人就是否能在一次步行中穿越哥尼斯堡(现在叫加里宁格勒,在波罗的海南岸)城中全部的七座桥后回到起点,且每座桥只经 过一次,图1、7就是这条河以及河上的两个岛 与七座桥的草图。请将该问题的数据模型抽象 出来,并判断此问题就是否有解。 七桥问题属于一笔画问题。 输入:一个起点 输出:相同的点 1, 一次步行 2, 经过七座桥,且每次只经历过一次 3, 回到起点 该问题无解:能一笔画的图形只有两类:一类就是所有的点都就是偶点。另一类就是只有二个奇点的图形。 2、在欧几里德提出的欧几里德算法中(即最初的欧几里德算法)用的不就是除法而就是减法。请用伪代码描述这个版本的欧几里德算法 1、r=m-n 2、循环直到r=0?2、1 m =n 2、2 n=r 2、3 r=m-n ?3 输出m 3.设计算法求数组中相差最小的两个元素(称为最接近数)的差。要求分别给出伪代码与C ++描述。 //采用分治法 //对数组先进行快速排序 //在依次比较相邻的差 #inc lud e <iostream> usin g n ames pac e std; in t pa rtion s(int b[],int l ow,int hi gh) { int pr votkey=b[lo w]; b [0]=b[lo w]; 图1、7 七桥问题

while (low<high) { while(low=prvotkey) --high; b[low]=b[high]; while (low

《算法设计与分析》实验一

学号1607070212 《算法设计与分析》 实验报告一 学生姓名张曾然 专业、班级16软件二班 指导教师唐国峰 成绩 计算机与信息工程学院软件工程系 2018 年9 月19 日

实验一:递归策略运用练习 一、实验目的 本次实验是针对递归算法的算法设计及应用练习,旨在加深学生对该算法原理的理解,提高学生运用该算法解决问题的能力。 二、实验步骤与要求 1.实验前复习课程所学知识以及阅读和理解指定的课外阅读材料; 2.学生独自完成实验指定内容; 3.实验结束后,用统一的实验报告模板编写实验报告。 4.提交说明: (1)电子版提交说明: a 需要提交Winrar压缩包,文件名为“《算法设计与分析》实验一_学号_姓名”, 如“《算法设计与分析》实验一_09290101_张三”。 b 压缩包内为一个“《算法设计与分析》实验一_学号_姓名”命名的顶层文件夹, 其下为两个文件夹,一个文件夹命名为“源程序”,另一个文件夹命名为“实验 报告电子版”。其下分别放置对应实验成果物。 (2)打印版提交说明: a 不可随意更改模板样式。 b 字体:中文为宋体,大小为10号字,英文为Time New Roman,大小为10号 字。 c 行间距:单倍行距。 (3)提交截止时间:2018年10月10日16:00。 三、实验项目 1.运用递归策略设计算法实现下述题目的求解过程。 题目列表如下: 【必做题】 (1)运动会开了N天,一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚,第二天发金牌2枚加剩下的七分之一枚,第3天发金牌3枚加剩下的七分之一枚,以后每天都照此办理。到了第N天刚好还有金牌N枚,到此金牌全部发完。编程求N和M。 (2)国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份,然后给第一个儿子一份,再加上剩余财产的1/10;给第二个儿子两份,再加上剩余财产的1/10;……;给第i 个儿子i份,再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱,孰不知国王是“一碗水端平”的。请用程序回答,老国王共有几个儿子?财产共分成了多少份?

算法设计与分析试卷及答案

湖南科技学院二○年学期期末考试 信息与计算科学专业年级《算法设计与分析》试题 考试类型:开卷试卷类型:C卷考试时量:120分钟 题号一二三四五总分统分人 得分 阅卷人 复查人 一、填空题(每小题3 分,共计30 分) 1、用O、Ω与θ表示函数f与g之间得关系______________________________。 2、算法得时间复杂性为,则算法得时间复杂性得阶为__________________________。 3、快速排序算法得性能取决于______________________________。 4、算法就是_______________________________________________________。 5、在对问题得解空间树进行搜索得方法中,一个活结点最多有一次机会成为活结点得就是_________________________。 6、在算法得三种情况下得复杂性中,可操作性最好且最有实际价值得就是_____情况下得时间复杂性。 7、大Ω符号用来描述增长率得下限,这个下限得阶越___________,结果就越有价值。。 8、____________________________就是问题能用动态规划算法求解得前提。 9、贪心选择性质就是指____________________________________________________________________________________________________________________。 10、回溯法在问题得解空间树中,按______________策略,从根结点出发搜索解空间树。 二、简答题(每小题10分,共计30分) 1、试述回溯法得基本思想及用回溯法解题得步骤。 2、有8个作业{1,2,…,8}要在由2台机器M1与M2组成得流水线上完成加工。每个作业加工得顺序都就是先在M1上加工,然后在M2上加工。M1与M2加工作业i所需得时间分别为: M110 2 8 12 6 9414

算法设计与分析第2版王红梅胡明习题答案

算法设计与分析(第2版)-王红梅-胡明-习题 答案 习题1 1. 图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉(Leonhard Euler ,1707—1783) 提出并解决了该问题。七桥问题是这样描述的:一个人是否能在一次步行中穿越哥尼斯堡(现在叫加里宁格勒,在波罗的海南岸)城中全部的七座桥后回到起点,且每座桥只经过一次, 图 1.7是这条河以及河上的两个岛和七座桥的 草图。请将该问题的数据模型抽象出来,并判 断此问题是否有解。 七桥问题属于一笔画问题。 输入:一个起点 输出:相同的点 1, 一次步行 2, 经过七座桥,且每次只经历过一次 3, 回到起点 该问题无解:能一笔画的图形只有两类:一类是所有的点都是偶点。另一类是只有二个奇点的图形。 2.在欧几里德提出的欧几里德算法中(即最初的欧几里德算法)用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法 1.r=m-n 2.循环直到r=0 2.1 m=n 2.2 n=r 2.3 r=m-n 3 输出m 3.设计算法求数组中相差最小的两个元素(称为最接近数)的差。要求分别给出伪代码和C ++描述。 //采用分治法 //对数组先进行快速排序 //在依次比较相邻的差 图1.7 七桥问题

#include using namespace std; int partions(int b[],int low,int high) { int prvotkey=b[low]; b[0]=b[low]; while (low=prvotkey) --high; b[low]=b[high]; while (low

算法设计与分析期末试题答案解析

1、用计算机求解问题的步骤: 1、问题分析 2、数学模型建立 3、算法设计与选择 4、算法指标 5、算法分析 6、算法实现 7、程序调试 8、结果整理文档编制 2、算法定义:算法是指在解决问题时,按照某种机械步骤一定可以得到问题结果的处理过程 3、算法的三要素 1、操作 2、控制结构 3、数据结构 算法具有以下5个属性: 有穷性:一个算法必须总是在执行有穷步之后结束,且每一步都在有穷时间内完成。 确定性:算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口 可行性:一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。 输入:一个算法有零个或多个输入,这些输入取自于某个特定对象的集合。 输出:一个算法有一个或多个输出,这些输出同输入有着某些特定关系的量。 算法设计的质量指标: 正确性:算法应满足具体问题的需求; 可读性:算法应该好读,以有利于读者对程序的理解;

健壮性:算法应具有容错处理,当输入为非法数据时,算法应对其作出反应,而不是产生莫名其妙的输出结果。 效率与存储量需求:效率指的是算法执行的时间;存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。 经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法 迭代法 基本思想:迭代法也称“辗转法”,是一种不断用变量的旧值递推出新值的解决问题的方法。 解题步骤:1、确定迭代模型。根据问题描述,分析得出前一个(或几个)值与其下一个值的迭代关系数学模型。 2、建立迭代关系式。迭代关系式就是一个直接或间接地不断由旧值递推出新值的表达式,存储新值的变量称为迭代变量 3、对迭代过程进行控制。确定在什么时候结束迭代过程,这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况:一种是所需的迭代次数是个确定的值,可以计算出来;另一种是所需的迭代次数无法确定。对于前一种情况,可以构建一

算法设计与分析课程期末试卷-A卷(自测 )

华南农业大学期末考试试卷(A卷) 2008学年第一学期考试科目:算法分析与设计 考试类型:(闭卷)考试时间:120分钟 学号姓名年级专业 一、选择题(20分,每题2分) 1.下述表达不正确的是。 A.n2/2 + 2n的渐进表达式上界函数是O(2n) B.n2/2 + 2n的渐进表达式下界函数是Ω(2n) C.logn3的渐进表达式上界函数是O(logn) D.logn3的渐进表达式下界函数是Ω(n3) 2.当输入规模为n时,算法增长率最大的是。 A.5n B.20log2n C.2n2D.3nlog3n 3.T(n)表示当输入规模为n时的算法效率,以下算法效率最优的是。A.T(n)= T(n – 1)+1,T(1)=1 B.T(n)= 2n2 C.T(n)= T(n/2)+1,T(1)=1 D.T(n)= 3nlog2n 4.在棋盘覆盖问题中,对于2k×2k的特殊棋盘(有一个特殊方块),所需的L型骨 牌的个数是。 A.(4k– 1)/3 B.2k /3 C.4k D.2k 5.在寻找n个元素中第k小元素问题中,若使用快速排序算法思想,运用分治算法 对n个元素进行划分,应如何选择划分基准?下面答案解释最合理。A.随机选择一个元素作为划分基准 B.取子序列的第一个元素作为划分基准 C.用中位数的中位数方法寻找划分基准 D.以上皆可行。但不同方法,算法复杂度上界可能不同

6. 现在要盖一所邮局为这9个村庄服务,请问邮局应该盖在 才能使到邮局到这9个村庄的总距离和最短。 A .(4.5,0) B .(4.5,4.5) C .(5,5) D .(5,0) 7. n 个人拎着水桶在一个水龙头前面排队打水,水桶有大有小,水桶必须打满水, 水流恒定。如下 说法不正确? A .让水桶大的人先打水,可以使得每个人排队时间之和最小 B .让水桶小的人先打水,可以使得每个人排队时间之和最小 C .让水桶小的人先打水,在某个确定的时间t 内,可以让尽可能多的人打上水 D .若要在尽可能短的时间内,n 个人都打完水,按照什么顺序其实都一样 8. 分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题,分 别解决子问题,最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题 。 A .问题规模相同,问题性质相同 B .问题规模相同,问题性质不同 C .问题规模不同,问题性质相同 D .问题规模不同,问题性质不同 9. 对布线问题,以下 是不正确描述。 A .布线问题的解空间是一个图 B .可以对方格阵列四周设置围墙,即增设标记的附加方格的预处理,使得算法简化对边界的判定 C .采用广度优先的标号法找到从起点到终点的布线方案(这个方案如果存在的话)不一定是最短的 D .采用先入先出的队列作为活结点表,以终点b 为扩展结点或活结点队列为空作为算法结束条件 10. 对于含有n 个元素的子集树问题,最坏情况下其解空间的叶结点数目为 。 A .n! B .2n C .2n+1-1 D . ∑=n i i n 1 !/! 答案:DACAD CACCB

算法设计与分析C++语言描述(陈慧南版)课后答案

第一章 15P 1-3. 最大公约数为1。快1414倍。 主要考虑循环次数,程序1-2的while 循环体做了10次,程序1-3的while 循环体做了14141次(14142-2循环) 若考虑其他语句,则没有这么多,可能就601倍。 第二章 32P 2-8.(1)画线语句的执行次数为 log n ????。(log )n O 。划线语句的执行次数应该理解为一格整体。 (2)画线语句的执行次数为 111 (1)(2) 16 j n i i j k n n n ===++= ∑∑∑。3()n O 。 (3 )画线语句的执行次数为 。O 。 (4)当n 为奇数时画线语句的执行次数为 (1)(3) 4 n n ++, 当n 为偶数时画线语句的执行次数为2 (2)4 n +。2()n O 。 2-10.(1)当1n ≥时,225825n n n -+≤,所以,可选5c =,01n =。 对于0n n ≥,22 ()5825f n n n n =-+≤,所以,22 582()n n n -+=O 。 (2)当8n ≥时,2222 582524n n n n n -+≥-+≥,所以,可选4c =,08n =。对于0n n ≥, 22()5824f n n n n =-+≥,所以,22582()n n n -+=Ω。 (3)由(1)、(2)可知,取14c =,25c =,08n =,当0n n ≥时,有22212582c n n n c n ≤-+≤,所以 22582()n n n -+=Θ。 2-11. (1) 当3n ≥时,3 log log n n n <<,所以()20log 21f n n n n =+<,3 ()log 2g n n n n =+>。可选21 2 c = ,03n =。对于0n n ≥,()()f n cg n ≤,即()(())f n g n =O 。注意:是f (n )和g (n )的关系。 (2)当4n ≥时,2 log log n n n <<,所以2 2 ()/log f n n n n =<,2 2 ()log g n n n n =≥。可选1c =,04n =。对于0n n ≥,2 ()()f n n cg n <≤,即()(())f n g n =O 。 (3)因为log log(log )()(log ) n n f n n n ==,()/log log 2n g n n n n ==。当4n ≥时,log(log )()n f n n n =≥,

算法设计与分析试卷及答案.doc

湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析》 试题 考试类型:开卷 试卷类型: C 卷 考试时量: 120 分钟 题号 一 二 三 四 五 总分 统分人 得 分 阅卷人 一、填空题(每小题 3 分,共计 30 分) 1. 用 O 、Ω和θ表示函数 f 与 g 之间的关系 ______________________________ 。 f n n lo g n g n log n 1, n 1 2. 算法的时间复杂性为 f (n) n ,则算法的时间复杂性的阶 8 f (3n / 7) n, 2 为__________________________ 。 3. 快速排序算法的性能取决于 ______________________________ 。 4. 算法是 _______________________________________________________ 。 5. 在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的 是_________________________ 。 6. 在算法的三种情况下的复杂性中, 可操作性最好且最有实际价值的是 _____情况下的时间复杂性。 7. 大Ω符号用来描述增长率的下限,这个下限的阶越 ___________,结果就越有价值。 。 8. ____________________________ 是问题能用动态规划算法求解的前提。 9. 贪心选择性质是指 ________________________________________________________ ____________________________________________________________ 。

《算法设计与分析》复习题(汇编)

填空 1.直接或间接地调用自身的算法称为 递归 。 2.算法的复杂性是 算法效率 的度量,是评价算法优劣的重要依据。 3.以广度优先或以最小耗费方式搜索问题解的算法称为 分支限界法 。 4.回溯法解题的显著特点是在搜索过程中动态产生问题的解空间。在任何时刻,算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n),则回溯法所需的计算空间通常为 o(h(n)) 。 5.人们通常将问题的解决方案分为两大类:一类是可以通过执行若干个步骤就能得出问题 6.算法就是一组有穷的 规则 ,它们规定了解决某一特定类型问题的 一系列运算 。 7.在进行问题的计算复杂性分析之前,首先必须建立求解问题所用的计算模型。3个基本计算模型是 随机存取机、 随机存取存储程序机 、 图灵机 。 8.快速排序算法的性能取决于 划分的对称性 。 9.计算机的资源最重要的是 内存 和 运算 资源。因而,算法的复杂性有时间 和 空间 之分。 10.贪心算法总是做出在当前看来 最优 的选择。也就是说贪心算法并不从整体最优考虑,它所做出的选择只是在某种意义上的 局部最优解 。 11.许多可以用贪心算法求解的问题一般具有2个重要的性质: 最优子结构的 性质和 贪心选择的 性质。 12.常见的两种分支限界法为 队列式 和 优先队列式 。 13.解决0/1背包问题可以使用动态规划、回溯法和分支限界法,其中需要排序的是 回溯法 ,不需要排序的是 动态规划和分支限界法 。 14.f ( n ) = 6 × 2n + n 2,f(n)的渐进性态f ( n ) = O ( 2^n )。 15.对于含有n 个元素的排列树问题,最好情况下计算时间复杂性为 ,最坏情况下计算时间复杂性为 n! 。 16.在忽略常数因子的情况下,O 、Ω和Θ三个符号中, Θ 提供了算法运行时间的一个上界。 17.回溯法的求解过程,即在问题的解空间树中,按 深度优先 策略从根结点出发搜索解空间树。 18.分支限界法的求解过程,即在问题的解空间树中,按 广度优先 策略从根结点出发搜索解空间树。 19.多项式10()m m A n a n a n a =+ ++的上界为 2^n 。 20.用分支限界法解布线问题时,对空间树搜索结束的标志是 活结点表为空 。 21.使用回溯法进行状态空间树裁剪分支时一般有两个标准:约束条件和目标函数的界,N 皇后问题和0/1背包问题正好是两种不同的类型,其中同时使用约束条件和目标函数的界进

算法设计与分析(第2版)王红梅胡明习题答案

习题1 1. 图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉(Leonhard Euler ,1707—1783)提出并解决了该问题。七桥问题是这样描述的:一个人是否能在一次步行中穿越哥尼斯堡(现 在叫加里宁格勒,在波罗的海南岸)城中全部的七座桥后回到起点,且每座桥只经过一次, 图是这条河以及河上的两个岛和七座桥的草 图。请将该问题的数据模型抽象出来,并判断此问题是否有解。 七桥问题属于一笔画问题。 输入:一个起点 输出:相同的点 1, 一次步行 2, 经过七座桥,且每次只经历过一次 3, 回到起点 该问题无解:能一笔画的图形只有两类:一类是所有的点都是偶点。另一类是只有二个奇点的图形。 2.在欧几里德提出的欧几里德算法中(即最初的欧几里德算法)用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法 =m-n 2.循环直到r=0 m=n n=r r=m-n 3输出m 3.设计算法求数组中相差最小的两个元素(称为最接近数)的差。要求分别给出伪代码和C++描述。 编写程序,求n 至少为多大时,n 个“1”组成的整数能被2013整除。 #include using namespace std; int main() { double value=0; 图 七桥问题

for(int n=1;n<=10000 ;++n) { value=value*10+1; if(value%2013==0) { cout<<"n至少为:"< using namespace std; int main () { double a,b; double arctan(double x);圣经上说:神6天创造天地万有,第7日安歇。为什么是6天呢任何一个自然数的因数中都有1和它本身,所有小于它本身的因数称为这个数的真因数,如果一个自然数的真因数之和等于它本身,这个自然数称为完美数。例如,6=1+2+3,因此6是完美数。神6天创造世界,暗示着该创造是完美的。设计算法,判断给定的自然数是否是完美数 #include using namespace std; int main() { int value, k=1; cin>>value; for (int i = 2;i!=value;++i) { while (value % i == 0 ) { k+=i;有4个人打算过桥,这个桥每次最多只能有两个人同时通过。他们都在桥的某一端,并且是在晚上,过桥需要一只手电筒,而他们只有一只手电筒。这就意味着两个人过桥后必须有一个人将手电筒带回来。每个人走路的速度是不同的:甲过桥要用1分钟,乙过桥要用2分钟,丙过桥要用5分钟,丁过桥要用10分钟,显然,两个人走路的速度等于其中较慢那个人的速度,问题是他们全部过桥最少要用多长时间 由于甲过桥时间最短,那么每次传递手电的工作应有甲完成 甲每次分别带着乙丙丁过桥 例如: 第一趟:甲,乙过桥且甲回来

南京邮电大学算法设计实验报告——动态规划法

实验报告 (2009/2010学年第一学期) 课程名称算法分析与设计A 实验名称动态规划法 实验时间2009 年11 月20 日指导单位计算机学院软件工程系 指导教师张怡婷 学生姓名丁力琪班级学号B07030907 学院(系) 计算机学院专业软件工程

实验报告 实验名称动态规划法指导教师张怡婷实验类型验证实验学时2×2实验时间2009-11-20一、实验目的和任务 目的:加深对动态规划法的算法原理及实现过程的理解,学习用动态规划法解决实际应用中的最长公共子序列问题。 任务:用动态规划法实现求两序列的最长公共子序列,其比较结果可用于基因比较、文章比较等多个领域。 要求:掌握动态规划法的思想,及动态规划法在实际中的应用;分析最长公共子序列的问题特征,选择算法策略并设计具体算法,编程实现两输入序列的比较,并输出它们的最长公共子序列。 二、实验环境(实验设备) 硬件:计算机 软件:Visual C++

三、实验原理及内容(包括操作过程、结果分析等) 1、最长公共子序列(LCS)问题是:给定两个字符序列X={x1,x2,……,x m}和Y={y1,y2,……,y n},要求找出X和Y的一个最长公共子序列。 例如:X={a,b,c,b,d,a,b},Y={b,d,c,a,b,a}。它们的最长公共子序列LSC={b,c,d,a}。 通过“穷举法”列出所有X的所有子序列,检查其是否为Y的子序列并记录最长公共子序列并记录最长公共子序列的长度这种方法,求解时间为指数级别的,因此不可取。 2、分析LCS问题特征可知,如果Z={z1,z2,……,z k}为它们的最长公共子序列,则它们一定具有以下性质: (1)若x m=y n,则z k=x m=y n,且Z k-1是X m-1和Y n-1的最长公共子序列; (2)若x m≠y n且x m≠z k,则Z是X m-1和Y的最长公共子序列; (3)若x m≠y n且z k≠y n,则Z是X和Y的最长公共子序列。 这样就将求X和Y的最长公共子序列问题,分解为求解较小规模的问题: 若x m=y m,则进一步分解为求解两个(前缀)子字符序列X m-1和Y n-1的最长公共子序列问题; 如果x m≠y n,则原问题转化为求解两个子问题,即找出X m-1和Y的最长公共子序列与找出X 和Y n-1的最长公共子序列,取两者中较长者作为X和Y的最长公共子序列。 由此可见,两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列,具有最优子结构性质。 3、令c[i][j]保存字符序列X i={x1,x2,……,x i}和Y j={y1,y2,……,y j}的最长公共子序列的长度,由上述分析可得如下递推式: 0 i=0或j=0 c[i][j]= c[i-1][j-1]+1 i,j>0且x i=y j max{c[i][j-1],c[i-1][j]} i,j>0且x i≠y j 由此可见,最长公共子序列的求解具有重叠子问题性质,如果采用递归算法实现,会得到一个指数时间算法,因此需要采用动态规划法自底向上求解,并保存子问题的解,这样可以避免重复计算子问题,在多项式时间内完成计算。 4、为了能由最优解值进一步得到最优解(即最长公共子序列),还需要一个二维数组s[][],数组中的元素s[i][j]记录c[i][j]的值是由三个子问题c[i-1][j-1]+1,c[i][j-1]和c[i-1][j]中的哪一个计算得到,从而可以得到最优解的当前解分量(即最长公共子序列中的当前字符),最终构造出最长公共子序列自身。

相关主题