《算法设计与分析计算题.doc》由会员分享，可在线阅读，更多相关《算法设计与分析计算题.doc（19页珍藏版）》请在三一办公上搜索。
1、算法设计与分析一、 排序和查找是经常遇到的问题。按照要求完成以下各题：(1)对数组A=15，29，135，18，32，1，27，25，5，用快速排序方法将其排成递减序。解：（1）第一步：15 29 135 18 32 1 27 25 5 第二步：29 135 18 32 27 25 15 1 5 第三步：135 32 29 18 27 25 15 5 1 第四步：135 32 29 27 25 18 15 5 1 (2)请描述递减数组进行二分搜索的基本思想，并给出非递归算法。解：基本思想：首先将待搜索元素v与数组的中间元素进行比较，如果，则在前半部分元素中搜索v；若，则搜索成功；否则在后半部分
2、数组中搜索v。非递归算法：输入：递减数组Aleft:right，待搜索元素v。输出：v在A中的位置pos，或者不在A中的消息（-1）。步骤：int BinarySearch(int A,int left,int right,int v)int mid;while (leftAmid) right=mid-1;else left=mid+1;return -1;(3)给出上述算法的递归算法。解：输入：递减数组Aleft:right，待搜索元素v。输出：v在A中的位置pos，或者不在A中的消息（-1）。步骤：【3分】int BinarySearch(int A,int left,int right
3、,int v)int mid;if (leftAmid) return BinarySearch(A,left,mid-1,v);else return BinarySearch(A,mid+1,right,v);elsereturn -1;(4)使用上述算法对（1）所得到的结果搜索如下元素，并给出搜索过程：18，31，135。解：搜索18：首先与27比较，1827，在前半部分搜索；再次32比较，3129，此时只有一个元素，未找到，返回-1。 搜索135：首先与27比较，13527，在前半部分搜索；再次32比较，13532，在前半部分搜索；与135比较，相同，返回0。二、排序和查找是常用的计算
4、机算法。按照要求完成以下各题：（1）对数组A=15，9，115，118，3，90，27，25，5，使用合并排序方法将其排成递减序。（2）若改变二分搜索法为三分搜索法，即从一个递减序列A中寻找元素Z，先与元素比较，若，则在前面个元素中寻找Z；否则与比较，总之使余下的序列为个元素。给出该方法的伪代码描述。(3)使用上述算法对（1）所得到的结果搜索如下元素，并给出搜索过程：118，31，25。解：（1）第一步：15 9 115 118 3 90 27 25 5 第二步：15 9 118 115 90 3 27 25 5第三步：118 115 15 9 90 27 25 3 5第四步：118 115
5、90 27 25 15 9 3 5第五步：118 115 90 27 25 15 9 5 3（2）输入：递减数组Aleft:right，待搜索元素v。输出：v在A中的位置pos，或者不在A中的消息（-1）。步骤：int BinarySearch(int A,int left,int right,int v)int mid;while (leftAfirst) right=first-1;else if (v=Asecond) return second;else if (vAsecond) left=first+1;right=second-1;else left=second+1;retur
6、n -1;（3） 搜索118：11827，所以right3；118115，所以right1；118118，找到。搜索31：3127，所以right3；3190，所以left=4，结束，未找到。搜索25：925du+w(u,v)then dv=du+wu,v;pv=udijkstra(G,w,s)Init-single-source(G,s) S= Q=VGwhile Q do u=min(Q) S=Sufor each vertex vadju do Relax(u,v,w) 四、对于下图使用Dijkstra算法求由顶点a到其他各个顶点的最短路径。并给出求各个顶点对之间的最短路径的算法思想。步
7、骤 V1 V2 E1 E21. a b ab2. a,b d ab bd3. a,b,d c,f ab,bd dc,df4. a,b,d,c f ab,bd df5. a,b,c,d,f e ab,bd,dc,df fe6. a,b,c,d,e,f g ab,bd,dc,df,fe eg7. a,b,c,d,e,f,g h ab,bd,dc,df,fe,eggh8. a,b,c,d,e,f,g,h ab,bd,de,df,fe,eg,gh 结果：从a到h的最短路径为，权值为18。五、问题描述：有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的选择方案，使选中物品的总重量不超过指定
8、的限制重量，但选中物品的价值之和最大。#includevoid main()int m,n,i,j,w50,p50,pl50,b50,s=0,max;printf(输入背包容量m,物品种类n :);scanf(%d %d,&m,&n);for(i=1;i=n;i=i+1)printf(输入物品的重量W和价值P :);scanf(%d %d,&wi,&pi);pli=pi;s=s+wi;if(s=m)printf(whole choosen);/return;for(i=1;i=n;i=i+1)max=1;for(j=2;jplmax/wmax)max=j;plmax=0;bi=max;for(
9、i=1,s=0;sm & i=n;i=i+1)s=s+wbi;if(s!=m)wbi-1=m-wbi-1;for(j=1;j=i-1;j=j+1)printf(choose weight %dn,wbj);六、假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量M150，使用回溯方法求解此背包问题。请写出状态空间搜索树（20分）。物品ABCDEFG重量35306050401025价值10403050354030 解：贪心算法：（1）标准：重量、价值和单位价值。（2）使用重量从小到大：FGBAEDC。得到贪心解为：FGBAE全部放入，而D放入20%，得到价值为165。使
10、用价值从大到小：DFBEGCA，得到贪心解为：DFBE全部放入，而G放入80%，得到价值为：189。使用单位价值从大到小：FBGDECA，得到贪心解为：FBGD全部放入，而E放入87.5%，得到价值为190.625。（3）显然使用单位价值作为标准得到的是最优解。回溯法：按照单位效益从大到小依次排列这7个物品为：FBGDECA。将它们的序号分别记为17。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：a b. c d. e. f. g. h. i.j. 在Q1处获得该问题的最优解为，背包效益为170。即在背包中装入物品F、B、G、D、A时达到最大效益，为170，重量为1
11、50。七、分别用贪心算法、动态规划法、回溯法设计0-1背包问题。要求：说明所使用的算法策略；写出算法实现的主要步骤；分析算法的时间（1）贪心算法 O（nlog（n）首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。具体算法可描述如下：void Knapsack(int n,float M,float v,float w,float x)Sort(n,v,w);int i;for (i=1;i
12、=n;i+) xi=0;float c=M;for (i=1;ic) break;xi=1;c-=wi;if (i=n) xi=c/wi;（2）动态规划法 O(nc)m(i，j)是背包容量为j，可选择物品为i，i+1，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下。void KnapSack(int v,int w,int c,int n,int m11)int jMax=min(wn-1,c);for (j=0;j=jMax;j+) /*m(n,j)=0 0=jwn*/mnj=0;for (j=wn;j=wn*/mnj=vn;for (i=
13、n-1;i1;i-) int jMax=min(wi-1,c);for (j=0;j=jMax;j+) /*m(i,j)=m(i+1,j) 0=jwi*/ mij=mi+1j;for (j=wi;j=wn*/ mij=max(mi+1j,mi+1j-wi+vi);m1c=m2c;if(c=w1)m1c=max(m1c,m2c-w1+v1);（3）回溯法 O(2n)cw:当前重量 cp:当前价值 bestp：当前最优值voidbacktrack(inti) /回溯法 i初值1if(in) /到达叶结点 bestp=cp; return; if(cw+wibestp) /搜索右子树 backtra
14、ck(i+1); 八、已知，k=1，2，3，4，5，6，r1=5，r2=10，r3=3，r4=12，r5=5，r6=50，r7=6，求矩阵链积A1A2A3A4A5A6的最佳求积顺序。（要求：给出计算步骤）解：求解矩阵为：12345610150330405165520102036033024301950301809301770403000186050150060123456101224220222230344404450560因此，最佳乘积序列为（A1A2）（A3A4）（A5A6），共执行乘法2010次。九、回答如下问题：（1） 什么是算法？算法的特征有哪些？答：算法是解决某类问题的一系列运算的
15、集合。特征：具有有穷行、可行性、确定性、0个或者多个输入、1个或者多个输出。（2） 什么是P类问题？什么是NP类问题？请描述集合覆盖问题的近似算法的基本思想。解：用确定的图灵机可以在多项式实践内可解的判定问题称为P类问题。用不确定的图灵机在多项式实践内可解的判定问题称为P类问题。集合覆盖问题的近似算法采用贪心思想：对于问题，每次选择F中覆盖了尽可能多的未被覆盖元素的子集S，然后将U中被S覆盖的元素删除，并将S加入C中，最后得到的C就是近似最优解。十、多段图问题：设G(V，E)是一个赋权有向图，其顶点集V被划分成k2个不相交的子集Vi：，其中，V1和Vk分别只有一个顶点s（称为源）和一个顶点t（
16、称为汇），图中所有的边（u,v），。求由s到t的最小成本路径。（25分）a) 给出使用动态规划算法求解多段图问题的基本思想。b) 使用上述方法求解如下多段图问题。解：（1）基本思想：设P(i,j)是从Vi中的节点j到汇点t的最小成本路径，Cost(i,j)是其成本。则。边界条件是（1）若h=t，则Cost(h,t)0；（2）Cost(k-1,j)c(j,t)。（2）求解过程可以表示为：其中每个节点标示的序偶(p,q)中，p表示节点到t的成本，q表示后继节点的编号。从而，最优路径为：1271012和1361012，成本为16。十一设x1、x2、x3是一个三角形的三条边，而且x1+x2+x3=14
17、。请问有多少种不同的三角形？给出解答过程。解：由于x1、x2、x3是三角形的三条边，从而xi+xjxk，|xi-xj|xk，（i,j,k=1,2,3），根据x1+x2+x3=14可知1xi7（i=1,2,3）。利用回溯法求解得到：即有4个可行解：（6，6，2），（6，5，3），（6，4，4，）（5，5，4）。十二、设数组A有n个元素，需要找出其中的最大最小值。（20分）(1)请给出一个解决方法，并分析其复杂性。(2)把n个元素等分为两组A1和A2，分别求这两组的最大值和最小值，然后分别将这两组的最大值和最小值相比较，求出全部元素的最大值和最小值。如果A1和A2中的元素多于两个，则再用上述方法各
18、分为两个子集。直至子集中元素至多两个元素为止。这是什么方法的思想？请给出该方法的算法描述，并分析其复杂性。解：（1）基本思想：从头到尾逐个扫描，纪录最大和最小元素。输入：具有n个元素的数组输出：最大值和最小值步骤：void FindMaxMin(int A, int n, int max, int min)max=min=A0;for (i=1;imax) max=Ai;if (Aimin) min=Ai;复杂性分析：由于是从头到尾扫描各个元素，而每个元素都要与max和min比较一遍，从而时间复杂性为：O(n)。（2）void FindMaxMin(int left,int right, in
19、t max, int min)if (left=right) max=min=Aleft;else if (left=right-1)max=(AleftAright?Aright:Aleft);min=( AleftAright?Aleft:Aright);elsemid=(left+right)/2;FindMaxMin(left,mid,gmax,gmin);FindMaxMin(mid+1,right,hmax,hmin);max=(gmaxhmax?hmax:gmax);min=(gmin1时）。写成递归函数有：int fib(int n) if (n=0) return 0; if
20、 (n=1) return 1; if (n1) return fib(n-1)+fib(n-2); 十五、求证：O(f(n)+O(g(n) = O(maxf(n),g(n)证明：对于任意f1(n) O(f(n) ，存在正常数c1和自然数n1，使得对所有nn1，有f1(n) c1f(n) 。类似地，对于任意g1(n) O(g(n) ，存在正常数c2和自然数n2，使得对所有nn2，有g1(n) c2g(n) 。令c3=maxc1, c2， n3 =maxn1, n2，h(n)= maxf(n),g(n) 。则对所有的 n n3，有f1(n) +g1(n) c1f(n) + c2g(n) c3f(
21、n) + c3g(n)= c3(f(n) + g(n) c32 maxf(n),g(n)= 2c3h(n) = O(maxf(n),g(n) .十六、用分支限界法解装载问题时，对算法进行了一些改进，下面的程序段给出了改进部分；试说明斜线部分完成什么功能，以及这样做的原因，即采用这样的方式，算法在执行上有什么不同 / 检查左儿子结点 Type wt = Ew + wi; / 左儿子结点的重量 if (wt bestw) bestw = wt; / 加入活结点队列 if (i bestw & i 0 故Ew+rbestw总是成立。也就是说，此时右子树测试不起作用。为了使上述右子树测试尽早生效，应提
22、早更新bestw。又知算法最终找到的最优值是所求问题的子集树中所有可行结点相应重量的最大值。而结点所相应得重量仅在搜索进入左子树是增加，因此，可以在算法每一次进入左子树时更新bestw的值。十七、请写出用回溯法解装载问题的函数装载问题：有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且。装载问题要求确定是否有一个合理的装载方案可将这n个集装箱装上这2艘轮船。如果有，找出一种装载方案。解：void backtrack (int i)/ 搜索第i层结点if (i n) / 到达叶结点更新最优解bestx,bestw;return;r -= wi;if (cw +
23、 wi bestw) xi = 0; / 搜索右子树backtrack(i + 1); r += wi;十八、用回溯法解0/1背包问题时，计算结点的上界的函数如下所示，请在空格中填入合适的内容Typep Knap:Bound(int i)/ 计算上界 Typew cleft = c - cw; / 剩余容量 Typep b = cp; / 结点的上界 / 以物品单位重量价值递减序装入物品 while (i = n & wi = cleft) cleft -= wi; b += pi; i+; / 装满背包 if (i = n) （b += pi/wi * cleft）; return b;十九
24、、用回溯法解布线问题时，求最优解的主要程序段如下。如果布线区域划分为的方格阵列，扩展每个结点需O(1)的时间，L为最短布线路径的长度，则算法共耗时 ( O(mn) )，构造相应的最短距离需要（O(L)）时间for (int i = 0; i NumOfNbrs; i+) nbr.row = here.row + offseti.row; nbr.col = here.col + offseti.col; if (gridnbr.rownbr.col = 0) / 该方格未标记 gridnbr.rownbr.col = gridhere.rowhere.col + 1; if (nbr.row
25、= finish.row) & (nbr.col = finish.col) break; / 完成布线 Q.Add(nbr); 二十、用回溯法解图的m着色问题时，使用下面的函数OK检查当前扩展结点的每一个儿子所相应的颜色的可用性，则需耗时（渐进时间上限）（O（mn）Bool Color:OK(int k)/ for(int j=1;j=n;j+)if(akj= =1)&(xj= =xk) return false;return true;二十一、n后问题回溯算法(1)用二维数组ANN存储皇后位置,若第i行第j列放有皇后,则Aij为非0值,否则值为0。(2)分别用一维数组MN、L2*N-1、R
26、2*N-1表示竖列、左斜线、右斜线是否放有棋子，有则值为1,否则值为0。for(j=0;j 0) hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); 二十三、简述二分检索（折半查找）算法的基本过程设输入是一个按非降次序排列的元素表Ai：j 和x，选取A(i+j)/2与x比较，如果A(i+j)/2=x，则返回(i+j)/2；如果A(i+j)/2=0;r-) /自底向上递归计算for(c=0; ctr+1c+1) trc+ = tr+1c ；else trc+=tr+1c+1 ； 二十五、已知非齐次递归方程： ，其中，b、c是常数，g(n)
27、是n的某一个函数。则f(n)的非递归表达式为：。现有Hanoi塔问题的递归方程为： ，求h(n)的非递归表达式。解：利用给出的关系式，此时有：b=2, c=1, g(n)=1, 从n递推到1，有：二十六、通过键盘输入一个高精度的正整数n(n的有效位数240)，去掉其中任意s个数字后，剩下的数字按原左右次序将组成一个新的正整数。编程对给定的n 和s，寻找一种方案，使得剩下的数字组成的新数最小。【样例输入】178543S=4【样例输出】13解答：为了尽可能地逼近目标，我们选取的贪心策略为：每一步总是选择一个使剩下的数最小的数字删去，即按高位到低位的顺序搜索，若各位数字递增，则删除最后一个数字，否则
28、删除第一个递减区间的首字符。然后回到串首，按上述规则再删除下一个数字。重复以上过程s次，剩下的数字串便是问题的解了。具体算法如下：输入s, n;while（ s 0 ） i=1; /从串首开始找while (i length(n) & (ni1)& (n1=0) delete(n,1,1); /删去串首可能产生的无用零输出n;二十七、 所以f(n)与g(n)是同阶的： 二十八、f(n) = n, g(n) = log n f(n)是g(n)的高阶，所以有二十九、f(n) = nlog n, g(n) = log n f(n)是g(n)的高阶，所以有三十、f(n) = 2n, g(n) = n2
29、 f(n)是g(n)的高阶，所以有三十一、f(n) = log2n, g(n) = logn2f(n)是g(n)的高阶，所以有三十二、求证：证明：先证 ，即证 使得当 时，因为显然所以有 再证 。即证 使得当 时， 。因为 ，所以这个c只能取0和1之间的数，暂取c = 1/2。当 ， ， 。以下用数学归纳法证明当 时， 。 假设当 ，( )时，有 当 时， 所以 ，则综合之前已证 有 。三十三、在一个66的棋盘上，共放置12颗棋子，每个格子最多只能放一个棋子，要求每一行，每一列以及两条主对角线上恰好都是两颗棋子。请用回溯法输出所有可能的布局。在不考虑对称的情况下，共有多少种布局？void Backtrack( int num_chessman )if ( num_chessman 12 ) if ( Ok( x ) ) /是否问题可行解(满足已知条件) sum +; for ( int i=0; i12; i+ ) coutxi0 xi1endl; else for ( int i=0; i6; i+ )for ( int j=0; j6; j+ ) xnum_chessman0 = i; xnum_chessman1 = j; if ( suitable(i,j) ) / (i,j)放下棋子是否违反规则 Backtrack( num_chessman+1 );
