简答：
1.算法定义：
算法是一个满足下列条件的计算：
①有穷性/终止性：有限步内必须停止。/* 好算法/坏算法 */
②确定性：每一步都是严格定义和确定的动作。 /* 要严格算法语言 */
③能行性：每一个动作都能够被精确地机械执行。
④输入：有一个满足给定约束条件的输入。
⑤输出：满足给定约束条件的结果。
2.常用算法及其特点：
递归分治法，贪心算法，动态规划，回溯法等。
3.递归分治法：
基本思想：将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。
4.动态规划法：
1）适用条件：当一个优化问题可分为多个子问题，子问题的解被重复使用。具有最优子结构和重叠子问题
2）基本思想：求解每个子问题仅一次，并保存其结果，以后用到时直接存取，不重复计算，节省计算时间。
3）解题步骤：
①分析优化解的结构
②递归地定义最优解的代价
③自底向上地计算优化解的代价保存之，并获取构造最优解的信息
④根据构造最优解的信息构造优化解
4）与递归分治法的区别：动态规划法自底向上，递归分治法自顶向下
5.贪心算法：
1）基本思想
·求解最优化问题的算法包含一些列步骤
·每一步都有一组选择
·作出在当前看来最好的选择
·希望通过作出局部优化选择达到全局优化选择
2）产生优化解的条件
① 贪心选择性
②优化子结构
3）与动态规划法的比较：
·动态规划方法可用的条件
①优化子结构
②子问题相交性
③子问题空间小
·贪心算法可用的条件
①优化子结构
②贪心选择性
*可用Greedy方法时，动态规划方法可能不适用。
*可用动态规划方法时，Greedy方法可能不适用。
6. 平摊分析：
1）基本思想：
·在平摊分析中，执行一系列数据结构操作所需要时间是通过对执行的所有操作求平均而得出的。
·平摊分析可用来证明在一系列操作中，即使单一的操作具有较大的代价，通过对所有操作求平均后，平均代价还是很小的。
·平摊分析与平均情况分析不同, 不牵涉到概率。
2)常用方法: 聚集方法、会计方法、势能方法。
3）区别与联系：
（1）聚集方法为每个操作都赋予相同的平摊代价，即使序列中存在不同类型操作时也一样。会计方法和势能方法对不同类型操作赋予不同的平摊代价。
（2）势能方法不是将已预付的费用作为存储在数据结构特定对象中的存款来表示，而是表示成一种“势能”，或“势”，它在需要时可释放出来以支付后面操作的代价。势
是与整个数据结构而不是其中的个别对象发生联系的。即会计存储在个体上，势能
存储在整体上。
7. 拟阵：
1）定义：Matroid是一个序对M=(S, I)，满足：
S是一个有限非空集合;
I是非空的S子集的集族，I中的子集合称为S的独立子集合;
遗传性: 如果B∈I，A?B，则A∈I；
交换性：如果A∈I，B∈I，?A?
2）图拟阵(Graphic Matroid)的定义：
设G=(V，E)是一个无向图，由G确定的图拟阵MG=（SG，IG）定义如下：
SG是G的边集合E，IG={A | A= E’?E, (V, A)是一个森林}。
①显然，S G=E是一个有限集合.
②因为?e∈E，(v, {e})是一个森林，{e}∈I G。于是，I G是S G的非空集族。
③证M G满足遗传性。如果B∈I G，A?B，则(V，A)是一个森林。于是，A∈I G，M G满足遗传性。
④证M G满足交换性。设A∈I G，B∈I G，?A?>?B?，由图论定理可知，具有k条边的森林包括∣V∣-k棵树，于是，A包括∣V∣-?A?棵树，B包括∣V∣-?B?棵树。
由于B具有较少的树，B一定包含一个树T，T的结点在A的不相同树中。T是连通的，必包括一条边(u, v)，使得u和v在A的不相同树中。(u, v)∈A-B连接A的两棵不同的树，(u, v)可以加到A，(V, A?{(u,v)})是森林，A?{(u,v)}∈ I G，于是M G满足交换性。Matroid的性质
定义2. 设M=(S，I)是一个Matroid，A∈I。x?A称为A的一个extension如果A?{x}∈I。
定义3. 设M=(S，I)是一个Matroid，A∈I（A称为M的独立子集合）。如果A没有extension，则称A为最大独立子集合。
定理2. 一个Matroid的所有最大独立子集合都具有相同大小。
证. A是Matroid M的最大独立子集合，而且存在M的另一个独立子集合B, ?A?
定义4（加权Matroid）设M=(S，I)是一个Matroid。如果存在一个权函数W，使得?x∈S, W(x)是一个正数，则称M是加权Matroid。
*权函数W可以扩展到S的任意子集合A：w(A)=∑
∈A
x x
W) (.
加权Matroid 上的Greedy 算法
Greedy(M,W)
1 A=Φ;
2 按权w 值大小排序S ；
3 FOR ?x ∈S （按w(x)非增序）DO
4 If A ?{x}∈I /*每次选择具有最大w(x)的x — 贪心*/
5 Then A ?{x}；
6 Return A.
时间复杂性
step 2: O(|s |log |s |) step 4: O(f(|s |))
T(|s |) = O(|s |lg |s |+|s | f(|s |)
8. P ： 时间复杂度在O(n 的k 次方)多项式之内可求解 NP ： 不能在多项式时间内求解，但可验证 NPC ： NP 问题的子集 9. 回溯法：
1） 基本思想：以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一
些组合数较大的问题。 2） 解题步骤：
(1)针对所给问题，定义问题的解空间 (2)确定易于搜索的解空间；
(3)以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索. 3）子集树与排列树
子集树： 当所给的问题是从n 个元素的集合S 中找出满足某种性质的子集时，相应的
解空间树称为子集树。O (2^n )
排列树： 当所给的问题是确定n 个元素满足某种性质的排列时，相应的解空间树称为
排列树。O (n !)
10. Master 定理
定理2.4.1 设11>≥b a 和是常数，f n ()是一个函数, T n ()是定义在非负整数集上的函数()T n aT n
b f n ()()=+. T n ()可以如下求解：
⑴. 若(
)ε
-O =a b n n f log )(,ε>0是常数，则()T n n
b a
()log =θ.
⑵. 若(
)a
b n
n f log )(θ=，则()
n n
n T a
b lg )(log θ=.
⑶. 若(
)ε
+Ω=a b n
n f log )(,ε>0是常数, 且对于所有充分大的n 。 ()af n b cf n ≤(),
c>1是常数, 则T n f n ()(())=θ.
*直观地：我们用f n ()与n b a
log
比较
⑴. 若a
b n
log 大，则(
)T n n
b a
()log
=θ
⑵. 若f n ()大，则T n f n ()(())=θ ⑶. 若f n ()与n b a
log
同阶，则(
)
)lg )((lg )(log n n f n n
n T a
b θθ==.
*更进一步：
（1） 在第一种情况,f n ()不仅小于n
b a
log
，必须多项式地小于,即对于一个常数
ε>0，).()(log εn
n O n f a
b =
（2） 在第三种情况,f n ()不仅大于a
b n
log ，必须多项式地大于，即对一个常数
ε>0，)()(log εn n n f a b ?Ω=.
*注意：这三种情况并没有cover 所有可能的f n () ⑴ 情况1与情况2之间有空隙,即f n ()小于n
b a
log
,但不是多项式也小于.
⑵ 情况2与情况3也同样有间断空隙.对于这两种情况，Master 定理也无能为力. 近似算法
1. Ratio Bound
(Ratio Bound) 设A 是一个优化问题的近似算法，A 具有ratio bound p(n)，如果
max ,()**c c c c p n ?? ?
?
?≤, 其中n 是输入大小，c 是近似算法所产生的解的代价，c *是优化解
的代价。
*若问题是最大化问题，则c c ≤*
，c c c c c c *
**=???
? ??，max *若问题是最小化问题，则c c ≥*
，***=???? ?
?c c
c c c c ，max *由于c/c *
<1当且仅当c*/c >1, 近似算法的Ratio Bound 不会小
于1，即1max ≥???? ?
?**c c c c ， *求解准确优化解的优化算法的Ratio Bound 一定是1
*具有较大Ratio Bound 的近似算法给出的近似解一定比优化解坏 的多 — Ratio Bound 表示了近似算法的性能 2．相对误差
对于任意输入, 近似算法的相对误差定义为
c c c -**
, 其中c 是近似算法所产生的解
的代价，c *
是优化解的代价。 *相对误差总是非负的。
一个近似算法的相对误差界为)(n ε如果
*
*-c c c )(n ε≤。
P={L| L is a language that can be accepted by a DTM in polynomial time.}
NP={L| L is a language that can be accepted by a NDTM in polynomial time.}
证明： 1、证明P n a n
n i i d
i
d ()()=
==∑0
θ,其中a d >0
证: 由于)(}m ax{)1(0
d
d i i d
i i n O n a d n a =+≤∑=，且
a n
a n n i i d
i
d d d =∑≥=0
Ω()，
所以P n a n
n i i d
i
d ()()=
==∑0
θ
2、对于任意f(n)和g(n), f n g n ()(())=θ iff f n g n ()(())=O 而且f (n )=Ω(g (n )). 证. ? 如果f n g n ()(())=θ, 则?>>c c n 12000,,, 当n n ≥0时,
c g n f n c g n 12()()()≤≤.
显然))(()( and ))(()(n g n f n g n f O =Ω=.
?
如果f n g n ()(())=O 且f n g n ()(())=Ω,则由f n g n ()(())=O 可知，存在c n 110,,≥使得，当n n ≥1，f n c g n ()()≤1。由f (n )=Ω(g (n ))可知，
?≥c n 220,,使得当2n n ≥，)()(2n g c n f ≥。
令{}n n n 012≥max ,,则当n n ≥0，)()()(12n g c n f n g c ≤≤。
所以f n g n ()(())=θ 3、
4、 例2 证明 n n =ο()2
。
证：令c =1,n 0=1,则当n n ≥0时，20cn n ≤≤。
5. 证明 f n an bn c n ()()=++=22θ
证. 设 c n an bn c c n 12222≤++≤，令c 1=a /4, c 2=7a /4,则
a n an bn c an 47
4
222≤++≤， 令(
)
()
n b a c a 02=?max ,
。当n n >0时c n an bn c c n 12222≤++≤成立。
6. 证明f n g n f n g n n ()(())lim
()
()
=?=→∞
ο0 证.由于f (n )=o (g (n )), 对任意ε>0,存在n 0，当n n ≥0时,0≤f (n )<εg (n ),即ε≤≤
)
()
(0n g n f . 于是, 0)
()
(lim
=∞
→n g n f n
计算题: 求界限和Master 定理
1、设对于所有k ≥0,a a r k k +≤<11，求a
k
k n
=∑0
的上界.
解：a a r a a r 1010≤?≤,
a a r a a r a r 212102
≤?≤≤, a a r a a r a r 323203≤?≤≤ …… a a r a a r a r k k k k k --≤?≤≤110 于是,
a a r a r a r
k k n k k
k k ==∞=∞
∑∑∑≤==
-0
00
00
1. 2、求∑==
n
k n k
H 11
的上界 解：
??? ??++++??? ??++=∑=7161514131211111
n
k k +??? ??++++++++1511411311211111019181 …… ??∑
∑=-=+≤
n i j i
i j log 1
1
2021
??∑∑=-=≤n i j i i
log 01202
1??∑=O =+≤≤n i n n log 1)(log 1log 1
3、
k n n
k n k n
==∑∑≤=11
2
4、
a
n i
k n
=∑≤1
?{}max a k .
5、求
()k k
k 31
=∞
∑的界（例1）
解.
k k k k k r k k
+=?+=+?
?
???≤=+133
131
13112
3
1. 于是 13
211
31323131111=-?=??? ??∑=∑≤∑∞
=∞
=∞
=k
k k k
k k r a k
6、用分裂和的方法求∑=n
k k 1
的下界.
解: ()
k k k n n n k n k n k n n k n k n n
===+==+∑∑∑∑∑=+≥+≥?? ???=112211221
2
2
022Ω
7、 用Master 定理求解()T n T n
n ()=+93.
解：a b f n n ===93，，(), a
b n log ()
=θn 2
(
) f n n n b a
()log
==-O ε
, ε=1
(
)()∴==T n n
n b a
()log
θθ2
8、用Master 定理求解()T n T n ()=+231.
解：()a b f n ===13
21，，，()a
b n
log 101log 2/3===n n ,
(
)
f n n b a
()()log
===11θθ, (
)
)2(log 2log )(log
n n n
n T a
b θθ==
9. 求解()n n T
n T lg 2)(+=
解：令n m lg =，则m
n 2=, ()
m T T m m
+???? ??=2222
.令()
m T m S 2)(=则??? ??=???
? ??222m S T m
.
于是, m m S m S +??
?
??=22)(. 显然,)lg ()(m m m S O =,即()
).lg (2m m T m
θ= 由于2m =n , m =lg n , ))lg(lg (lg )(n n n T ?=θ.
10. 用Master 定理求解()T n T n
n n ()lg =+34
解：()793.03log log 4lg )(43n n n n n n f b a a
b O =====，，，
⑴ ε
+=≥=a b n n n n n f log lg )(,ε≈02.
⑵ 对所有n ,())(lg 43
4lg 434lg 43n cf n n n n n n b n
af =≤=?=,c =34
.
于是, T n f n n n ()(())(lg )==θθ 11. ()T n T n
n n ()lg =+22.
解：a b f n n n ===22，，，()lg n n a
b =log .f n n n ()lg =大于n
n b a
log
=，但
不是多项式也大于, Master 定理不使用于该T n ().
综合题：
在实际生活中，当遇到一个新的未知问题，综合运用《算法设计与分析》课程所学的知识给出你的最佳解决策略。
1）先判定问题是否可判定，若问题不可判定，则该问题无法求解； 2）若问题可判定，再进一步判定该问题是P 问题还是NP 问题； 3）若问题是P 问题，进行精确求解；
4）若问题是NP 问题，判断问题的规模n 的大小，若n 很小，设计算法精确求解； 5）若问题的规模n 很大，设计近似算法，求近似最优解。 算法设计：
1、活动安排问题： 1）算法：
3） 复杂性分析：
If 结束时间已排序 T(n)=θ(n)
If 结束时间未排序 T(n)=θ(n)+θ(nlog2n)=θ(nlog2n) 2、王教授加油问题：
s[0]表示出发地 s[m + 1]终点站 n 表示加满油的行程 refuel(s,m,n) {
return A i j }{a A then A f if s to n do for i j a A s length n s, f f f f i j
i n 87652413}{2][1)SELECT OR(-ACT IVIT Y -GREEDY )...(121←?←≥←←←←≤≤≤
for (i = m + 1; i >= 2; i --) {
s[i] = s[i] - s[i - 1]; if (s[i] > n)
{
return ("NO Solution");
} }
t = s[1]; k = 0;
for ( i = 1; i <= m; i++) {
t = t + s[i + 1];
if (t > n) {
k = k + 1;
x[k] = i; t = s[i + 1];
} } }
3、哈夫曼树：
初始：c:12b:13
f:5
e:9d:16a:45
14第一步:
01c:12b:13d:16a:45
f:5
e:9
14第二步:
25
010
1
d:16a:45
第三步:
f:5
e:9
1401c:12
b:13
25
130
a:45
第四步:c:12
b:13
25
01d:16
f:5
e:9
140130
55
101a:45
第五步:
c:12b:13
25
1
d:16
f:5
e:9
14013055
0101100
01
4、最小生成树：
5、点覆盖问题：
输入：无向图G=（V ，E ）
输出：V V '
?，满足
(1).()?∈u v E ,，u V ∈'
、v V ∈'
或{u,v }?V’
(2).V '
是满足条件(1)的最小集合。
*理论上已经证明优化结点覆盖问题是NP-完全问题。
时间复杂性 T(G)=O(|E|).
性能 定理1 Approx-Vertex-Cover 具有Ratio Bound 2
证: 令A={
(,)(,)u v u v 是算法第4步选中的边}。 若(u,v)∈A ，则所以与（u,v ）邻接的边皆从'E 中删除。于是, A 中无相邻接边.于是，第五步的每次运行增加两个结点到C ，
|C |=2|A | 设C *是优化解，C *必须覆盖A 。 由于A 中无邻接边，C *
至少包含A 中每条边的一个
结点。于是，|A |≤|C *|，|C |=2|A|≤2|C *|，即|C|/|C *
|≤2.
6、集合覆盖问题：
6.旅行商问题
五综合题
1）先判定问题是否可判定，若问题不可判定，则该问题无法求解； 2）若问题可判定，再进一步判定该问题是P 问题还是NP 问题； 3）若问题是P 问题，进行精确求解；
4）若问题是NP 问题，判断问题的规模n 的大小，若n 很小，设计算法精确求解； 5）若问题的规模n 很大，设计近似算法，求近似最优解。
《计算机算法设计与分析》习题及答案 一．选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5．下列算法中通常以自底向上的方式求解最优解的是（B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是（ C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是（ D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是（A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9．下面不是分支界限法搜索方式的是（D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 10．下列算法中通常以深度优先方式系统搜索问题解的是（D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法
11.备忘录方法是那种算法的变形。（ B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法 12．哈夫曼编码的贪心算法所需的计算时间为（B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 13．分支限界法解最大团问题时，活结点表的组织形式是（B ）。 A、最小堆 B、最大堆 C、栈 D、数组 14．最长公共子序列算法利用的算法是（B）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．实现棋盘覆盖算法利用的算法是（A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是（C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素（ D ） A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略（B ） A．递归函数 B.剪枝函数 C。随机数函数 D.搜索函数 19. （D）是贪心算法与动态规划算法的共同点。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质 20. 矩阵连乘问题的算法可由（ B ）设计实现。 A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法 21. 分支限界法解旅行售货员问题时，活结点表的组织形式是（ A ）。
算法递归典型例题 实验一：递归策略运用练习 三、实验项目 1．运用递归策略设计算法实现下述题目的求解过程。 题目列表如下： （1）运动会开了N天，一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。到了第N天刚好还有金牌N枚，到此金牌全部发完。编程求N和M。 （2）国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10；给第二个儿子两份，再加上剩余财产的1/10；……；给第i 个儿子i份，再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？ 源程序： （3）出售金鱼问题：第一次卖出全部金鱼的一半加二分之一条金鱼；第二次卖出乘余金鱼的三分之一加三分之一条金鱼；第三次卖出剩余金鱼的四分之一加四分之一条金鱼；第四次卖出剩余金鱼的五分之一加五分之一条金鱼；现在还剩下11条金鱼，在出售金鱼时不能把金鱼切开或者有任何破损的。问这鱼缸里原有多少条金鱼？ （4）某路公共汽车，总共有八站，从一号站发轩时车上已有n位乘客，到了第二站先下一半乘客，再上来了六位乘客；到了第三站也先下一半乘客，再上来了五位乘客，以后每到一站都先下车上已有的一半乘客，再上来了乘客比前一站少一个……，到了终点站车上还有乘客六人，问发车时车上的乘客有多少？ （5）猴子吃桃。有一群猴子摘来了一批桃子，猴王规定每天只准吃一半加一只（即第二天吃剩下的一半加一只，以此类推），第九天正好吃完，问猴子们摘来了多少桃子？ （6）小华读书。第一天读了全书的一半加二页，第二天读了剩下的一半加二页，以后天天如此……，第六天读完了最后的三页，问全书有多少页？ （7）日本著名数学游戏专家中村义作教授提出这样一个问题：父亲将2520个桔子分给六个儿子。分完后父亲说：“老大将分给你的桔子的1/8给老二；老二拿到后连同原先的桔子分1/7给老三；老三拿到后连同原先的桔子分1/6给老四；老四拿到后连同原先的桔子分1/5给老五；老五拿到后连同原先的桔子分1/4给老六；老六拿到后连同原先的桔子分1/3给老大”。结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子？ 四、实验过程 （一）题目一：…… 1.题目分析 由已知可得，运动会最后一天剩余的金牌数gold等于运动会举行的天数由此可倒推每一 天的金牌剩余数，且每天的金牌数应为6的倍数。 2.算法构造 设运动会举行了N天， If(i==N)Gold[i]=N; Else gold[i]=gold[i+1]*7/6+i;
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类问题。。
算法设计与分析实验报告 贪心算法 班级：2013156 学号：201315614 姓名：张春阳哈夫曼编码 代码 #include printf("\n"); for(i=0;i 算法实现题3-7 数字三角形问题 问题描述： 给定一个由n行数字组成的数字三角形，如图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。编程任务： 对于给定的由n行数字组成的数字三角形，编程计算从三角形的顶至底的路径经过的数字和的最大值。数据输入： 有文件input.txt提供输入数据。文件的第1行是数字三角形的行数n，1<=n<=100。接下来的n行是数字三角形各行的数字。所有数字在0-99之间。结果输出： 程序运行结束时，将计算结果输出到文件output.txt中。文件第1行中的数是计算出的最大值。 输入文件示例输出文件示 例 input.txt output.txt 5 30 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 源程序： #include "stdio.h" voidmain() { intn,triangle[100][100],i,j;//triangle数组用来存储金字塔数值,n表示行数 FILE *in,*out;//定义in，out两个文件指针变量 in=fopen("input.txt","r"); fscanf(in,"%d",&n);//将行数n读入到变量n中 for(i=0;i 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.以深度优先方式系统搜索问题解的算法称为_____________。 背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。 9.动态规划算法的两个基本要素是___________和___________。? 10.二分搜索算法是利用_______________实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 2.流水作业调度问题的johnson算法的思想。 算法设计与分析试卷(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 课程设计报告 课程设计名称: 算法设计与分析 系 : 三系 学生姓名: 吴阳 班级: 12软件(2)班 学号: 0311232 成绩: 指导教师: 秦川 开课时间: 年一学期 一、问题描述 1．普通背包问题 给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。选择装入的背包的物品, 使得装入背包中的物品的总价值最大, 在选择物品i装入背包时, 能够选择物品i的一部分, 而不一定要全部装入背包, 1≤i≤n。 2．0/1背包问题 给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。选择装入的背包的物品, 使得装入背包中的物品的总价值最大, 在选择物品i装入背包时, 对于每种物品i只有两种选择, 即装入背包或者不装入背包, 不能将物品装入背包多次, 也不能只装入部分的物品i。 3．棋盘覆盖问题 在一个2k x 2k个方格组成的棋盘中恰有一个方格与其它的不同称为特殊方格, 想要求利用四种L型骨牌( 每个骨牌可覆盖三个方格) 不相互重叠覆盖的将除了特殊方格外的其它方格覆盖。 二、问题分析 1．普通背包问题 对于背包问题, 若它的一个最优解包含物品j, 则从该最优解中拿出所含的物品j的那部分重量Ｗ, 剩余的将是n-1个原重物品1, 2, ······, j-1, j+1, ·····, n以及重为Ｗi－Ｗ的物品j 中可装入容量为C－Ｗ的背包且具有最大价值的物品。 2．0/1背包问题 如果当前背包中的物品的总容量是cw, 前面的k-1件物品都已经决定好是否要放入包中, 那么第k件物品是否放入包中取决于不等式 cw + wk <= M (其中, wk为第k件物品的容量, M为背包的容量)( 此即约束条件) 然后我们再寻找限界函数, 这个问题比较麻烦, 我们能够回忆一下背包问题的贪心算法, 即物品按照物品的价值/物品的体积来从大到小排列, 然后最优解为( 1, 1, 1......., 1, t, 0, 0, ......) , 其中0<=t<=1; 因此, 我们在确定第k个物品到底要不要放入的时候(在前k-1个物品已经确定的情况下), 我们能够考虑我们能够达到的最大的价值, 即我们能够经过计算只放入一部分的k物品来计算最大的价值。我们要确保当前选择的路径的最大的价值要大于我们已经选择的路径的价值。这就是该问题的限界条件。经过该条件, 能够减去很多的枝条, 大大节省运行时间。 3．棋盘覆盖问题 每次都对分割后的四个小方块进行判断, 判断特殊方格是否 算法设计与分析实验报告 姓名：888 学号：129074999 老师：许精明 实验1：杨辉三角 解法思路： 根据杨辉三角中除最外层（不包括杨辉三角底边）的数为1外，其余的数都是它肩上两个数之和这一性质，用数组输出杨辉三角。 根据杨辉三角的第n行恰好是C(n,0)~C(n,n)，可以不用数组输出，而用动态规划。这里的C表示组合。 注：由于为了便于控制输出格式，程序中的最大输出行确定的较小，但程序本身并没有错误。若要输出更多行，需要增加控制输出格式的语句。 解法一：数组 #include 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 ）。 精品文档习题胡明-版)-王红梅-算法设计与分析(第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 算法分析与设计 学习总结 题目:算法分析与设计学习总结 学院信息科学与工程学院专业2013级计算机应用技术 届次 学生姓名 学号2０１31１0６57 二○一三年一月十五日 算法分析与设计学习总结 本学期通过学习算法分析与设计课程，了解到:算法是一系列解决问题的清晰指令,代表着用系统的方法描述解决问题的策略机制。算法能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂性和时间复杂度来衡量。算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。计算机系统中的操作系统、语言编译系统、数据库管理系统以及各种各样的计算机应用系统中的软件，都必须使用具体的算法来实现。算法设计与分析是计算机科学与技术的一个核心问题。 设计的算法要具有以下的特征才能有效的完成设计要求，算法的特征有：（1）有穷性。算法在执行有限步后必须终止。(2)确定性。算法的每一个步骤必须有确切的定义。(3)输入。一个算法有0个或多个输入,作为算法开始执行前的初始值，或初始状态。(4）输出。一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。 (5)可行性。在有限时间内完成计算过程。 算法设计的整个过程,可以包含对问题需求的说明、数学模型的拟制、算法的详细设计、算法的正确性验证、算法的实现、算法分析、程序测试和文档资料的编制。算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论的算法、动态规划以及数值分析、加密算法、排序算法、检索算法和并行算法。 经典的算法主要有: 1、穷举搜索法 穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，bing从中找出那些符合要求的候选解作为问题的解。 穷举算法特点是算法简单，但运行时所花费的时间量大。有些问题所列举书来的情况数目会大得惊人，就是用高速计算机运行,其等待运行结果的时间也将使人无法忍受。我们在用穷举算法解决问题是，应尽可能将明显不符合条件的情况排除在外，以尽快取得问题的解。 2、迭代算法 迭代法是数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题（一般是解方程或方程组)的过程，为实现这一过程所使用的方法统称为迭代法。迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为ｆ(ｘ)=0,用某种数学方法导出等价的形式x=g(x),然后按以下步骤执行： （1）选一个方程的近似根，赋给变量x0。 (2)将ｘ0的值保存于变量x1，然后计算g(x1),并将结果存于变量x0。 (3）当x0与x1的差的绝对值还小于指定的精度要求时，重复步骤（２）的计算。 若方程有根，并且用上述方法计算出来的近似根序列收敛,则按上述方法求得的x0就认为是方程的根。 3、递推算法 递推算法是利用问题本身所具有的一种递推关系求问题解的一种方法。它把问题分成若干步，找出相邻几步的关系,从而达到目的。 4、递归算法 递归算法是一种直接或间接的调用自身的算法。 能采用递归描述的算法通常有这样的特征：为求解规模为ｎ的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法,分解成规模更小的问题,并从这些更小问题的解构造出规模 压缩软件课程设计书 一、问题描述： 建立一个文本文件，统计该文件中各字符频率，对各字符进行Huffman编码，将该文件至翻译成Huffman编码文件，再将Huffman编码文件翻译成原文件。 二、算法分析及思路： 对于该问题，我们做如下分析： （1）首先得构造出哈弗曼树，我们用函数HuffmanTree(int w[],int s[],int n)设计；（2）在构建哈弗曼树的基础上，进一步实现哈弗曼编码问题，我们用函数Huffmancode(char wen[])设计； （3）实现哈弗曼编码后再进一步实现哈弗曼译码问题，我们用函数Huffmandecode()设计； （4）其中编码问题中，得进一步统计出各个字符在文件中的频率，并进行一些必要的标记，我们用函数runhuffman(char wen[])设计； （5）在译码过程中，还有必要的一步是比较原文件与译码后的文件是否相同，我们用函数compare(char wen[])设计； （6）其中的文件输入我们用到类”fstream.h”中的输入输出流，并在运行的文件夹中建立一个文件名为逍遥游的文本文件，且在逍遥游文件中输入需要编码的数据。 三、主要解决的设计问题： 1.写一个对txt文件压缩和解压的程序，使用动态编码。 2.使用Huffman编码压缩和解压时，Huffman树的存储可以直接存储树结构，也可以存储所有字符的频度或权值，然后读取时建立Huffman树； 3.使用Huffman编码压缩和解压时，注意定义压缩码的结束标记，可以使用一个特殊的字符作为结束标记，也可以在压缩码之前存储其比特长度；如果使用一个特殊字符作为结束标记，则其频度为1，需要在建立Huffman树时把它看作一个独立的字符进行建树。 4.使用Huffman编码压缩和解压时，在一个缓冲区里面收集压缩码比特流，每当收集的比特数满8时，可以把这8比特通过位操作合并成一个字节写入文件（当然也可以收集满一定数目的字节后再写入文件）。写入文件的最小信息单位为字节。 四、程序设计的流程图： 习题1.1 5..证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立. Hint: 根据除法的定义不难证明: 如果d整除u和v, 那么d一定能整除u±v; 如果d整除u,那么d也能够整除u的任何整数倍ku. 对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d 能整除n和r，也一定能整除m=r+qn和n。 数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。故gcd(m,n)=gcd(n,r) 6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次? Hint: 对于任何形如0<=m 1、用计算机求解问题的步骤： 1、问题分析 2、数学模型建立 3、算法设计与选择 4、算法指标 5、算法分析 6、算法实现 7、程序调试 8、结果整理文档编制 2、算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程 3、算法的三要素 1、操作 2、控制结构 3、数据结构 算法具有以下5个属性： 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口 可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。 输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。 输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。 算法设计的质量指标： 正确性：算法应满足具体问题的需求； 可读性：算法应该好读，以有利于读者对程序的理解； 健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。 效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。 经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法 迭代法 基本思想：迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。 解题步骤：1、确定迭代模型。根据问题描述，分析得出前一个（或几个）值与其下一个值的迭代关系数学模型。 2、建立迭代关系式。迭代关系式就是一个直接或间接地不断由旧值递推出新值的表达式，存储新值的变量称为迭代变量 3、对迭代过程进行控制。确定在什么时候结束迭代过程，这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一 算法设计与分析课程报告 第一章 算法问题求解基础 1、算法的概念：算法是指解决问题的一种方法或过程，是由若干条指令组成的有穷序列。 2、算法的特性 ① 有穷性：一个算法必须保证执行有限步之后结束; ② 确切性：算法的每一步骤必须有确切的定义; ③ 输入： 一个算法有 0 个或多个输入， 法 本身定除了初始条件; ④ 输出： 一个算法有一个或多个输出， 是毫无意义的; ⑤可行性：算法原则上能够精确地运行, 而且人们用笔和纸做有限次运算后即可完成 3、算法与程序的关系： 区别：程序可以不一定满足可终止性。但算法必须在有限时间内结束; 程序可以没有输出 ,而算法则必须有输出; 算法是面向问题求解的过程描述，程序则是算法的实现。 联系：程序是算法用某种程序设计语言的具体实现; 程序可以不满足算法的有限性性质。 4、算法描述方式：自然语言，流程图，伪代码，高级语言。 第二章 算法分析基础 1、算法复杂性分析： 算法复杂性的高低体现运行该算法所需计算机资源（时间，空间）的多少。 算法复杂性度量： 期望反映算法本身性能，与环境无关。 理论上不能用算法在机器上真正的运行开销作为标准（硬件性能、代码质量影响） 般是针对问题选择基本运算和基本存储单位，用算法针对基本运算与基本存储单 以刻画运算对象的初始情况， 所谓 0 个输入是指算 以反映对输入数据加工后的结果。 没有输出的算法 位的开销作为标准。算法复杂性C依赖于问题规模N、算法输入I和算法本身A。即C=F（N, I,A）。 第五章分治法 1、递归算法：直接或间接地调用自身的算法。 用函数自身给出定义的函数称为递归函数。 注：边界条件与递归方程是递归函数的二个要素。 实例：①阶乘函数; ② Fibonacci 数列；③ Ackerman 函数; ④排列问题; ⑤整数划分问题; ⑥ Hanoi 塔问题 优缺点：①优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性, 因此它为设计算法、调试程序带来很大方便。 ②缺点：递归算法的运行效率低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 2、分治法的设计思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。（将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解） 分治法所能解决的问题一般具有以下几个特征： ①该问题的规模缩小到一定的程度就可以容易地解决; ②该问题可以分为若干个规模更小的相同问题，即该问题具有最有子结构性质; ③利用该问题分解出的子问题的解可以合并为该问题的解; ④该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 第六章贪心法 1、贪心算法的思想： 湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析》 试题 考试类型：开卷 试卷类型：C 卷 考试时量：120 分钟 1. 用O 、Ω和θ表示函数f 与g 之间的关系______________________________。 ()()log log f n n n g n n == 2. 算法的时间复杂性为1, 1()8(3/7), 2 n f n f n n n =?=? +≥?，则算法的时间复杂性的阶 为__________________________。 3. 快速排序算法的性能取决于______________________________。 4. 算法是_______________________________________________________。 5. 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是_________________________。 6. 在算法的三种情况下的复杂性中，可操作性最好且最有实际价值的是_____情况下的时间复杂性。 7. 大Ω符号用来描述增长率的下限，这个下限的阶越___________，结果就越有价值。。 8. ____________________________是问题能用动态规划算法求解的前提。 9. 贪心选择性质是指________________________________________________________ ____________________________________________________________。 题 号 一 二 三 四 五 总分 统分人 得 分 阅卷人 湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析》 试题 考试类型：开卷 试卷类型： 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. 贪心选择性质是指 ________________________________________________________ ____________________________________________________________ 。 本科实验报告 课程名称：算法设计与分析 实验项目：递归与分治算法 实验地点：计算机系实验楼110 专业班级：物联网1601 学号：2016002105 学生姓名：俞梦真 指导教师：郝晓丽 2018年05月04 日 实验一递归与分治算法 1.1 实验目的与要求 1．进一步熟悉C/C++语言的集成开发环境； 2．通过本实验加深对递归与分治策略的理解和运用。 1.2 实验课时 2学时 1.3 实验原理 分治（Divide-and-Conquer）的思想：一个规模为n的复杂问题的求解，可以划分成若干个规模小于n的子问题，再将子问题的解合并成原问题的解。 需要注意的是，分治法使用递归的思想。划分后的每一个子问题与原问题的性质相同，可用相同的求解方法。最后，当子问题规模足够小时，可以直接求解，然后逆求原问题的解。 1.4 实验题目 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．代码设计： 第一章作业 1.证明下列Ο、Ω和Θ的性质 1）f=Ο(g)当且仅当g=Ω(f) 证明：充分性。若f=Ο(g)，则必然存在常数c1>0和n0，使得?n≥n0，有f≤c1*g(n)。由于c1≠0，故g(n) ≥ 1/ c1 *f(n)，故g=Ω(f)。 必要性。同理，若g=Ω(f)，则必然存在c2>0和n0，使得?n≥n0，有g(n) ≥ c2 *f(n).由于c2≠0，故f(n) ≤ 1/ c2*f(n)，故f=Ο(g)。 2）若f=Θ(g)则g=Θ(f) 证明：若f=Θ(g)，则必然存在常数c1>0，c2>0和n0，使得?n≥n0，有c1*g(n) ≤f(n) ≤ c2*g(n)。由于c1≠0，c2≠0，f(n) ≥c1*g(n)可得g(n) ≤ 1/c1*f(n)，同时，f(n) ≤c2*g(n)，有g(n) ≥ 1/c2*f(n)，即1/c2*f(n) ≤g(n) ≤ 1/c1*f(n)，故g=Θ(f)。 3）Ο(f+g)= Ο(max(f,g))，对于Ω和Θ同样成立。 证明：设F(n)= Ο(f+g)，则存在c1>0，和n1，使得?n≥n1，有 F(n) ≤ c1 (f(n)+g(n)) = c1 f(n) + c1g(n) ≤ c1*max{f,g}+ c1*max{f,g} =2 c1*max{f,g} 所以，F(n)=Ο(max(f,g))，即Ο(f+g)= Ο(max(f,g)) 对于Ω和Θ同理证明可以成立。 4）log(n!)= Θ(nlogn) 证明： ?由于log(n!)=∑=n i i 1 log ≤∑=n i n 1 log =nlogn ，所以可得log(n!)= Ο(nlogn)。 ?由于对所有的偶数n 有， log(n!)= ∑=n i i 1 log ≥∑=n n i i 2 /log ≥∑=n n i n 2 /2/log ≥(n/2)log(n/2)=(nlogn)/2-n/2。 当n ≥4，(nlogn)/2-n/2≥(nlogn)/4，故可得?n ≥4，log(n!) ≥(nlogn)/4，即log(n!)= Ω(nlogn)。 综合以上两点可得log(n!)= Θ(nlogn) 2. 设计一个算法，求给定n 个元素的第二大元素，并给出算法在最坏情况下使用的比较次数。（复杂度至多为2n-3） 算法： V oid findsecond(ElemType A[]) { for (i=2; i<=n;i++) if (A[1]算法设计与分析课后部分习题答案
算法设计与分析考试题及答案
算法设计与分析试卷(2010)
算法设计与分析课程设计报告样本
算法设计与分析
计算机算法设计与分析期末考试复习题
算法设计与分析第2版 王红梅 胡明 习题答案
算法设计与分析学习总结
算法设计与分析课程设计报告
算法设计与分析基础习题参考答案
算法设计与分析期末试题答案解析
算法设计与分析课程报告
算法设计与分析试卷及答案
算法设计与分析试卷及答案.doc
算法设计与分析实验报告
算法设计与分析习题解答
相关主题
文本预览