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

*分析过程：由于主管道是东西走向，那么通过主轴线的y坐标可唯一确定其位置。由带权中位数问题可知，其中位数即为管道最优解。用一个线性时间选择找中位数算法，即可在O(n)时间内解此问题。这里采用RandomizedSelect算法。油井数可能为奇数或者偶数奇数则取其中位数偶数则取两个中位数中的任意一个*/#include #include #include #define LEN 100using 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 yLEN, int p, int r)int i = p, j = r+1;int x = yp;while(true)while(y+ix&ix);if(i=j) break;Swap(yi,yj);yp = yj;yj = x;return j;int RandomizedPartition(int yLEN, int p, int r)int i = Random(p,r);Swap(yi,yp);return Partition(y,p,r);int RandomizedSelect(int yLEN, int p, int r, int k)if(p=r) return yp;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 yLEN;/油井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;in;i+)scanf(%d,&yi);/x坐标在此题中无用，而y坐标在x坐标之后写入。因此两次写入一样的数组yLENscanf(%d,&yi);dy = RandomizedSelect(y, 0, n-1, (n+1)/2);/中位数求取for(i=0; in; i+)sum+=abs(yi-dy);/计算管道和printf(%dn,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, xMAXN, yMAXN, numMAXN;Rst f(int s, int e) /分治求解, 参数s,e为小区编号, 函数求出从s到e编号的小区中, 哪一个到所有小区的加权距离和最短, 并返回距离和与小区编号 int i; if (s = e) /如果区间里面只有一个小区, 显然返回该小区 Rst rst = s, 0; for (i=0; in; i+) rst.l += numi * sqrt(xs-xi)*(xs-xi) + (ys-yi)*(ys-yi); return rst; else /否则, 分别找出左半和右半区间中的最佳小区, 谁更优, 就返回谁 Rst a = f(s, (s+e)/2), b = f(s+e+1)/2, e); return a.lb.l?a:b; int main() int i, j, k; cout n; cout请分别输入n个小区的x坐标,y坐标,住户数n; for (i=0; in; i+) cout第i+1xiyinumi; Rst rst = f(0, n-1); /0到n-1为所有小区编号, 则返回值就是最终结果 cout到各个用户的距离之和最短的小区编号: rst.idx+1n该小区到各个用户的距离之和: rst.l 查看同主题问题： 算法 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 | 三级 为什么用分支法呢？别的行不行？ 赞同02008-11-25 14:55 高金山 | 十四级 邮局选址问题 问题描述： 在一个按照东西和南北方向划分成规整街区的城市里，n个居民点散乱地分布在不同的街区中。用x坐标表示东西向，用y坐标表示南北向。各居民点的位置可以由坐标(x,y)表示。街区中任意2点(x1,y1)和(x2,y2)之间的距离可以用数值|x1-x2|+|y1-y2|度量。 居民们希望在城市中选择建立邮局的最佳位置，使n个居民点到邮局的距离总和最小。 编程任务： 给定n个居民点的位置,编程计算n个居民点到邮局的距离总和的最小值。 数据输入： 由文件input.txt提供输入数据。文件的第1行是居民点数n，1n10000。接下来n行是居民点的位置，每行2个整数x和y，-10000x，y10000。 结果输出: 程序运行结束时，将计算结果输出到文件output.txt中。文件的第1行中的数是n个居民点到邮局的距离总和的最小值。 输入文件示例 5 1 2 2 2 1 3 3 -2 3 3 输出文件示例 10解法：/lyflower/archive/2008/03/07/2156943.aspx/- By CQ.Xiao SCAU/- Nov.9th 2007#include iostreamusing namespace std;struct info unsigned dis; /最小值 unsigned r; /标号r之前（包括r）的村庄为一个辖区;/- Definition for Global-Variableunsigned village = 0, postoffice = 0; /number of village & postofficeunsigned *xCoordinate = NULL; /x coordinate of each villageunsigned *center = NULL, *dis = NULL; /point for Center(l,r) & Dis(l,r)info *totalDis = NULL; /point for TotalDis(t,k)/- Function Declarevoid input();void calculateCenter();void calculateDis();void calculateTotalDis();void output(unsigned t, unsigned k);void setFree();int main() input(); calculateCenter(); calculateDis(); calculateTotalDis(); output(0, postoffice); setFree(); return 0;void input() /- Input cin village postoffice; xCoordinate = new unsigned village; for (unsigned i = 0; i xCoordinatei; /- Sort int t = 0; for (i = 0; i village - 1; i+) for (int j = 0; j xCoordinatej+1) t = xCoordinatej; xCoordinatej = xCoordinatej+1; xCoordinatej+1 = t; void calculateCenter() /- 内存分配 center = new unsigned *village; /动态分配二维数组的第一维 for (unsigned i=0; ivillage; i+) /动态分配二维数组的第二维 centeri = new unsignedvillage; /- 初始化Center(l,r) for (unsigned l = 0; l village; l+) for (unsigned r = l; r village; r+) centerlr = xCoordinate(r-l)/2 + l;void calculateDis() /- 内存分配 dis = new unsigned *village; /动态分配二维数组的第一维 for (unsigned i = 0; i village; i+) /动态分配二维数组的第二维 disi = new unsignedvillage; /- 初始化Dis(l,r) for (unsigned l = 0; l village; l+) for (unsigned r = l; r village; r+) dislr = 0; for (unsigned k = l; k xCoordinatek) dislr += centerlr - xCoordinatek; /计算unsigned时不要得出负数 else dislr += xCoordinatek- centerlr; void calculateTotalDis() /- 内存分配 totalDis = new info *village; /动态分配二维数组的第一维 for (unsigned i = 0; i village; i+) /动态分配二维数组的第二维 totalDisi = new infopostoffice+1; /- 计算TotalDis(v,p+1) /- 当k=1时，根据公式(1.2)，直接计算 for (unsigned t = 0; t village; t+) totalDist1.dis = distvillage-1; /- 当k=2,3,.,p时的情况 for (unsigned k = 2; k = postoffice; k+) for (unsigned t = 0; t village; t+) totalDistk.dis = (unsigned)(-1); totalDistk.r = 0; for (unsigned r = t; r = village-k; r+) unsigned temp = distr + totalDisr+1k-1.dis; /- 计算最小值 if (temp totalDistk.dis) totalDistk.dis = temp; totalDistk.r = r; void output(uns