资源描述
《算法分析与设计》2012-2013-2学期期中测试（信息安全专业DQ教学班）
姓名： 学号： 得分：
1. 证明。（10分）
证明：对于任意f1(n) Î O(f(n))，存在正常数c1和自然数n1，使得对所有n ³ n1，有f1(n) £ c1f(n)成立。
类似，对于任意g1(n) Î O(g(n))，存在正常数c2和自然数n2，使得对所有n ³ n2，有g1(n) £ c2g(n)成立。
令c3 = max{c1, c2}，n3 = max{n1, n2}，则对所有的n ³ n3，有
f1(n) +g1(n) £ c1f(n) + c2g(n)
£ c3f(n) + c3g(n)
= c3(f(n) + g(n))
即成立。
2. 将下列5个函数按渐近增长率由低至高进行排序，要求写出比较过程。（15分）
解：
(1) 是对数函数的幂，是幂函数，因此;
(2) ，因此;
(3) ，因此;
(4) 对和取对数，有
，
因为，所以;
因此，5个函数按渐近增长率由低至高排序为。
3. 给定按升序排列的n个不同整数存于数组a[1:n]中，请设计的算法找到下标i，，使得a[i] = i，如不存在这样的下标，则返回0。（15分）
解：
令head = 1, rear = n.
(1) 当head <= rear时，令mid = ⌊(head + rear)/2⌋；
(2) 如果a[mid] = mid，返回mid值，结束。
如果a[mid] > mid，令rear = mid – 1，返回(1)继续执行；
如果a[mid] < mid，令head = mid + 1，返回(1) 继续执行；
(3)返回0值，结束。
public static int Search(int [] a, int n)
{
// 在 a[0] <= a[1] <= ... <= a[n-1] 中搜索 a[i] = i
// 找到a[i] = i时返回i，否则返回0
int left = 0; int right = n – 1;
while (left <= right)
{
int mid = ⌊(left + right)/2⌋;
if (a[mid] == mid) return mid;
if (a[mid] > mid) right = mid – 1;
else left = mid + 1;
}
return 0; // 未找到a[i] = i
}
4. 利用主方法给出下列递归式的渐近界，并用数学归纳法证明式(2)的渐近界。（20分）
(1) , (2) , (3)
解：(1)
因此，.
(2)
因此，.
(3)
而且其中，
因此，.
证明：假设当时，，其中c为常数。
因此，命题得证。
5. 利用直接展开法求解下列递归式的渐近界。（20分）
(1) , (2)
解：(1)
(2)
其中，则
所以，，
即.
6. 某超市中有n种商品搞活动，每种商品i的重量是wi，其价格为vi，现在给你发一个容量为C的购物车，你可以在这n种商品中选一些放入你的购物车中免费带走。但是要求所选的商品重量之和不能大于购物车容量C，而且超市中每种商品每人最多选两件。请问在这种情况下你如何选择商品使得你能带走的免费商品的价格达到最大？（20分）
(a) 为该问题设计一个动态规划算法，要求写出分析过程和递归式。
(b) 若该超市共有3种商品搞活动，商品的价值依次为v = (25, 30, 15)，商品的重量依次为w = (2, 3, 1)，购物车容量为C = 5。运用自底而上的方法求解上述问题，要求画出表格，并给出最优解与最优值！
解：
方法1
² 将n种商品全部复制一份得到2n种商品，这样每种商品最多只能选择1件。
² 定义m(i, j)为购物车容量为j，由第1, …, i种商品装入购物车的最优值。
² Case 1: 不选择第i种商品
Ø 则m(i, j)为当重量限制为j时，{1, …,i – 1}种商品装入购物车所产生的最大价值
² Case 2: 选择第i种商品.
Ø 新的重量限制为 j – wi
Ø m(i, j – wi) 为新重量限制下，{1, …, i – 1}种商品装入购物车所产生的最大价值
因此，递归式如下：
最优解：选择商品1,1’,3, 即选择两个商品1, 一个商品3
最优值 = 25+25+15=65
方法2
² 定义m(i, j)为购物车容量为j，由第1, …, i种商品装入购物车的最优值。
² Case 1: 不选择第i种商品
Ø 则m(i, j)为当重量限制为j时，{1, …,i – 1}种商品装入购物车所产生的最大价值
² Case 2: 仅选择1格第i种商品.
Ø 新的重量限制为 j – wi
Ø m(i, j – wi) 为新重量限制下，{1, …, i – 1}种商品装入购物车所产生的最大价值
² Case 3: 选择两个第i种商品
Ø 新的重量限制为 j – 2wi
Ø m(i, j – 2wi) 为新重量限制下，{1, …,i – 1}种商品装入购物车所产生的最大价值
因此，递归式如下：
最优解：选择两个商品1, 一个商品3
最优值 = 25+25+15=65
第2章作业：算法分析基础
1. 算法与程序的区别
(1).算法特性之一是有穷性，程序不一定满足有穷性。
(2). 计算机程序是用来给计算机读的，而算法是给人来读的，直接将算法输入计算机是不能运行的。
(3).算法是解决问题的一种方法或一个过程，而程序则是算法用某种程序设计语言的具体实现。
2. 将下列函数按渐进增长率由低到高排列出来。
令，则有
显然上述4个函数的渐近增长率排序为；
显然上述3个函数的渐近增长率排序为；
因此，原函数的渐近增长率排序为。
3. 已知，证明。
证明：因为，存在正常数c0和自然数n0，使得对所有n ³ n0，有成立。
令c1 = c0 + 1，则对所有的n ³ n0，有
f(n) +g(n) £ f(n) + c0f(n)
£ (1 + c0)f(n)
= c1f(n)
即成立。
第3章作业：分治递归
1.画出T(n)=2T(n/2)+1的递归树，并给出其解的渐进界。然后用数学归纳法证明给出的界。
证明：假设当时，，其中c1和c2为常数。
因此，命题得证。
2.直接展开法求解递归式T(n)=T(n/2)+1
3.用主方法求解递归式
1.T(n)=4T(n/2)+n, 2.T(n)=4T(n/2)+n2, 3.T(n)=4T(n/2)+n3, 4.T(n)=3T(n/2)+ n2
请参考期中测试答案。
第4章作业：动态规划
1、设计一个O(n*log k) 时间的分治递归算法，将k个排好序的序列合并成一个排好序的序列，其中 k个序列共计包含n个元素。
a1[]
a2[]
a3[]
a4[]
ak[]
ak–1[]
a1[]…a2[]
a3[]…a4[]
ak–1[]…ak[]
a1[]…a4[]
ak–3[]…ak[]
a1[]…ak/2[]
ak/2+1[]…ak[]
a1[]…ak[]
将k个有序数列两两合并排序，得到个有序数列，再次两两合并排序，得到个有序数列，重复操作直至得到一个长度为n的有序数列。共计log k 次合并排序，每次合并排序数据的总体规模为n，则时间复杂度为O(n log k)
2、给定数组a[1…n]，n为偶数。设计一个算法，在最坏情况下用 3n/2 – 1 次比较找出a[1…n]中元素的最大值和最小值。
将a[1]…a[N]两两分成一组，即为a[1]和a[2] , a[3]和a[4] , a[5]和a[6] , … 共计N/2组，每组中的两个元素进行比较，得到最大值和最小值，共计N/2次比较；
上述每组中的最大值组成数组b[1…N/2]，冒泡排序(或其他排序方法)求得b[1…N/2]中的最大值，即为原数组a[1…N]的最大值，需N/2 – 1次比较；
同理，上述每组中的最小值组成数组c[1…N/2]，冒泡排序(或其他排序方法)求得c[1…N/2]中的最小值，即为原数组a[1…N]的最小值，需N/2 – 1次比较；
因此，共需3N/2 – 1次比较.
3、设计O(n2)时间的动态规划算法，找出由n个数组成的序列的最长单调递增子序列，要求给出分析过程和递归表达式。
原序列记为X, 对n个数递增排序, 构造一个新序列Y, 对X, Y求其最长公共子序列即可.
设序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}的最长公共子序列为Z={z1,z2,…,zk} ，则
(1)若xm=yn，则zk=xm=yn，且zk-1是xm-1和yn-1的最长公共子序列。
(2)若xm≠yn且zk≠xm，则Z是xm-1和Y的最长公共子序列。
(3)若xm≠yn且zk≠yn，则Z是X和yn-1的最长公共子序列。
由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用c[i][j]记录序列和的最长公共子序列的长度。其中， Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时c[i][j]=0。其他情况下，由最优子结构性质可建立递归关系如下：
4、两个序列进行对齐时，匹配得1分，错配罚1分，空位罚2分。给定两个字符序列X=CTACG和Y=TACAG，如何对齐才能使得得分最大？根据递归公式自底而上求解上述问题，要求画出求解过程表格，并给出最大得分和相应的对齐方式。
OPT(i, j) = 对齐 x1 x2 … xi 和 y1 y2 … yj.最大的得分
Case 1: OPT 匹配 xi-yj.
xi-yj 配对的得分 + 对齐x1 x2 … xi-1 和y1 y2 … yj-1 最大的得分
Case 2a: OPT 留下 xi 不匹配
– 2 + 对齐 x1 x2 … xi-1 和 y1 y2 … yj 最大的得分
Case 2b: OPT留下 yj 不匹配
– 2 + 对齐 x1 x2 … xi 和 y1 y2 … yj-1 最大的得分
OPT(i,j) j
i
0
1
2
3
4
5
0
0
– 2
– 4
– 6
– 8
– 10
1
– 2
– 1
– 3
– 3
– 5
– 7
2
– 4
– 1
– 2
– 4
– 5
– 7
3
– 6
– 3
0
– 2
– 3
– 5
4
– 8
– 5
– 2
1
– 1
– 3
5
– 10
– 7
– 4
– 1
0
0
最优对齐方式为
C
T
A
C
G
T
A
C
A
G
第5章作业：贪心算法
1、请叙述分治递归、动态规划、备忘录方法和贪心算法各自的特点和基本要素，并比较它们之间的相同之处及其差异。
分治递归法所能解决的问题一般具有以下几个特征:
(1) 该问题规模缩小到一定的程度就可以容易地解决；
(2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有递归子结构性质
(3) 利用该问题分解出的子问题的解可以合并为该问题的解；
(4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
动态规划与分治的比较
(1) 共同点：递归子结构
将待求解问题分解成若干个规模较小的相同类型的子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
(2) 不同点：重叠子问题
适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。
(3) 不同点：求解问题的顺序
分治递归、备忘录方法：自顶向下，动态规划：自底向上，
贪心算法的基本要素
(1) 贪心选择性质
(2) 最优子结构性质
贪心算法的特点
(1) 总是作出局部最优选择
(2) 不能保证得到全局最优解
贪心法与动态规划的比较
相同点：递推算法、最优子结构、局部最优解→全局最优解
不同点：
动态规划：自底向上，贪心算法：自顶向下
贪心算法：当前局部最优解←上一步局部最优解，动态规划：当前局部最优解←之前所有局部最优解
2、给定一个包含{b,e,f,n,o,t,y}字符集的文本文件，每个字符在文件中出现频率如下表所示，文件共有140个字符，试用huffman编码对该文本文件进行编码，要求画出编码的huffman树，给出每个字符的huffman编码，并求解编码后文件的长度。
字符
b
e
f
n
o
t
y
次数
12
43
33
15
7
6
24
编码后文件长度 = (6 + 7) × 4 + (12 + 15 + 24) × 3 + (33 + 43) × 2 = 357 bit
3、用Dijkstra 算法求下图中顶点1到其他所有顶点的最短路径，要求给出计算过程和最优解、最优值。
解1：
迭代
S
u
The distance from node 1 to node #
2
3
4
5
6
7
初始
{1}
-
7
4
10
1
{1,3}
7
4
10
10
2
{1,3,2}
7
4
10
10
3
{1,3,2,4}
7
4
10
10
15
4
{1,3,2,4,5}
7
4
10
10
13
5
{1,3,2,4,5,6}
7
4
10
10
13
15
{1,3,2,4,5,6,7}
7
4
10
10
13
15
解2：
迭代
S
u
The distance from node 1 to node #
2
3
4
5
6
7
初始
{1}
-
7
4
10
1
{1,3}
7
4
10
10
2
{1,3,2}
7
4
10
10
3
{1,3,2,5}
7
4
10
10
13
4
{1,3,2,5,4}
7
4
10
10
13
5
{1,3,2,4,5,6}
7
4
10
10
13
15
{1,3,2,4,5,6,7}
7
4
10
10
13
15
最短路径：
1→2：1,2
1→3：1,3
1→4：1,4
1→5：1,3,5
1→6：1,3,5,6
1→7：1,3,5,6,7
4、分别叙述用Prim算法和Kruskal算法求最小生成树的过程，并分别用上述两种算法求下图的最小生成树，要求给出最小生成树中边的生成顺序，画出最小生成树，并最小权重之和。（其中Prim算法从节点1开始执行）
Prim‘s 算法. 首先置S={1}，然后，只要S是V的真子集，就作如下的贪心选择：选取满足条件iÎS，jÎV-S，且c[i][j]最小的边，将顶点j添加到S中。这个过程一直进行到S=V时为止
Kruskal‘s 算法. 首先将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接2个不同的连通分支：当查看到第k条边(v,w)时，如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。这个过程一直进行到只剩下一个连通分支时为止。
Prim‘s 算法.(1,3), (3,5), (5,6), (6,7), (6,4), (4,2)
Kruskal‘s 算法. (6,7), (5,6), (1,3), (6,4), (4,2), (3,5)
权重之和为15。
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
