算法设计技巧与分析 汇总算法test汇总

1、 TEST(9 月 12 日)1 已知：1() = (1 (n)，2 () = (2 (n)，请证明：(1)(2)(3)1 () + 2 () = (1 (n) + 2 (n)1() + 2() = (max(1 (n),2 (n)1 () 2 () = (1 (n) 2 (n)2 设计一个分治算法，求 n 个数所组成的数组中第二大的元素。并请分析算法的时间复杂性。 输入：n 个元素的数组 A1n 输出：第二大元素 typedef struct MyTwoMaxint Max; int SecMaxMyMax； MyMax getSecMax(int A,int low,int high)/分

2、治求数值中的最大的两个元素 MyMax lm,rm,mm; int mid;if(high-low=1)if(high-low=1)mm.Max=max(Alow,Ahigh); mm.SecMax=min(Alow,Ahigh); return mm;elsemm.Max=Alow;mm.SecMax=0; return mm; elsemid=(low+high)/2 lm=getSecMax(A,low,mid); rm=getSecMax(MyInt,mid+1,high);mm.Max=max(lm.Max,rm.Max); mm.SecMax=max(min(lm.Max,rm.M

3、ax),max(lm.SecMax,rm.SecMax); return mm;3 请证明任意 P 类问题，也是 NP 类问题。 P 类问题是一个判定问题，这些问题可以用一个确定性算法在多项式时间内判定或者解出，即能够在多项式时间算法内得到结果。 NP 类问题也是一个判定问题，这些问题可以用一个确定性算法在多项式时间内检查或者验证它们的解。在得到问题的解的情况下，能够在多项式时间算法内验证解是否正确，而不在乎求解本身多花费的时间。 那么由此看来 P 类问一也是 NP 类问题，因为既然可以在多项式时间内求解，那么也能 够在多项式时间对解进行验证。 TEST(10 月 10 日)设计一个随机二分查

4、找算法，并计算其时间复杂度。输入：n 个元素的升序数组 A1n和元素 x输出：若 x=Aj，1 j n，则输出 j，否则输出 01.2.3.4.5.6.7.8.low 1; high n; j 0while(low high) and (j = 0) mid random(low, high) if x = Amid then j midelse if x m2算法设计如下： 1.k 12.while k m 3.4.5.6.7.8.9.10.11.12.r random(1,n)i k 1while i 1 and r Ai i i 1end while if i = 0Ak rk k +

5、1end if end while复杂度分析如下： 每次随机生成一个新元素 r，要查找 r 是否已经出现在已选定的数字中。假设生成第 i 个有效随机数时，平均要产生E( )次。则复杂度为： T(n, m) = 0 E(1)+ 1 E(2) + + (m 1) E() = ( 1) ()=1= ( 1) =11 =1 = ( 1)1 T(n, m) = n 11 =11 =1 ( 1)= ( 1) + 1 + 12111( 1) = 1 2T(n, m) = n 1 = 1 1=1=1 因为m2 n，则 (2) T(n, m) (2)，所以 T(n,m) = (2)TEST(11 月 7 日)1

6、.给出 FFD 算法的具体描述形式。FFD 算法： 容量是 1.0 输出：bini是放物品 i 的箱子号，1in. 为了使算法简单，在装箱前，货物已经按尺寸从大到小排序 sort(S,n)/将 S 从大到小递减排序 new usedn+1/usedj是箱子 j 已经使用的空间for(i=1;i=n;i+) for(j=1;j=n;j+) if(usedj+Si1.0) bini=j; usedj+=Si; break; 2.证明无向图中奇数度的个数是偶数。 证明： 设 G=V,E是任一图。设|V|=n。 由欧拉握手定理可得 deg(v)=2|E|可得，图中所有结点度数之和是偶数。显然所 vV有

7、偶数度结点的度数之和仍为偶数，从而所有奇数度结点的度数之和也是偶数。因此， 图中度数为奇数的结点一定为偶数个。 3.给出求欧拉图中欧拉回路的算法，分析时间复杂性。 TEST(11 月 14 日)在 Ford-Fulkson 算法中第 5 步，寻找剩余图 R 中的一条增广路径p=st，请给出具体寻找增广路径的算法。要求算法时间复杂度为 O(m)，m 为图示中边的条数。 使用广度优先搜索或者深度优先搜索找一条增广路径的时间复杂度均为 O（m） 广度优先：从 S 开始，访问 S 各个未被访问的邻接点 W1,W2,Wn，接着从 Wi 点一次出发访问其未被访问的邻接点，直到 t 为止。 设图 G 的初态

8、是所有顶点均未访问，以 S 作为初始点，基本思想是： （1） 从顶点 S 出发，访问之；并将其访问标志置为已被访问，即 visitedi=1； （2） 依次访问顶点 S 的各个未被访问过的邻接点，将 S 的全部邻接点都访问到； （3） 分别从这些邻接点出发，依次访问它们的未被访问过的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直到图中所有已被访问到顶点t。 void BFS(VLink G, int v) int w;VISIT(s);visiteds = 1; ADDQ(Q,s); while(!EMPTYQ(Q) s = DELQ(Q);w = FIRSTADJ(G,s);while(w != -1) if(visitedw = 0) VISIT(w);ADDQ(Q,w);visitedw = 1;w = NEXTADJ(G,s);/*访问顶点 s*/*顶点 S 对应的访问标记为 11*/*退出对头元素 s*/*求 s 的第一个邻接点，无邻接点则返回-1*/*访问顶点*/*当前被访问的点进队*/*访问记录标记为 1*/*求 s 下一个邻接点*/TEST(11 月 21 日)利用 MPM 算法求下图的最大流，画出过程 12 月 05 号 TES