算法与分析与设计平时作业

平时作业

1、给定下述二分搜索算法，请判断算法的正确性，指出错误算法的产生原因。

a) int BinarySearch(Type a[], const Type& x, int l, int r){

while (r >= l){

int m = (l+r)/2;

if (x == a[m]) return m;

if (x < a[m]) r = m-1;

else l = m+1;

}

return -1;

}

b) int BinarySearch(Type a[], const Type& x, int l, int r){

while (r >= l){

int m = (l+r)/2;

if (x == a[m]) return m;

if (x < a[m]) r = m+1;

else l = m-1;

}

return -1;

}

c) int BinarySearch(Type a[], const Type& x, int l, int r){

while (r > l){

int m = (l+r)/2;

if (x == a[m]) return m;

if (x < a[m]) r = m-1;

else l = m+1;

}

return -1;

}

2、O(1)空间子数组环卫算法：设a[0:n-1]是一个n维数组，k（1≤ k ≤n-1）是一个非负整数。试设计一个算法将子数组a[0 : k-1]与a[k+1 : n-1]换位。要求算法在最坏情况下耗时O(n)，且只用O(1)的辅助空间。

3、定义： 给定一个自然数n，由n开始依次产生半数集set(n)中的元素如下：

1）nset(n)；

2）在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半；

3）按此规则进行处理，直至不能再添加新的自然数为止。

例如 set(n){6,16,26,126,36,136}。其中共有6个元素。

半数集问题：对于给定的n，求半数集set(n) 中元素的个数。

4、设计一个算法，找出由n个数组成的序列的最长单调递增子序列的长度。

5、会场安排问题：假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。对于给定的n个待安排的活动，计算使用最少会

场的个数。每个活动i都有一个开始时间和结束时间，分别表示为b(i)，f(i)。

6、最优分解问题：设n是一个正整数。现要求将n分解为若干个互不相同的自然数的和，使得这些自然数的乘积最大。设计一个算法，得到最优分解方案。

分析：我们知道如果a+b=常数，则|a-b|越小，a*b越大。

贪心策略：将n分成从2开始的连续自然数的和。如果最后剩下一个数，将此数在后项优先的方式下均匀地分给前面各项。

7、子集和问题：设S{x1,x2,,xn}是n个正整数的集合，c是一个正整数。那么是否存在S的一个子集S1，使得子集中元素之和等于c，即xSxc1。

8、设序列Z{z1,z2,,zk}是序列X{x1,x2,,xm}和Y{y1,y2,,yn}的最长公共子序列。

a) 请说明最长公共子序列具有最优子结构性质。

Y{y1,y2,,yj}b) 设c[i][j]记录序列Xi{x1,x2,,xi}i和j的最长公共子序列的长度。由

最长公共子序列问题的最优子结构性质建立子问题最优值c[i][j]的递归关系。

c) 写出寻找最长公共子序列的算法。

9、记矩阵连乘积

A[i,j]AiAi1...Aj,ij。 确定计算A[1:n]的最优计算次序，使得所

需数乘的次数最少。

1、说明矩阵连乘计算次序问题的最优解包含着其子问题的最优解，即最优子结构性质。

2、该问题具备子问题的重叠性质。

3、说明采用动态规划方法可以解决该问题。

4、设计该算法，分析算法的复杂性。

10、考虑分数背包问题，定义如下：给出n 个大小为 s1, s2, …, sn , 价值为v1, v2, …, vn 的物品， 并设背包容量为C, 要找到非负实数x1, x2, …, xn, 使和

xvi1nii 在约束

xsi1niiC下最大。写出求解问题的贪心算法，估计算法的时间复杂性。