精华内容
下载资源
问答
  • 输油管道问题分治法)
    千次阅读
    2020-03-01 12:33:36

    某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n口油井的位置,即它们的x 坐标(东西向)和y 坐标(南北向),应如何确定主管道的最优位置,即使各油井到主管道之间的输油管道长度总和最小的位置? 证明可在线性时间内确定主管道的最优位置。
    给定n口油井的位置, 计算各油井到主管道之间的输油管道最小长度总和。
    输入格式: 输入的第1 行是油井数n,1<=n<=10000。接下来n 行是 油井的位置,每行2个用空格割开的整数 x和 y,-10000<=x,y<=10000。
    输出格式: 输出油井到主管道之间的输油管道最小长度总和。
    输入样例:
    5
    1 2
    2 2
    1 3
    3 -2
    3 3

    输出样例: 6

    分析

    设主管道所在的坐标为Y0,则各油井到主管道之间的输油管道长度总和为:
    S=|Y1-Y0|+|Y2-Y0|+ …… …… +|Yn-Y0|
    现在的问题是Y0等于何值时, S的值是最小的?

    结论:Y0取所有Yi的中间值时可以使得S达到最小。

    #include<stdio.h>
    #include<stdlib.h>
    #include<math.h>
    void sort(int a[],int left,int right){
    	int i,j,temp,t;
    	if(left>right){
    		return ;
    	}
    	temp = a[left];
    	i  = left;
    	j = right;
    	while(i!=j){
    		while(a[j]>=temp&&i<j)
    			j--;
    		while(a[i]<=temp&&i<j)
    			i++;
    		if(i<j){
    			t = a[i];
    			a[i] = a[j];
    			a[j] = t;
    		}
    	}
    	a[left] = a[i];
    	a[i] = temp;
    	sort(a,left,i-1);
    	sort(a,i+1,right);
    }
    int main(){
    
    	int *a,n,i,x;
    	scanf("%d",&n);
    	a = (int*)malloc(sizeof(int)*n);
    	for(i=0;i<n;i++){
    		scanf("%d %d",&x,&a[i]);
    	}
    	sort(a,0,n-1);
    	int sum=0;
    	x = a[n/2];
    	for(i=0;i<n;i++){
    		sum+=abs(a[i]-x);
    	}
    	printf("%d",sum);
    	return 0;
    }
    
    更多相关内容
  • 输油管道问题分治策略)

    千次阅读 2020-04-03 12:05:41
    输油管道问题 问题描述: 思路:确定输油主干道的纵坐标,因为是东西走向,用前面用到的选择问题求中位数也就是主干道的纵坐标,然后用到求出最小的总和` 以下是代码 //select代码注释在选择问题中给出了解释 #...

    输油管道问题

    问题描述:
    在这里插入图片描述
    思路:确定输油主干道的纵坐标,因为是东西走向,用前面用到的选择问题求中位数也就是主干道的纵坐标,然后用到在这里插入图片描述求出最小的总和`
    以下是代码

     //select代码注释在选择问题中给出了解释 
     #include <bits/stdc++.h>
     
      int a[50];
      
      int select(int left,int right,int k)
      {
        if( left >= right )    return a[left];
        
        int x = a[left];
        
        int i = left;
        
        int j = right+1;
        
        while( true )
    	{
            do{
                i++;
             }while(a[i]<x);
             
            do{
                 j--;
             }while(a[j]>x);
             
            if( i>=j )   break ;
            std::swap(a[i],a[j]);
         }
         
         if( j-left+1 == k )    return x;
         
         a[left] = a[j];
         
         a[j] = x;
         
         if( j-left+1 < k )
             return select(j+1,right,k-j+left-1);
        else
             return select(left,j-1,k); 
       }
     
     	int  main()
    	{
    		int x;
    		int y;
    		int n;
    		scanf("%d",&n);
    		
    		for(int i=0; i<n; i++)
    		scanf("%d%d",&x,&a[i]);
    		
    		y=select(0,n-1,n/2);  //这里是求中位数
    		 
    		printf("主油管道的的纵坐标为:%d\n",y);
    		 
    	    int min=0;
    	    
    	    for(int i=0; i<n; i++)
    	    {
    	    	min+=(int)fabs(a[i]-y);
    		}
    		printf("各输油管道到主管道的最小距离总和为:%d",min);
    		
    		return 0;
    	}
    	 
    
    

    以下是程序运行结果:
    在这里插入图片描述

    展开全文
  • 输油管道问题-分治法求解

    千次阅读 2019-03-22 22:22:35
    题目要求:某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。 如果给定n口油井的位置,即它们的x坐标(东西向)和y...

    题目要求:某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。
    如果给定n口油井的位置,即它们的x坐标(东西向)和y坐标(南北向),应如何确定主管道的最优位置,即使各油井到主管道之间的输油管道长度总和最小的位置?

    算法设计的思想:

    1.问题实际上可以转化成一维问题,即油井到管道的距离只喝纵坐标有关,故可以将对象抽象到一条y方向的数轴上面。
    2.已知,如果是两个井,则管道穿过二者中间;如果是三个井,则管道穿过最中间的一个点。归纳一下即为,管道的纵坐标应该是所有油井的纵坐标的中位数。
    问题转化为求,n个数的中位数.。

    求中位数的分治思想:

    1.如果这组数是有序的,那么这个数组的中位数就是a[n/2];直接用排序中用到分治法的冒泡排序进行排序,但是这样一方面时间复杂度nlogn较高,一方面我们并不想排序,多做了无用的步骤,算法效率不高.
    2.线性时间复杂度下的选择算法。实际上还是利用快速排序,进行选择。代码如下.

    #include<stdlib.h>//绝对值函数
    #include<stdio.h>
    #define N 10000
    void Swap(int &a,int &b)
    {
    	int t=a;
    	a=b;
    	b=t;
    }
    
    int Partion (int a[],int l,int h)//a数组,l表示下限,h表示上限
    {
    	 int x=a[l];
    	//将小于x的元素交换到左边区域,将大于x的元素交换的右边区域
    	while(l<h)
    	{
    		while(l<h&&a[h]>=x) --h;
    		Swap(a[l],a[h]);
    		while(l<h&&a[l]<=x) ++l;
    		Swap(a[l],a[h]);
    	}
    	a[l]=x;
    	return l;//返回数轴的位置
    }
    
    int Select(int a[],int l,int h,int k)
    {
    	if(l==h) return a[l];
    	int i=Partion(a,l,h);
    	int j=i-l+1; //表示这个数轴是整个数组中第几小的.
    	if(k<=j)//如果比第k小的数要大,则在比它小的数中中在找第k小的
    	   return Select(a,l,i,k);
    	else//如果比第k小的数要大,则只需要在比它大的数中找,第k-j大的
    		return Select(a,i+1,h,k-j);
    	
    }
    int main()
    {
    	int a[N],b[N];
        int n,mid,sum=0;
        scanf("%d",&n);
        for(int i=0; i<n; i++)
            scanf("%d %d",&b[i],&a[i]);
        mid=Select(a,0,n-1,n/2+1);
        printf("mid=%d\n",mid);
        for(int i=0; i<n; i++)
            sum+=abs(a[i]-mid);
        printf("%d",sum);
        return 0;
    }
    
    
    
    

    输入输出样例
    5
    1 2
    2 2
    1 3
    3 -2
    3 3
    输出
    mid=2
    6

    时间复杂度分析

    平均时间复杂度为O(n)在这里插入图片描述

    展开全文
  • 分治策略——输油管道问题

    千次阅读 2020-05-04 18:18:11
    某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。 如果给定n口油井的位置,即它们的x坐标(东西向)和y坐标...

    分治策略

    1.分治策略是对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同。
    2。递归地解这些子问题,然后将各子问题的解合并得到原问题的解。

    分治法的基本步骤

    在这里插入图片描述

    分治策略的算法设计模式

    Divide_and_Conquer(P)
    {
     if (|P|<=n0 ) return adhoc(P);
     divide P into smaller substances P1,P2,…,Pk;
     for (i=1; i<=k; k++) 
      yi=Divide-and-Conquer(Pi)      //递归解决Pi
     Return merge(y1,y2,…,yk)     //合并子问题
    }
    

    根据分治法的分割原则,原问题应该分为多少个子问题才较适宜?各个子问题的规模应该怎样才为适当?这些问题很难予以肯定的回答。
    在用分治法设计算法时,最好使子问题的规模大致相同。如分成大小相等的k个子问题,许多问题可以取k=2。
    这种使子问题规模大致相等的做法是出自一种平衡(Balancing)子问题的思想,它几乎总是比子问题规模不等的做法要好。

    分治法的适用条件

    在这里插入图片描述

    问题描述

    某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。
    如果给定n口油井的位置,即它们的x坐标(东西向)和y坐标(南北向),应如何确定主管道的最优位置,即使各油井到主管道之间的输油管道长度总和最小的位置?
    给定n口油井的位置,编程计算各油井到主管道之间的输油管道最小长度总和。
    在这里插入图片描述

    输入

    第1行是一个整数n,表示油井的数量(1≤n≤10 000)。
    接下来n行是油井的位置,每行两个整数x和y
    (﹣10 000≤x,y≤10 000)。

    输出

    各油井到主管道之间的输油管道最小长度总和。

    输入样例

    5
    1 2
    2 2
    1 3
    3 -2
    3 3

    输出样例

    6

    算法分析

    设n口油井的位置分别为p(i)=(xi,yi),i=1~n。由于主输油管道是东西向的,因此可用其主轴线的y坐标唯一确定其位置。主管道的最优位置y应该满足:
    在这里插入图片描述
    由中位数定理可知,y是中位数。

    代码

    对数组a排序(一般是升序),取中间的元素

    #include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        int n;     //油井的数量
        int x;     //x坐标,读取后丢弃
        int a[1000];    //y坐标
        cin>>n;
        for(int k=0;k<n;k++)
         cin>>x>>a[k];
         sort(a,a+n);    //按升序排序
        //计算各油井到主管道之间的输油管道最小长度总和
        int min=0;
        for(int i=0;i<n;i++)
         min += (int)fabs(a[i]-a[n/2]);
        cout<<min<<endl;
    }

    算法2:采用分治策略求中位数

    #include <iostream>
    #include <cmath>
    #define NUM 1001
    using namespace std;
    int a[NUM];
    int select(int left, int right, int k)
    {
        if (left >= right)
            return a[left];
        int i = left;
        int j = right+1;
        int pivot = a[left];
        while (true)
        {
            do
            {
                i = i+1;
            }
            while (a[i] < pivot);
            do
            {
                j = j-1;
            }
            while (a[j] > pivot);
            if (i >= j)
                break;
            swap(a[i], a[j]);
        }
        if (j-left+1 == k)
            return pivot;
        a[left] = a[j];
        a[j] = pivot;
        if (j-left+1 < k)
            return select(j+1, right, k-j+left-1);
        else
            return select(left, j-1, k);
    }
    int main()
    {
        int n,x,y;
        cin>>n;
        for (int i=0; i<n; i++)
            cin>>x>>a[i];
        y = select(0, n-1, n/2);
        int min=0;
        for(int i=0; i<n; i++)
            min += (int)fabs(a[i]-y);
        cout<<min<<endl;
        return 0;
    }
    展开全文
  • 输油管道问题

    2020-10-13 12:10:14
    问题描述: 根据中位数定理,要使总和距离最小,应该选择中位数作为目标点。因此解决此问题的方法就是将各个油井投影到y轴,找到y坐标的中位数即可。 求解中位数 1、先排序,在求解中位数。 ...
  • 输油管道问题分治算法)

    千次阅读 2017-06-10 15:52:36
    题目描述:某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n 口油井的位置,即它们的x 坐标(东西向)和y...
  • 输油管道问题 分治算法

    千次阅读 2017-05-08 21:47:37
    某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。 如果给定n口油井的位置,即它们的x坐标(东西向)和y坐标...
  • 某石油公司计划建造一条由西向东的主输油管道,该管道要穿过一个有n口油井的油田。从每口油田都要有一条输油管道沿最短路径(或南或北)与主管道相连。如果给定n口油井的位置,即它们的x坐标(东西向)和y坐标(南北...
  • 某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n口油井的位置,即它们的x 坐标(东西向)和y 坐标(南北...
  • 输油管道问题,在VC6.0中实现,算法参考《计算机算法设计与分析》(王晓东)。分治算法RandomizedSelect
  • 如果给定n 口油井的位置,即它们的x 坐标(东西向)和y 坐标(南北向),应如何确定主管道的最优位置, 即使各油井到主管道之间的输油管道长度总和最小的位置?证明可在线性时间内确定主管道的最优位置。 编程任务: ...
  • 输油管道问题-分治

    千次阅读 2016-06-26 12:33:25
    某石油公司计划建造一条由东向西的主输油管道。该管道 要穿过一个有n口油井的油田。从每口油井都要有一条输 油管道沿最短路经(或南或北)与主管道相连。 如果给定n口油井的位置,即它们的x坐标(东西向)和y ...
  • 某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。 如果给定n口油井的位置,即它们的x坐标(东西向)和y坐标...
  • 7-3 输油管道问题 (50 分) 某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n口油井的位置,即它们的x ...
  • 算法设计与分析之输油管道问题

    千次阅读 2019-09-25 08:59:38
    输油管道问题 问题描述 某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。 如果给定n口油井的位置,即它们的x坐标...
  • 输油管道问题(线性时间解决)

    千次阅读 2020-01-12 15:39:56
    输油管道问题 某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有 n口油井的油田。从每口油井都要有一条输油管道沿南北向最短路经与主管道相连。如果给定 n 口油井的地理位置,即它们的 x 坐标...
  • 算法设计与分析: 2-1 输油管道问题

    千次阅读 2018-07-07 09:25:14
    2-1 输油管道问题 问题描述 某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n口油井的位置,即它们的...
  • 7-2 输油管道问题

    2022-04-17 14:49:43
    某石油公司计划建造一条由东向西的主输油管道。该管道要穿过一个有n 口油井的油田。从每口油井都要有一条输油管道沿最短路经(或南或北)与主管道相连。如果给定n口油井的位置,即它们的x 坐标(东西向)和y 坐标(南北...
  • 如果给定n口油井的位置,即它们的x坐标(东西向)和y坐标(南北向),应如何确定主管道的最优位置,即使各油井到主管道之间的输油管道长度总和最小的位置? 如果有两口油井,取两口油井南北方向之间的任意位置 ...

空空如也

空空如也

1 2 3 4 5 ... 8
收藏数 148
精华内容 59
关键字:

输油管道问题分治