算法与分析平时作业 - 答案.doc

《算法与分析平时作业 - 答案.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、平时作业1、给定下述二分搜索算法，请判断算法的正确性，指出错误算法的产生原因。a)intBinarySearch(Typea[],constType&x,intl,intr){while(r>=l){intm=(l+r)/2;if(x==a[m])returnm;if(x=l){intm=(l+r)/2;if(x==a

2、[m])returnm;if(xl){intm=(l+r)/2;if(x==a[m])returnm;if(x

3、答：错误。while(r>l)要考虑到数组只有一个元素的情况所以应该是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)的辅助空间。答：最简单的方法就是循环(n-k-1)次，将a数组的末尾数字插入到a[0]之前。具体做法：(1)首先开辟一个额外空间temp用于存放每一次a数组的末尾数据。(2)temp<-a[n-1](3)将a[0

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

5、个数。答：半数集set(n)中元素个数的求解是个递归的过程。设set(n)中的元素个数为f(n)，则显然有递归表达式：f(n)=1+∑f(i)，i=1,2……n/2。即半数集set(n)元素个数f(n)=1+f(1)+f(2)+...+f(floor(n/2)).用递推法求解。C语言代码如下：#include#includeintmain(){intn;inti,j,s;intbuf[106];char*in="input.txt",*out="output.txt

6、";FILE*ip,*op;if((ip=fopen(in,"r"))==NULL)return1;if((op=fopen(out,"w"))==NULL)return2;fscanf(ip,"%d",&n);fclose(ip);buf[1]=1;buf[2]=2;buf[3]=2;for(i=4;i*2<=n;i++){s=1;for(j=1;j<=i/2;j++){s+=buf[j];}buf[i]=s;}s=1;for(j=1;j<=n/2;j++){s+=buf[j];}fprintf(op

7、,"%d",s);fclose(op);/*system("pause");*/return0;}4、设计一个算法，找出由n个数组成的序列的最长单调递增子序列的长度。答：#include#definem10//快速排序voidQuickSort(intR[],ints,intt){inti=s,j=t;inttmp;if(si&&R[j]>=tmp)j--;R[i]=R[j];while(i

8、p)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;i