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

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

ID:56761136

大小:108.51 KB

页数:11页

时间:2020-07-07

算法与分析平时作业 - 答案.doc_第1页
算法与分析平时作业 - 答案.doc_第2页
算法与分析平时作业 - 答案.doc_第3页
算法与分析平时作业 - 答案.doc_第4页
算法与分析平时作业 - 答案.doc_第5页
资源描述:

《算法与分析平时作业 - 答案.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

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。