算法与分析平时作业

平时作业1、给定下述二分搜索算法，请判断算法的正确性，指出错误算法的产生原因。a)intBinarySearch(Typea[],constType&x,intl,intr){while(r=l){intm=(l+r)/2;if(x==a[m])returnm;if(xa[m])r=m-1;elsel=m+1;}return-1;}答：正确b)intBinarySearch(Typea[],constType&x,intl,intr){while(r=l){intm=(l+r)/2;if(x==a[m])returnm;if(xa[m])r=m+1;elsel=m-1;}return-1;}答：错误，if(xa[m])r=m-1;elsel=m+1;c)intBinarySearch(Typea[],constType&x,intl,intr){while(rl){intm=(l+r)/2;if(x==a[m])returnm;if(xa[m])r=m-1;elsel=m+1;}return-1;}答：错误，while(r=l){2、O(1)空间子数组环卫算法：设a[0:n-1]是一个n维数组，k（1≤k≤n-1）是一个非负整数。试设计一个算法将子数组a[0:k-1]与a[k+1:n-1]换位。要求算法在最坏情况下耗时O(n)，且只用O(1)的辅助空间。答：算法分析：当v[k]左边子数组的长度等于右边的子数组长度时，直接将两个子数组对应的元素互换即可当左边子数组长度小于右边子数组长度时，将左边子数组与右边子数组右边的等长子数组对换，再对结果递归调用对换函数当右边子数组长度小于左边子数组长度时，将右边子数组与左边子数组左边的等长子数组对换，再对结果递归调用对换函数通过分析，可知只需要利用保存元素对换时的交换空间即可，空间复杂度为O(1)，子数组对换时时间复杂度不会超过O(n)#includestdio.h#includestdlib.h#includevector#includeiostreamusingnamespacestd;//对应互换v的left_low-left_high和right_low-right_highvoidSwap(vectorint&v,intleft_low,intleft_high,intright_low,intright_high){inttemp;while(left_low=left_high){temp=v[left_low];v[left_low]=v[right_low];v[right_low]=temp;++left_low;++right_low;}return;}//分治算法，每次选最小的子数组对应交换voidExchange(vectorint&v,intk,intlow,inthigh){if(lowhigh){if((k-low+1)==(high-k)){//v[k]左右两个子数组长度相等，直接互换Swap(v,low,k,k+1,high);}elseif((k-low+1)(high-k)){//v[k]左边子数组长度小于右边子数组，将左边的子数组互换到右边子数组的右边Swap(v,low,k,low+high-k,high);Exchange(v,k,low,low+high-k-1);}else{//v[k]右边子数组换到左边子数组前部分Swap(v,low,high+low-k-1,k+1,high);Exchange(v,k,high+low-k,high);}}return;}intmain(){vectorintv;intn,k;while(scanf(%d%d,&n,&k)==2){v.resize(n);for(inti=0;in;++i){scanf(%d,&v[i]);}printf(Beforeexchangesubarray:\n);for(intj=0;jn;++j){printf(%d,v[j]);}printf(\n);Exchange(v,k,0,n-1);printf(Afterexchangesubarray:\n);for(intk=0;kn;++k){printf(%d,v[k]);}printf(\n);}return0;}3、定义：给定一个自然数n，由n开始依次产生半数集set(n)中的元素如下：1）()nsetn；2）在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半；3）按此规则进行处理，直至不能再添加新的自然数为止。例如(){6,16,26,126,36,136}setn。其中共有6个元素。半数集问题：对于给定的n，求半数集set(n)中元素的个数。答：#includeiostream.husingnamespacestd;inta[1001];intcomp(intn){inti;for(i=2;i=n;i++){if(i%2==0)a[i]=a[i/2]+a[i-1];elsea[i]=a[i-1];}returna[n];}intmain(){intn;cout请输入一个不大于1000的自然数：n=;cinn;for(inti=0;i=n;i++)a[i]=i;if(n=0||n1000)coutendl输入错误，请注意输入值n的范围.endl;else{coutendl半数集set(n)中的元素个数为：;coutcomp(n)endl;}return0;}4、设计一个算法，找出由n个数组成的序列的最长单调递增子序列的长度。答：#includeiostream.h#definem10//快速排序voidQuickSort(intR[],ints,intt){inti=s,j=t;inttmp;if(st){tmp=R[s];while(i!=j){while(ji&&R[j]=tmp)j--;R[i]=R[j];while(ij&&R[i]=tmp)i++;R[j]=R[i];}R[i]=tmp;QuickSort(R,s,i-1);QuickSort(R,i+1,t);}}//找出最长公共子序列voidLCSLength(intx[],inty[],intn,intc[m][m],intb[m][m]){inti,j;for(i=0;in;i++){c[0][i]=0;c[i][0]=0;}for(i=0;in;i++)for(j=0;jn;j++){if(x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}elseif(c[i-1][j]=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;}else{c[i][j]=c[i][j-1];b[i][j]=3;}}}voidLCS(inti,intj,int*x,intb[m][m]){if(i0||j0)return;if(b[i][j]==1){LCS(i-1,j-1,x,b);coutx[i];}elseif(b[i][j]==2)LCS(i-1,j,x,b);elseLCS(i,j-1,x,b);}voidmain(){intx[m],y[m],d;cout请输入元素个数endl;cind;cout请输入元素endl;for(inti=0;id;i++){cinx[i];y[i]=x[i];}intc[m][m]={0},b[m][m]={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)。答：#includeiostreamusingnamespacestd;#defineM50//最大活动数structActive{intb;//开始时间intf;//结束时间intno;//预安排会场号}a[M];//两元素交换位置voidswap(Active&a,Active&b){Activet;t=a;a=b;b=t;}voidmain(){intk;inti,j;cout输入待安排活动数:endl;cink;cout输入待安排活动的开始时间和结束时间:endl;//输入活动时间for(i=1;i=k;i++){cina[i].ba[i].f;a[i].no=0;}//活动时间排序for(i=1;i=k;i++){for(j=i;j=k;j++){if(a[i].ba[j].b)swap(a[i],a[j]);if(a[i].b==a[j].b){if(a[i].fa[j].f)swap(a[i],a[j]);}}}intsum=1;//使用的会场数初始化intn;a[1].no=sum;for(i=2;i=k;i++){for(n=1;ni;n++){if(a[n].no!=0&&a[n].f=a[i].b){a[i].no=a[n].no;a[n].no=0;//已经安排过的活动就不再比较break;}}if(n==i){sum+=1;a[i].no=sum;}}cout输出最少会场数:\nsumendl;system(pause);}6、最优分解问题：设n是一个正整数。现要求将n分解为若干个互不相同的自然数的和，使得这些自然数的乘积最大。设计一个算法，得到最优分解方案。分析：我们知道如果a+b=常数，则|a-b|越小，a*b越大。贪心策略：将n分成从2开始的连续自然数的和。如果最后剩下一个数，将此数在后项优先的方式下均匀地分给前面各项。答：voiddicomp(intn,int[]a){intk=1;if(n3){a[1]=0;return;}if(n5){a[k]=1;a[++k]=n-1;return;}a[1]=2;n-=2;while(na[k]){k++;a[k]=a[k-1]+1;n-=a[k];}if(n==a[k]){a[k]++;n--;}for(inti=0;in;i++)a[k-i]++;}7、子集和问题：设12{,,,}nSxxx是n个正整数的集合，c是一个正整数。那么是否存在S的一个子集S1，使得子集中元素之和等于c，即1xSxc。答：#includestdio.hintn,c;inta[100];intcurrent[100];//存放当前选择的情况intbest[100];//存放最后选择的子集合，best[i]=1，表示包含，反之即不包含。intd=1;//判断有无满足的情况intd2=0;//是否已经选出子集和voidBack(intm,intcount);intmain(){inti,j;scanf(%d%d,&n,&c);for(i=0;in;i++){scanf(%d,&a[i]);current[i]=best[i]=0;}Back(0,0);if(d)printf(nosolution\n);for(j=0;jn;j++)//输出满足情况的子集和{if(best[j]==1)printf(%d\t\t,a[j]);}}voidBack(intm,intcount){intk;if(mn)return;if(count==c){d=0;//有满足的子集和if(d2)return0;for(k=0;k=m;k++)best[k]=current[k];d2=1;return0;}else{current[m]=1;/