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

*分析过程：

由于主管道是东西走向，那么通过主轴线的y坐标可唯一确定其位置。

由带权中位数问题可知，其中位数即为管道最优解。

用一个线性时间选择找中位数算法，即可在O(n)时间内解此问题。

这里采用RandomizedSelect算法。

油井数可能为奇数或者偶数

奇数则取其中位数

偶数则取两个中位数中的任意一个

*/

#include

#include

#include

#define LEN 100

using namespace std;

int Random(int p, int r){//随机化

return rand()*(r-p)/32767+p;

}

void Swap(int &a, int &b){

int temp = a;

a = b;

b = temp;

}

int Partition(int y[LEN], int p, int r){

int i = p, j = r+1;

int x = y[p];

while(true){

while(y[++i]

while(y[--j]>x);

if(i>=j) break;

Swap(y[i],y[j]);

}

y[p] = y[j];

y[j] = x;

return j;

}

int RandomizedPartition(int y[LEN], int p, int r){

int i = Random(p,r);

Swap(y[i],y[p]);

return Partition(y,p,r);

}

int RandomizedSelect(int y[LEN], int p, int r, int k){

if(p==r) return y[p];

int i = RandomizedPartition(y,p,r);

int j = i-p+1;

if(k<=j) return RandomizedSelect(y,p,i,k);

else return RandomizedSelect(y,i+1,r,k-j);

}

void main(){

int n;//油井数

int sum = 0;//管道长度总和

int y[LEN];//油井y坐标

int dy;//油井y坐标中位数

freopen("input.txt","r",stdin);//打开一个输入流，读取input.txt文件

freopen("output.txt","w",stdout);//打开一个输出流，写output.txt文件

scanf("%d",&n);//读取油井数

for(int i=0;i

scanf("%d",&y[i]);//x坐标在此题中无用，而y坐标在x坐标之后写入。因此两次写入一样的数组y[LEN]

scanf("%d",&y[i]);

}

dy = RandomizedSelect(y, 0, n-1, (n+1)/2);//中位数求取

for(i=0; i

sum+=abs(y[i]-dy);//计算管道和

printf("%d\n",sum);

fclose(stdin);//关闭输入流

fclose(stdout);//关闭输出流

}

窗体底端

窗体顶端

窗体底端

邮局选址的分治算法，C++语言

2008-11-25 13:28

提问者：哆啦没做梦 | 悬赏分：200 | 浏览次数：1080次

一道我们算法课上留的作业题，大概内容是：某市有n个小区（坐标给出），每个小区的住户数不相同（带权）。现有一邮局将建在某小区内，要求到各个用户的距离之和最短，用分治法解答。

请高手帮下忙，很急，在线等。请注解详细点，采用后积分倾囊相赠！

问题补充：

必须用分治法的，因为是分治法那章留的题。

分治是在小区坐标的地方，把横纵坐标分开来计算，好像是利用中位点求解的。

拜托了！

2008-11-25 14:43

最佳答案

代码如下:

#include

#include

#include

#include

using namespace std;

const int MAXN = 10000;

typedef struct {int idx, l;} Rst;

int n, x[MAXN], y[MAXN], num[MAXN];

Rst f(int s, int e)

//分治求解, 参数s,e为小区编号, 函数求出从s到e编号的小区中, 哪一个到所有小区的加权距离和最短, 并返回距离和与小区编号

{

int i;

if (s == e) //如果区间里面只有一个小区, 显然返回该小区

{

Rst rst = {s, 0};

for (i=0; i

return rst;

}

else //否则, 分别找出左半和右半区间中的最佳小区, 谁更优, 就返回谁

{

Rst a = f(s, (s+e)/2), b = f((s+e+1)/2, e);

return a.l

}

}

int main()

{

int i, j, k;

cout << "请输入小区数量:";

cin>>n;

cout<<"请分别输入"<个小区的x坐标,y坐标,住户数\n";

for (i=0; i

{

cout<<"第"<个小区:";

cin>>x[i]>>y[i]>>num[i];

}

Rst rst = f(0, n-1); //0到n-1为所有小区编号, 则返回值就是最终结果

cout<<"到各个用户的距离之和最短的小区编号: "<该小区到各个用户的距离之和: "<

return 0;

}

//最后说两句, 算法时间复杂度O(n^2), 其实就跟枚举没有区别..

//这个题目布置的不好 根本体现不出分治算法的优势

赞同

4

向TA求助

回答者： deitytoday | 五级

擅长领域： C/C++ 程序设计

参加的活动： 暂时没有参加的活动

提问者对于答案的评价：

非常感谢，主函数有一点小问题，刚刚改了下已经能运行了。

分给你了！

相关内容

∙ 2008-10-7 大家帮帮忙，用递归算法的分治策略求一个数组的众数，用c语言编写，告诉... 1

∙ 2007-9-19 邮局把信件自动分检 使用的是哪种计算机技术？ A机器翻译B自然语言理解C... 3

∙ 2009-6-10 学校超市选址，c语言 采用数据结构编写 1

∙ 2009-5-31 C语言数据结构 超市选址

∙ 2011-5-21 求用FLOYD算法解此矩阵，并附带floyd的c语言程序，矩阵中M_A_X表两点不... 2

更多关于邮局选址问题代码？的问题>>

查看同主题问题： 算法 c++ c++ 语言 邮局 选址

等待您来回答

∙ 0回答大三的线性代数课件

∙ 2回答请问谁有建筑结构基础与识图，中国建筑工业出版社的第二版的课件ppt,...

∙ 0回答高一英语必修一unit3 Discovering useful structures 3 （人教版）

∙ 0回答人教版六年级数学目标检测第三单元检测

∙ 2回答我昨天才发现我老公我婚外情的，我只找到他最近特别爱找茬，昨天无意...

∙ 0回答100高分跪求2011年11月的证券从业资格考试基础知识，证券交易，基金，投...

∙ 1回答那里有优秀的ppt化学课件呢

∙ 1回答人教版高一地理必修一1

更多等待您来回答的问题>>

其他回答 共2条

2008-11-25 13:37 rupxup | 三级

为什么用分支法呢？别的行不行？

赞同

0

2008-11-25 14:55 高金山 | 十四级

邮局选址问题

本文来源：https://www.2haoxitong.net/k/doc/aa5968c14028915f804dc262.html