算法与分析平时作业.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[m])returnm;if(x

2、;}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)，且

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

4、eam>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;}//分治算法，每次选最小的子数组对应交

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

6、v,low,high+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、ntf("Afterexchangesubarray:");for(intk=0;k