《算法设计与分析计算题》由会员分享，可在线阅读，更多相关《算法设计与分析计算题（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 与数组的中间
2、元素进行比较，如果，2nA 2nvA 则在前半部分元素中搜索 v；若，则搜索成功；否则在后半部分数组中搜索 v。2nvA 非递归算法： 输入：递减数组 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。
3、输出：v 在 A 中的位置 pos，或者不在 A 中的消息（-1） 。 步骤：【3 分】int BinarySearch(int A,int left,int right,int v) int mid; if (leftAmid) return BinarySearch(A,left,mid-1,v); else return BinarySearch(A,mid+1,right,v); else return -1; (4)使用上述算法对（1）所得到的结果搜索如下元素，并给出搜索过程：18，31，135。解：解：搜索 18：首先与 27 比较，1827，在前半部分搜索；再次 32 比较，31
4、29，此时只有一个元素，未找到，返回-1。搜索 135：首先与 27 比较，13527，在前半部分搜索；再次 32 比较，13532，在前 半部分搜索；与 135 比较，相同，返回 0。二、排序和查找是常用的计算机算法。按照要求完成以下各题：二、排序和查找是常用的计算机算法。按照要求完成以下各题：（1）对数组 A=15，9，115，118，3，90，27，25，5，使用合并排序方法将其排成递减序。（2）若改变二分搜索法为三分搜索法，即从一个递减序列 A 中寻找元素 Z，先与元素比较，若，则在前面个元素中寻找 Z；否则与比较，总之使余下的 3nA 3nZA 3n23nA序列为个元素。给出该方法的
5、伪代码描述。 3n(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 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
6、,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; return -1; （3）搜索 118：11827，所以 right3；118115，所以 right1；118118，找到。 搜索 31：3127，所以 right3；31du+w(u,v) then dv=du+wu,v;pv=upv=u dijk
7、stra(G,w,s) Init-single-source(G,s) S= Q=VG while Q1;i-) int jMax=min(wi-1,c);for (j=0;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：当前最优值void backtrack(int i) /回溯法 i 初值 1 if(i n) /到达叶结点 bestp = cp; return; if(cw + wi bestp) /搜索右子树 backtrac
8、k(i+1); 八、已知八、已知， 1( ) *() iik kijr rAa k k=1=1，2 2，3 3，4 4，5 5，6 6，r r1 1=5=5，r r2 2=10=10，r r3 3=3=3，r r4 4=12=12，r r5 5=5=5，r r6 6=50=50，r r7 7=6=6，求矩阵链积，求矩阵链积A A1 1AA2 2AA3 3AA4 4AA5 5AA6 6的最佳求积顺序。的最佳求积顺序。 （要求：给出计算步骤）（要求：给出计算步骤）解：解：求解矩阵为：1234561015033040516552010203603302430195030180930177040300
9、0186050150060因此，最佳乘积序列为（A1A2） （A3A4） （A5A6） ） ，共执行乘法 2010 次。123456101224220222230344404450560九、回答如下问题：（1）什么是算法？算法的特征有哪些？答：算法是解决某类问题的一系列运算的集合。特征：具有有穷行、可行性、确定性、0 个或者多个输入、1 个或者多个输出。（2）什么是 P 类问题？什么是 NP 类问题？请描述集合覆盖问题的近似算法的基本思想。解：解：用确定的图灵机可以在多项式实践内可解的判定问题称为 P 类问题。 用不确定的图灵机在多项式实践内可解的判定问题称为 P 类问题。 集合覆盖问题的近似
10、算法采用贪心思想：对于问题，每次选择 F 中覆盖了尽可能 多的未被覆盖元素的子集 S，然后将 U 中被 S 覆盖的元素删除，并将 S 加入 C 中，最后得到 的 C 就是近似最优解。十、十、 、多段图问题：设、多段图问题：设 G G(V(V，E)E)是一个赋权有向图，其顶点集是一个赋权有向图，其顶点集 V V 被划分成被划分成 k2k2 个不相交的个不相交的子集子集 V Vi i：，其中，其中，V V1 1和和 V Vk k分别只有一个顶点分别只有一个顶点 s s（称为源）和一个顶点（称为源）和一个顶点 t t（称为汇）（称为汇） ，1ik 图中所有的边（图中所有的边（u,vu,v） ，。求由
11、。求由 s s 到到 t t 的最小成本路径。的最小成本路径。 （2525 分）分）iuV1ivVa)给出使用动态规划算法求解多段图问题的基本思想。b)使用上述方法求解如下多段图问题。1234568791110129732486356241st221171145V1V2V3V4V5解：解：（1）基本思想：设 P(i,j)是从 Vi 中的节点 j 到汇点 t 的最小成本路径，Cost(i,j)是其成本。则。边界条件是（1）若i+1Cost(i,j)=minc(j,h)+Cost(i+1,h)|hV ,(j,h)Eh=t，则 Cost(h,t)0；（2）Cost(k-1,j)c(j,t)。 （2）
12、求解过程可以表示为：1234568791110129732486356241st221171145V1V2V3V4V516,2/37,79,618,815,87,105,107,10/114,122,121,12其中每个节点标示的序偶(p,q)中，p 表示节点到 t 的成本，q 表示后继节点的编号。从而， 最优路径为：1271012 和 1361012，成本为 16。十一设十一设x x1 1、x x2 2、x x3 3是一个三角形的三条边，而且是一个三角形的三条边，而且 x x1 1+x+x2 2+x+x3 3=14=14。请问有多少种不同的三角。请问有多少种不同的三角形？给出解答过程。形？给
13、出解答过程。解：由于x1、x2、x3是三角形的三条边，从而 xi+xjxk，|xi-xj|max) max=Ai; if (Ai1 时）。写成递归函数有：int fib(int n) if (n=0) return 0;if (n=1) return 1;if (n1) return fib(n-1)+fib(n-2); 1245637910128131411151234567891011121314151 245 6 3 79 1012 81314111512 45 6 3 79 1012 8131411151 2 3 45 679 1012 8131411151 2 45 6 3 79 1
14、012 81314111567571 2 3 456 79 1012 81314111561 2 3 45 6 12 79 1081314111551 2 3 45 6 79 1012 81314111541 2 35 6 7 49 1012 81314111551 2 3 45 6 7 89 10121314111531 2 3 45 6 7 89 10121314111521 2 3 45 6 7 89 10121513141131 2 3 45 689 10 7 121314111531 2 3 45 6 7 89 10111213141511 2 3 45 6 7 8910121314
15、111531 2 3 45 6 7 89 10111213141521 2 3 45 6 7 89 1011121314150十五、求证：十五、求证：O(f(n)+O(g(n)O(f(n)+O(g(n) = = O(maxf(n),g(n)O(maxf(n),g(n)证明：对于任意证明：对于任意 f1(n)f1(n) O(f(n)O(f(n) ，存在正常数，存在正常数 c1c1 和自然数和自然数 n1n1，使得对所有，使得对所有 n nn1n1，有，有f1(n)f1(n) c1f(n)c1f(n) 。类似地，对于任意类似地，对于任意 g1(n)g1(n) O(g(n)O(g(n) ，存在正常数，存在正常数 c2c2 和自然数和自然数 n2n2，使得对所有，使得对所有 n nn2n2，有有 g1(n)g1(n) c2g(n)c2g(n) 。令令 c3=maxc1,c3=maxc1, c2c2， n3n3 =maxn1,=maxn1,
