1、一、已知下列递推式： C(n) = 1 若 n =1 = 2C（n/2） + n 1 若 n 2 请由定理 1 导出 C(n)的非递归表达式并指出其渐进复杂性。 定理 1：设 a,c 为非负整数，b,d,x 为非负常数，并对于某个非负整数 k, 令 n=ck, 则以下递推式 f(n) =d 若 n=1 =af(n/c)+bnx 若 n=2 的解是 f(n)= bnxlogcn + dnx 若 a=c x f(n)= 若 ac xxaxncbbdclog 解：令 F(n) = C(n) 1 则 F(n) = 0 n=1 F(n) = 2C(n/2) + n 2 n=2 = 2F(n/2) + 1
2、 + n 2 = 2F(n/2) + n 利用定理 1，其中： d=0,a=2,c=2,b=1,x=1,并且 a=cx 所以 F(n) = nlog 2n 所以 C(n) = F(n) + 1 = nlog 2n + 1 C(n)的渐进复杂性是 O(nlog2n) 二、由于 Prim 算法和 Kruskal 算法设计思路的不同，导致了其对不同问题实例 的效率对比关系的不同。请简要论述： 1、如何将两种算法集成，以适应问题的不同实例输入； 2、你如何评价这一集成的意义？ 答： 1、Prim 算法基于顶点进行搜索，所以适合顶点少边多的情况。 Kruskal 从边集合中进行搜索，所以适合边少的情况。
3、 根据输入的图中的顶点和边的情况，边少的选用 kruskal 算法，顶点少的选 用 prim 算法 2、没有一个算法是万能的，没有一个算法是对所有情况都适合的。这一集成 体现了针对具体问题选用最适合的方法，即具体问题具体分析的哲学思想。 三、分析以下生成排列算法的正确性和时间效率： HeapPermute(n) /实现生成排列的 Heap 算法 /输入：一个正正整数 n 和一个全局数组 A1n /输出：A 中元素的全排列 if n = 1 write A else for i 1 to n do HeapPermute(n-1) if n is odd swap A1and An else s
4、wap Aiand An 解： n=1 时，输出 a1 n=2 时，输出 a1a2，a2a1 n=3 时， (1) 第一次循环 i=1 时，HeapPermute(2)将 a1a2 做完全排列输出，记为 a1a2a3，并将 A 变为 a2a1a3，并交换 1,3 位，得 a3a1a2 (2) 第二次循环 i=2 时，HeapPermute(2)输出a3a1a2，并将 A 变为 a1a3a2，交换 1,3 位，得 a2a3a1 (3) 第三次循环 i=3 时，HeapPermute(2)输出a2a3a1，并将 A 变为 a3a2a1，交换 1,3 位，得 a1a2a3，即全部输出完毕后数组 A
5、回到初始顺 序。 n=4 时， (1)i=1 时，HeapPermute(3)输出a1a2a3a4，并且 a1a2a3 顺序不变，交 换 1,4 位，得 a4a2a3a1 (2)i=2 时，HeapPermute(3)输出a4a2a3a1，并且 a4a2a3 顺序不变，交 换 2,4 位，得 a4a1a3a2 (3)i=3 时，HeapPermute(3)输出a4a1a3a2，并且 a4a1a3 顺序不变，交 换 3,4 位，得 a4a1a2a3 (4)i=4 时，HeapPermute(3)输出a4a1a2a3，并且 a4a1a2 顺序不变，交 换 4,4 位，得 a4a1a2a3，即全部输
6、出完毕后数组 A 循环右移一位。 由以上分析可得出结论： 当 n 为偶数时，HeapPermute(n)输出全排列后数组元素循环右移一位。 当 n 为奇数时，HeapPermute(n)输出全排列后数组元素顺序保持不变。 所以由归纳法证明如下： (1)i=1 时，显然成立。 (2)i=k 为偶数时，假设输出的是全排列，则 i=k+1(奇数)时，k+1 次循环 中，每次前 k 个元素做全排列输出后循环右移一位，所以对换 swap A1 and An可以保证每次将前 k 个元素中的一个换到 k+1 的位置，所以 k+1 次 循环后输出的是 A1k+1的全排列。 (3)i=k 为奇数时，假设输出的是
7、全排列,则 i=k+1(偶数)时，k+1 次循环中， 每次前 k 个元素做全排列输出后顺序保持不变，所以对换 swap Aiand An 可以保证每次将前 k 个元素中的一个换到 k+1 的位置，所以 k+1 次循环后 输出的是 A1k+1的全排列。 证毕。 时间复杂度递推公式为 T(n) = 1 n=1 = n T(n-1)+2 n1 化简得 T(n) = n! + O(nn-1) 所以时间复杂度为 O(n!) + O(nn-1) 四、对于求 n 个实数构成的数组中最小元素的位置问题，写出你设计的具有减 治思想算法的伪代码，确定其时间效率，并与该问题的蛮力算法相比较。 解： (1)算法思想：
8、将 n 分为n/2，n-n/2(表示向下取整)两部分，分别找 出其中的最小元及其位置，比较这两个元素的大小，得出总的最小元素的位置。 (2)伪代码： (x,i) = FindLeastElement(a,b) /从数组 Aab中找出最小元 x，及其位置 i /输入：全局实数数组 A1n，搜索起始位置 a,结束位置 b /输出：最小元素 x 及其位置 i if a=b return （Aa,a） else (x1,i) = FindLeastElement(1,n/2); (x2,j) = FindLeastElement(n/2+1,n); if x11 化简：F(n) = 2F(n/2) +
9、 1 = 22F(n/22)+1 + 1 = 22F(n/22) + 2 + 1 = 2kF(2k/2k) + 1 + 2 + + 2k-1 ( n=2k) = 2n-1 所以复杂度为 O(2n-1) 蛮力法的复杂度为 O(n)，所以此方法还没有蛮力法效率高，因为减治后会 增加比较次数。 五、请给出约瑟夫斯问题的非递推公式 J（n） ，并证明之。其中，n 为最初总 人数，J(n) 为最后幸存者的最初编号。 解：已知幸存者号码的递推公式：J(1) = 1; J(2k) = 2J(k) 1; n=2k J(2k+1) = 2J(k) + 1; n=2k+1 幸存者号码非递推公式：设 n = 2m
10、+ b，J(n) = 2*b+1 (01 时， 当 i 为偶数时，设 k = i/2 时成立，即 k = 2m + b，则 J(k) = 2b+1， 此时，i = 2k = 2m+1 + 2b J(i) = J(2k) = 2J(k) 1 = 2(2b+1) 1 = 4b + 1 = 2(2b) + 1，即 k=i 时成立。 当 i 为奇数时，设 k = (i-1)/2 时成立，即 k = 2m + b，则 J(k) = 2b+1， 此时，i = 2k + 1 = 2m+1 + 2b+1 J(i)= J(2k+1) = 2J(k)+1 = 2(2b+1)+1 = 4b+3 = 2(2b+1) +1， 即 k=i 时成立。 证毕。
