算法设计及分析C

1、网络学院算法试题C及答案一 ？填空题：每题4分，共20分1. 环境栈空间用来保存函数调用返回时恢复运行所需要的信息，具体包括返回地址；所有局部变量的值、递归函数的传值形式参数的值；所有引用参数以及常量引用参数的定义。2?估算程序运行时间的方法通常有两种，分别为 和操作计数方法，统计程序的执行步数3 ?递归函数的两大根本要素是和 。递归方程和边界条件4. 一个分治法将规模为n n>1的问题分成k个规模为n/ m的子问题去解。设分解阀值no=1，且解规模为1的问题消耗1个单位时间。再设将原问题分解为k个子问题以及由k个子问题的解合并为原问题的解需用fn个单位时间。用 T n表示该分治法解规模

2、为|P|=n的问题所需的计算时间，那么T n=。kT n/m+f n5?采用回溯法求解问题时，通常采用两种策略即两种剪枝函数防止无效的搜索，它们分别是和。约束函数，限界函数二?简答题：每题6分，共18分1. 简述分治法的总体思想：a将难以直接求解的大问题分解为k个相同的子问题；b对这k个子问题分别求解。如果子问题的规模仍然不够小，那么再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止；c将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。d经分解得到的各个子问题相互独立。2. 假设以加法和乘法为关键操作，估算下述n次多项式求值函数的时

3、间复杂度取T为整型templatevclass T>T PolyEval (T coeff, i nt n, const T& x )T y=1, value=coeff0;for(i=1;iv=n ;i+)y*=x;value+=y*coeffi;retur n value;解答：T PolyEval(T coeff, i nt n, const T& x) /计算n次多项式的值，coeff0:n为多项式的系数T y=1, value=coeffO;for(i=1;iv=n ;i+)/ n 循环 /累加下一项y*=x;/ 一次乘法value+=y*coeffi;/ 一次

4、加法和一次乘法retur n value;II 3n次根本操作3. 什么是贪心选择性质？所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来到达。.计算和编程题：前两小题每题18分，后两小题每题13分，共62分1.考虑如下的贪心算法，它试图找出在有正方边长的有向图G中顶点s到顶点t的距离。从顶点s开始，到最近的顶点，称为 X；从x出发到最近的顶点，称为 y ;继续这种做法直 到到达顶点s到t的距离;t。给出一个最少顶点的图，证明这种探索不总是产生从(1, 2)= 3;(1, 3)= 2;(3, 2)= 4;(2, 4)= 2;(3, 4)= 5;假设求 1 到 4

5、 的最短路径：按如上的算法得到路径为 :1 >3 >2 >4 长度为 8;但实际路径为 1 >2 >4 长度为 5; 所以贪心算法不总能得到整体的最优解，但它们还是最优解的最好近似2 ?请用分治法设计算法：在一个整数组A 仁 n 中，同时寻找最大值和最小值，并分析你的算法的时间复杂度。 假设 n 为 2 的方幕 解答算法： MINMAX 输入： n 个整数元素的数组 A1.n, n 为 2 的方幕。输出： ( x, y ) , A 中的最大元素和最小元素。过程 Min_Max(low, high)if high-low=1 thenif AlowvAhigh th

6、en return (Alow,Ahigh)else return (Ahigh,Alow) end if.elsemid= l(low+high)/2 (x1, y1)=Min_Max(low, mid) (x2,y2)=Min_Max(mid+1, high) x=min(x1,x2) y=max(y1,y2) return (x, y)end if该算法的复杂度分析：设 C(n) 表示算法在由 n 个元素组成的数组上执行的元素比拟次数， 那么可得到算法所作 的元素比拟次 数的递推关系式如下：1 假设 n = 2C( n),2 C ( n /唱 2 假设 n > 2C(n) 二 2C

7、(n/2) 2二 2(2C(n/4) 2) 2-4C(n/4) 4 2=4(2C(n/8) 2) 4 2=8C(n/8) 8 4 2 ak-1k -1 k -1=2 C(n/2 ) 2k- 2 25k-1C(2) ' 2 j=(n/2) 2k - 2二 3n/2 - 23.给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为 C。问应如何 选择装入背 包的物品，使得装入背包中物品的总价值最大？解答：1) 定义最优值设m(i, j)是背包容量为j,可选择物品为i, i+1，n时0-1背包问题的最优解的值。由0-1背包问题的最优子结构性质，可以建立计算m(i , j)的递归

8、式如下：m(i,j) maxm(i +1, j),m(i +1,j wj+V jvm(n, j)=m(i+1,j)Wn(2)2) 计算最优值void knapsack(int v , int w , int c, int m) int n=v.length-1;int jMax=min(wn-1,c);/进行(1)式赋值 for( int j=0 for( int j=wn; jv=c; j+) mnj=vn; /进行式赋值for( int i=n-1; i>1; i-) jMax=min(wi-1,c); for( int j=0; jv=jMax; j+) mij=mi+1j; fo

9、r(int j=wi; jv=c; j+) mij=max(mi+1j, mi+1j-wi+vi); m1c=m2c;II 当; jv=jMax; j+) mnj=0;/ 当 0v=jvwn/ j 为背包容量当 wn v= j , m(n,j) 赋值/当 0v=jvwi / 当wi v= j v= cOv=jvw1if (c>=w1)当 w1 v= jm1c=max(m1c, m2c-w1+v1);3)根据最优值计算最优解void traceback( int m , i nt w , i nt c, i nt x) int n=wength-1;for(i nt i=1; i <n; i+)if (mic=mi+1c) xi=0;/物品 i 没有被选择else xi=1; c-=wi; xn =(m n c>0)? 1:0; 4 ?在用回溯法求解0/1背包问题时，()1 o1画出该问题的解空间树；2用伪代码描述用于剪枝的限界函数。解答：1这个问题的解可以表示成0/1数组x1, x2, . . . , xn ，依据wi是否属于S, xi分别取值1或0。故解空间中共有2An个兀素。它的树结构是一棵完全二叉树。解空间树2)限界函数：double boun d(i nt i)/计算上界double cleft = c - cw;/剩余容量double bou