东南大学2015春算法试卷答案.pdf

1、求解下面的递归式，并针对每个递推式给出一个界限。 （1） 7/7T nT nn 解： 7/7T nT nn， 其中 7,7,abf nn。 因此， 1 loglog 1 ba nnnn， 由于 f nnn，应用主定理第二条定理有， log loglog ba T nnnnn。 （2） 3/2 8/6logT nT nnn 解 ： 3/2 8/6logT nT nnn， 其 中 3/2 8,6,logabf nnn。 因 此 ， 6 loglog 80.778 ba nnn，由于 6 log 83/2 logf nnnn ，其中0.8，应用主 定理情况 3，当n足够大时，对于8/64/3c ，有： 3/2 /8/6 log/64/3logaf n bf nnnncf n，条件成立。因此，应用情 况 3 有， 3/2 logT nnn。 （3） 1/3 21T nT n 解：做代换2mn ，只考虑 1/3 n为整数的情形。可以得到， /3 2221 mm TT， 将此式改写为： 2/31S mS m。 对此式应用主定理情况 1，可以得到 3 loglog 2 ba S mmm，所以： 3 3 log 2 log 2 2 2log m T nTS mmn 22 2/31 1 2 1 2/3.1 22.2/3 kk S mS mS mS m ， 当 /31 k m时， 有， 3 logkm， 所以 33 loglog1 1 2 .2121 mm S mS ， 因此， 3 33 log 2 loglog 2 2 22log mm T nTS mmn 2、给出一个求解背包问题的算法。并说明其正确性。 输入：给定n个物品，物品价值分别为 12 , n P PP物品重量分别 12 , n W WW，背 包容量为M。每种物品可部分装入到背包中。 输出： 12 ,01 ni X XXX，使得 1 ii i n PX 最大，并且满足 1 ii i n W XM 。 解：这个问题的特点是：每种物品只有一件，可以选择放或者不放。利用动态规 划思想 ，子问题为：假设( , )f i j表示剩余容量为j，剩余物品为,1,.,i in 时的最优解的值。DP 求解过程可以这样理解： 对于前件物品，背包剩余容量为时，所取得的最大价值只依赖于两个状态。 状态状态 1 1：只要不选第个物品,前1i件物品，背包剩余容量为j。在该状态下， 1f ij。 状态状态 2 2：选第个物品,前1i件物品，背包剩余容量为 jW i。在该状态下, 1f ij W iP i 因为，这里要求最大价值，所以只要从状态 1 和状态 2 中选择最大价值较大 的一个即可。 （1）采用二维数组 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include #include using namespace std; int main() static const int M = 10; / 定义空间最大值 static const int n = 5; / 物品个数 vector dp(n + 1, vector(M + 1, 0); vector W(n + 1), P(n + 1); for (int i = 1; i Wi Pi; / 输入物品i的体积和价值 for (int i = 1; i = n; +i) / 对每一个物品进行选择 for (int j = Pi; j = M; +j) / 对每一个状态进行比较 / 按照状态转移方程进行比较 dpij = max(dpi - 1j, dpi - 1j - Wi + Pi); cout dpM Wi Pi; / 输入物品i的体积和价值 for (int i = 1; i = Pi; -j) / 对每一个状态进行比较 / 按照状态转移方程进行比较 dpj = max(dpj, dpj - Wi + Pi); cout dpM endl; / 输出最后结果 return 0; 3、下图是一个流网络，请说明 s 到 t 的最大流值是多少？并标示一种流方式。 4、 设1. Xn，1. Yn为两个数组， 每个都包含n个有序元素。 请设计一个logn 时间的算法来找出数组X和Y中所有2n个元素的中位数。 算法：算法：分别对X和Y进行二分搜索，对于搜索中值middle，比较X middle和 Y middle 的大小， 如果X middleY middle， 那么就舍弃X的前半部分 和Y的 后 半 部 分 。 这 样 下 一 次 搜 索 的 区 间 就 减 少 了 一 半 。 = X middleY middle或 者X和Y的 搜 素 区 间 长 度 为 1 。 这 时 取 /2X middleY middle为返回的中位数。 解：解： 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 #include using namespace std; static const int n = 10; double Xn = 1,2,3,4,5,6,7,8,9,10 ; double Yn = 8,9,10,11,12,13,14,15,16,17 ; double middle(int iX, int jX, int iY, int jY) int midX = (iX + jX) / 2; int midY = (iY + jY) / 2; if (iX = jX | iY = jY | XmidX = YmidY) return (XiX + YiY) / 2; / 终止条件 else if (XmidX YmidY) / 奇偶讨论，如果搜索范围内有奇数个数，那么右侧左移一次 / 如果搜索范围内有偶数个数，那么右侧在原位不动 return middle(midX + 1, jX, iY, midY - (iY + jY) % 2 ? 0 : 1); else return middle(iX, midX - (iX + jX) % 2 ? 0 : 1), midY + 1, jY); int main() cout n k) vector a(n + 1); vector sum(n + 1, vector(n + 1, 0); vector dp(n + 1, vector(k + 1, 0); for (int i = 1; i ai; / 输入待求数组 for (int i = 1; i = n; i+) for (int j = i; j = n; j+) int s = 0; for (int k = i; k = j; k+) s += ak; / sumij初始化为待求数组i到j的和 sumij = s; for (int i = 1; i = n; i+) dpi0 = sum1i;/ dpi0为1到i中，乘号个数为0时，数组的最大结果 for (int j = 1; j = k; j+) / 不断的添加乘号，动态规划求最大值 for (int i = j + 1; i = n; i+) / 添加乘号时，起始计算位是j+1 dpij = -1; / 开始动态规划 for (int k = j; k i; k+) dpij = max(dpij, dpkj - 1 * sumk + 1i); / 自底向上根据状态转移方程求最大值 cout dpnk; return 0; 6