《算法与分析平时作业-答案.doc》由会员分享，可在线阅读，更多相关《算法与分析平时作业-答案.doc（11页珍藏版）》请在金锄头文库上搜索。
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 = l) int m = (l+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
2、 (x l) int m = (l+r)/2; if (x = am) return m; if (x 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 - an-1 (3) 将a0: n
3、-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)中元素个数的求解是个递归的过程。设set(n
4、)中的元素个数为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#includeint main() int n; int i,j,s; int buf106; char *in=input.txt,*out=output.txt; FILE *ip,*op; if(ip=fopen(in,r)=NULL)return 1; if(op=fopen(out,w)=NULL)return 2; fscanf(ip,%d,&n); fc
5、lose(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(pause);*/ return 0;4、设计一个算法，找出由n个数组成的序列的最长单调递增子序列的长度。答： #include #define m 10 /快速排序 void QuickSort(int R,int s,int t) int i=s,j=t; int tm
6、p; if(si&Rj=tmp) j-; Ri=Rj; while(ij&Ri=tmp) i+; Rj=Ri; Ri=tmp; QuickSort(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;in;i+) c0i=0; ci0=0; for(i=0;in;i+) for(j=0;j=cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; void LCS(int i,int j,int
7、 *x,int bmm) if(i0|j0) return; if(bij=1) LCS(i-1,j-1,x,b); coutxi ; else if(bij=2) LCS(i-1,j,x,b); else LCS(i,j-1,x,b); void main() int xm,ym,d; cout请输入元素个数d; cout请输入元素endl; for(int i=0;ixi; 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、会场
8、安排问题：假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。对于给定的n个待安排的活动，计算使用最少会场的个数。每个活动i都有一个开始时间和结束时间，分别表示为b(i)，f(i)。答： #include using 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
9、,j; cout输入待安排活动数:k; cout输入待安排活动的开始时间和结束时间:endl; /输入活动时间 /活动时间排序for(i=1;i=k;i+) for(j=i;jaj.b) swap(ai,aj);if(ai.b=aj.b)if(ai.faj.f) swap(ai,aj); int int sum=1;/使用的会场数初始化 int n; a1.no=sum; for(i=2;i=k;i+) for(n=1;ni;n+) if(an.no!=0&an.f=ai.b) ai.no=an.no; an.no=0;/已经安排过的活动就不再比较 break; if(n=i) sum+=1;
10、 ai.no=sum; cout输出最少会场数:nsumendl; system(pause); 6、最优分解问题：设n是一个正整数。现要求将n分解为若干个互不相同的自然数的和，使得这些自然数的乘积最大。设计一个算法，得到最优分解方案。 分析：我们知道如果a+b=常数，则|a-b|越小，a*b越大。 贪心策略：将n分成从2开始的连续自然数的和。如果最后剩下一个数，将此数在后项优先的方式下均匀地分给前面各项。答： void dicomp(int n, int a) int k = 1; if (n 3) a1 = 0; return; if (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，即。答： #includeint n,c; int a100; int current100; /存放当前选择的情况 int best100; /存放最后选择的子集合，besti=1，表示包含，反之即不包含。 int d=1; /判断有无满足的情况 int d2=0; /是否已经选出子集和 voi
