算法与分析报告平时作业

算法与分析报告平时作业

ID:29445358

大小:186.00 KB

页数:17页

时间:2018-12-19

算法与分析报告平时作业_第1页
算法与分析报告平时作业_第2页
算法与分析报告平时作业_第3页
算法与分析报告平时作业_第4页
算法与分析报告平时作业_第5页
资源描述:

《算法与分析报告平时作业》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库

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[m])returnm;if(x

2、1;}return-1;}答:错误,if(xl){intm=(l+r)/2;if(x==a[m])returnm;if(x=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(

3、1)的辅助空间。精彩文档实用标准文案答:算法分析:当v[k]左边子数组的长度等于右边的子数组长度时,直接将两个子数组对应的元素互换即可当左边子数组长度小于右边子数组长度时,将左边子数组与右边子数组右边的等长子数组对换,再对结果递归调用对换函数当右边子数组长度小于左边子数组长度时,将右边子数组与左边子数组左边的等长子数组对换,再对结果递归调用对换函数通过分析,可知只需要利用保存元素对换时的交换空间即可,空间复杂度为O(1),子数组对换时时间复杂度不会超过O(n)#include#include#include#include

4、ream>usingnamespacestd;//对应互换v的left_low-left_high和right_low-right_highvoidSwap(vector&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;}//分治算法,每次选最小的子数组对应交换voi

5、dExchange(vector&v,intk,intlow,inthigh){if(low

6、h+low-k-1,k+1,high);Exchange(v,k,high+low-k,high);}}return;}精彩文档实用标准文案intmain(){vectorv;intn,k;while(scanf("%d%d",&n,&k)==2){v.resize(n);for(inti=0;i

7、"Afterexchangesubarray:");for(intk=0;k

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

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

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