算法分析中的几个经典例子

《算法分析中的几个经典例子》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、*分析过程：由于主管道是东西走向，那么通过主轴线的y坐标可唯一确定其位置。由带权中位数问题可知，其中位数即为管道最优解。用一个线性时间选择找中位数算法，即可在O(n)时间内解此问题。这里采用RandomizedSelect算法。油井数可能为奇数或者偶数奇数则取其中位数偶数则取两个中位数中的任意一个*/#include#include#include#defineLEN100usingnamespacestd;intRandom(intp,intr){//随机化returnrand()*(r-p)/32767+p

2、;}voidSwap(int&a,int&b){inttemp=a;a=b;b=temp;}intPartition(inty[LEN],intp,intr){inti=p,j=r+1;intx=y[p];while(true){while(y[++i]x);if(i>=j)break;Swap(y[i],y[j]);}y[p]=y[j];y[j]=x;returnj;}intRandomizedPartition(inty[LEN],intp,intr){inti=Random(p,r);Swap(y[i],y[p])

3、;returnPartition(y,p,r);}intRandomizedSelect(inty[LEN],intp,intr,intk){if(p==r)returny[p];inti=RandomizedPartition(y,p,r);intj=i-p+1;if(k<=j)returnRandomizedSelect(y,p,i,k);elsereturnRandomizedSelect(y,i+1,r,k-j);}voidmain(){intn;//油井数intsum=0;//管道长度总和inty[LEN];//油井y坐标intdy;//油井y坐标中位数

4、freopen("input.txt","r",stdin);//打开一个输入流，读取input.txt文件freopen("output.txt","w",stdout);//打开一个输出流，写output.txt文件scanf("%d",&n);//读取油井数for(inti=0;i

5、n;i++)sum+=abs(y[i]-dy);//计算管道和printf("%d",sum);fclose(stdin);//关闭输入流fclose(stdout);//关闭输出流}窗体底端窗体顶端窗体底端邮局选址的分治算法，C++语言2008-11-2513:28提问者：哆啦没做梦

6、悬赏分：200

7、浏览次数：1080次一道我们算法课上留的作业题，大概内容是：某市有n个小区（坐标给出），每个小区的住户数不相同（带权）。现有一邮局将建在某小区内，要求到各个用户的距离之和最短，用分治法解答。请高手帮下忙，很急，在线等。请注解详细点，采用后积分倾囊相赠！问题补充：

8、必须用分治法的，因为是分治法那章留的题。分治是在小区坐标的地方，把横纵坐标分开来计算，好像是利用中位点求解的。拜托了！2008-11-2514:43最佳答案代码如下:#include#include#include#includeusingnamespacestd;constintMAXN=10000;typedefstruct{intidx,l;}Rst;intn,x[MAXN],y[MAXN],num[MAXN];Rstf(ints,inte)//分治求解,参数s,e为小区编号,函数求出从

9、s到e编号的小区中,哪一个到所有小区的加权距离和最短,并返回距离和与小区编号{inti;if(s==e)//如果区间里面只有一个小区,显然返回该小区{Rstrst={s,0};for(i=0;i

10、nti,j