算法与分析平时作业答案

1、平时作业1、给定下述二分搜索算法，请判断算法的正确性，指出错误算法的产生原因。 a) int BinarySearch(Type a, const Type& x, int l, int r) while (r >= l) int m = (l+r)/2; if (x = am) return m; if (x < am) r = m-1; else l = m+1; return -1; 答：正确b) int BinarySearch(Type a, const Type& x, int l, int r) while (r >= l) int m = (l

2、+r)/2; if (x = am) return m; if (x < am) r = m+1; else l = m-1; return -1; 答：错误if (x < am) r = m+1; 当查找的元素在中间元素的左边时，右指针应该为m-1位置，修改成if (x < am) r = m+1; else l = m+lc) int BinarySearch(Type a, const Type& x, int l, int r) while (r > l) int m = (l+r)/2; if (x = am) return m; if (x <

3、 am) r = m-1; else l = m+1; return -1; 答：错误。while (r > l) 要考虑到 数组只有一个元素的情况 所以应该是 r>=l ;2、O(1)空间子数组环卫算法：设a0:n-1是一个n维数组，k（1 k n-1）是一个非负整数。试设计一个算法将子数组a0 : k-1与ak+1 : n-1换位。要求算法在最坏情况下耗时O(n)，且只用O(1)的辅助空间。答：最简单的方法就是循环(n-k-1)次，将a数组的末尾数字插入到a0之前。具体做法： (1) 首先开辟一个额外空间temp用于存放每一次a数组的末尾数据。 (2) temp <- a

4、n-1 (3) 将a0: n-2 每个数据都依次向后移动一位赋值给a1: n-1。 (4) a0 <- temp (5) 循环执行(2) -(4) 步 (n-k+1)次。代价分析： 时间代价 O(n-1)*(n-k+1) 即O(n2)数量级；空间代价： O（1）3、定义： 给定一个自然数n，由n开始依次产生半数集set(n)中的元素如下： 1）； 2）在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半； 3）按此规则进行处理，直至不能再添加新的自然数为止。 例如 。其中共有6个元素。 半数集问题：对于给定的n，求半数集set(n) 中元素的个数。答：半数集set(n)中元素个

5、数的求解是个递归的过程。设set(n)中的元素个数为f(n)，则显然有递归表达式：f(n)=1+f(i)，i=1,2n/2。即半数集set(n)元素个数f(n)=1+f(1)+f(2)+.+f(floor(n/2). 用递推法求解。C语言代码如下：#include<stdio.h>#include<stdlib.h>int main() int n; int i,j,s; int buf106; char *in="input.txt",*out="output.txt" FILE *ip,*op; if(ip=fopen(in,

6、"r")=NULL)return 1; if(op=fopen(out,"w")=NULL)return 2; fscanf(ip,"%d",&n); fclose(ip); buf1=1; buf2=2; buf3=2; for(i=4;i*2<=n;i+) s=1; for(j=1;j<=i/2;j+) s+=bufj; bufi=s; s=1; for(j=1;j<=n/2;j+) s+=bufj; fprintf(op,"%d",s); fclose(op);/* system(&

7、quot;pause");*/ return 0;4、设计一个算法，找出由n个数组成的序列的最长单调递增子序列的长度。答： #include<iostream.h> #define m 10 /快速排序 void QuickSort(int R,int s,int t) int i=s,j=t; int tmp; if(s<t) tmp=Rs; while(i!=j) while(j>i&&Rj>=tmp) j-; Ri=Rj; while(i<j&&Ri<=tmp) i+; Rj=Ri; Ri=tmp; Qu

8、ickSort(R,s,i-1); QuickSort(R,i+1,t); /找出最长公共子序列 void LCSLength(int x,int y,int n,int cmm,int bmm) int i,j; for(i=0;i<n;i+) c0i=0; ci0=0; for(i=0;i<n;i+) for(j=0;j<n;j+) if(xi=yj) cij=ci-1j-1+1; bij=1; else if(ci-1j>=cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; void LCS(int i,int j,in

9、t *x,int bmm) if(i<0|j<0) return; if(bij=1) LCS(i-1,j-1,x,b); cout<<xi<<" " else if(bij=2) LCS(i-1,j,x,b); else LCS(i,j-1,x,b); void main() int xm,ym,d; cout<<"请输入元素个数"<<endl; cin>>d; cout<<"请输入元素"<<endl; for(int i=0;i<

10、d;i+) cin>>xi; yi=xi; int cmm=0,bmm=0; QuickSort(x,0,d-1); LCSLength(x,y,d,c,b); cout<<"最长单调递增子序列为："<<endl; LCS(d-1,d-1,x,b); 5、会场安排问题：假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。对于给定的n个待安排的活动，计算使用最少会场的个数。每个活动i都有一个开始时间和结束时间，分别表示为b(i)，f(i)。答： #include<iostream> us

11、ing namespace std;#define M 50/最大活动数struct Active int b;/开始时间 int f;/结束时间int no;/预安排会场号 aM; /两元素交换位置 void swap(Active &a,Active &b) Active t=a; a=b; b=t; void main() int k, i,j; cout<<"输入待安排活动数:"<<endl;cin>>k; cout<<"输入待安排活动的开始时间和结束时间:"<<endl

12、; /输入活动时间 /活动时间排序for(i=1;i<=k;i+) for(j=i;j<=k;j+) if(ai.b>aj.b) swap(ai,aj);if(ai.b=aj.b)if(ai.f>aj.f) swap(ai,aj); int int sum=1;/使用的会场数初始化 int n; a1.no=sum; for(i=2;i<=k;i+) for(n=1;n<i;n+) if(an.no!=0&&an.f<=ai.b) ai.no=an.no; an.no=0;/已经安排过的活动就不再比较 break; if(n=i) su

13、m+=1; ai.no=sum; cout<<"输出最少会场数:n"<<sum<<endl; system("pause"); 6、最优分解问题：设n是一个正整数。现要求将n分解为若干个互不相同的自然数的和，使得这些自然数的乘积最大。设计一个算法，得到最优分解方案。 分析：我们知道如果a+b=常数，则|a-b|越小，a*b越大。 贪心策略：将n分成从2开始的连续自然数的和。如果最后剩下一个数，将此数在后项优先的方式下均匀地分给前面各项。答： void dicomp(int n, int a) int k = 1; if

14、 (n < 3) a1 = 0; return; if (n < 5) ak = 1; a+k = n - 1; return; a1 = 2; n -= 2;while (n > ak) k+; ak = ak - 1 + 1; n -= ak; if (n = ak) ak+; n-; for (int i = 0; i < n; i+) ak - i+; 7、子集和问题：设是n个正整数的集合，c是一个正整数。那么是否存在S的一个子集S1，使得子集中元素之和等于c，即。答： #include<stdio.h>int n,c; int a100; int

15、current100; /存放当前选择的情况 int best100; /存放最后选择的子集合，besti=1，表示包含，反之即不包含。 int d=1; /判断有无满足的情况 int d2=0; /是否已经选出子集和 void Back(int m,int count); int main() int i,j; scanf("%d %d",&n,&c); for(i=0;i<n;i+) scanf("%d",&ai); currenti=besti=0; Back(0,0); if(d) printf("no s

16、olutionn"); for(j=0;j<n;j+) /输出满足情况的子集和 if(bestj=1) printf("%dtt",aj); void Back(int m,int count) int k; if(m>n)return; if(count=c) d=0; /有满足的子集和 if(d2) return 0; for(k=0;k<=m;k+) bestk=currentk; d2=1; return 0; else currentm=1; /选入子集和 count+=am; Back(m+1,count); currentm=0;

17、/不选入子集和 count=count-am; Back(m+1,count); 8、设序列是序列和的最长公共子序列。a) 请说明最长公共子序列具有最优子结构性质。b) 设cij记录序列i和的最长公共子序列的长度。由最长公共子序列问题的最优子结构性质建立子问题最优值cij的递归关系。c) 写出寻找最长公共子序列的算法。答： 最长公共子序列问题具有最优子结构性质： 1、若 xm = yn ， 则 zk = xm = yn，且 Zk-1 是 Xm-1 和 Yn-1 的最长公共子序列 2、若 xm != yn ，且 zk != xm , 则 Z 是 Xm-1 和 Y 的最长公共子序列 3、若 xm

18、!= yn , 且 zk != yn , 则 Z 是 Yn-1 和 X 的最长公共子序列 由性质导出子问题的递归结构： 当 i = 0 , j = 0 时 , cij = 0 当 i , j > 0 xi = yi 时 , cij = ci-1j-1 + 1 当 i , j > 0 xi != yi 时 , cij = max cij-1 , ci-1j public class LSC private int c,b; private int m,n; private char A,B; public LSC(char A,char B) this.A=A; this.B=B;

19、m=A.length; n=B.length; c=new intm+1n+1; b=new intm+1n+1; for(int i=0;i<n+1;i+) c0i=0; for(int j=0;j<m+1;j+) cj0=0; public LSC() public int LSCLength() for(int i=1;i<m+1;i+) for(int j=1;j<n+1;j+) /* 如果 Ai-1和j-1是相等的话*/ if(Ai-1=Bj-1) cij=ci-1j-1+1; bij='0' /* * 情况 */ else if(ci-1j&

20、gt;=cij-1) cij=ci-1j; bij='1' /* * 情况 */ else cij=cij-1; bij='2' return cmn; public void print(int i,int j) if(i<=0|j<=0) return; else if(bij='0') print(i-1,j-1); System.out.print(Ai-1); else if(bij='1') print(i-1,j); else print(i,j-1); public int LSCLength2(int

21、 i,int j) if(i<0|j<0) return 0; else if(Ai=Bj) return 1+LSCLength2(i-1,j-1); else int a1=LSCLength2(i,j-1); int a2=LSCLength2(i-1,j); return a1>a2?a1:a2; public static void main(String args) char A='g','f','d','a','s','d','a','c

22、9; charB='g','c','f','a','t','0','c','c' LSC lsc=new LSC(A,B); System.out.println(lsc.LSCLength2(7,7); 9、记矩阵连乘积 。 确定计算A1:n的最优计算次序，使得所需数乘的次数最少。 1、说明矩阵连乘计算次序问题的最优解包含着其子问题的最优解，即最优子结构性质。 2、该问题具备子问题的重叠性质。 3、说明采用动态规划方法可以解决该问题。 4、设计该算法，分析算法的复杂

23、性。答：计算 Ai:j的最优次序所包含的计算矩阵子链 Ai:k和 Ak+1:j的次序也是最优的。 设计算 Ai:j，1ijn，所需要的最少数乘次数 mi,j，则原问 题的最优值为 m1,n 当 i=j 时，Ai:j=Ai，无需计算，因此，mi,j=0，i=1,2,n 当 i<j 时，利用最优子结构性质计算 mi,j . 设 Ai:j的最优次序在 Ak 和 Ak1 之间断开，则 ，i-1kj其中 Ai 的维数为 pi-1×pj k 的位置只有 j-i 种可能, i, i+1, , j-1，其中使计算量最小的那个位置 为最优解，数乘次数 mi,j最小值为问题的最优值可以递归地定义

24、mi,j为： ，= mini，k + 0k +1, j +i-1kj i=ji<j 将最优值 mi j对应的断开位置记为 si j，则可递归的由 si j构造出相应的最优 解 对于 1ijn 不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的 个数最多只有 由此可见，在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态 规划算法求解的又一显著特征。 用动态规划算法解此问题， 可依据其递归式以自底向上的方式进行计算。在计算 过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只 要简单查一下，从而避免大量的重复计算最终得到多项式时间的算法 matrixCh

25、ain 已经记录了构造最优解所需的全部信息。从 s1n 可知，计算 A1:n的最优加括号方式为 ( A 1 : s1n ) (As1n+1: n ) 计算 A 1 : s1n 的最优加括号方式为 (A 1 : s1s1n )(A s1s1n +1 : s1n )10、考虑分数背包问题，定义如下：给出n 个大小为 s1, s2, , sn , 价值为v1, v2, , vn 的物品， 并设背包容量为C, 要找到非负实数x1, x2, , xn, 使和 在约束下最大。写出求解问题的贪心算法，估计算法的时间复杂性。答：从问题的某一初始解出发；while 能朝给定总目标前进一步 do 求出可行解的 一个解元素； 由所有解元素组合成问题的一个