输油管道问题算法源程序

输油管道问题，在VC6.0中实现，算法参考《计算机算法设计与分析》（王晓东）。分治算法RandomizedSelect

#include

using std::cout;
using std::endl;
using std::cin;



int Random（int pint r）
{
//	srand（（unsigned）time（0））;
	int a=rand（）%（r-p+1）+p; 
	return a;
}

 void Swap（int &aint &b）
   { int m;
     m=a;
     a=b;
     b=m;  
   }

int Partition（int a[]int pint r）
{
	int i=pj=r+1;
	int x=a[p];
	while（true）
	{
	 while （a[++i]	 while （a[--j]>x）;
	 if （i>=j） break;
	 Swap（a[i]a[j]）;
	}
     a[p]=a[j];
	 a[j]=x;
	 return j;

}

int RandomizedPartition（int a[]int pint r）
{
   int i=Random（pr）;
   Swap（a[i]a[p]）;
   return Partition（apr）;

}

int RandomizedSelect（int a[]int pint rint k）
{ int j;
  if（p>=r） return a[p];
   int  i=RandomizedPartition（apr）;
      j=i-p+1;
  if（k==j） return a[i];
  if（k  else return RandomizedSelect（ai+1rk-j）;
}


int r=0;
int main（）{

	printf（“请输入油井的个数:“）;
	cin>>r;
	int *x=new int[r];
	int *y=new int[r];
	for（int i=0;i	{
		printf（“请输入第%d个管道的坐标:“i+1）; 
		cin>>x[i];
		cin>>y[i];
	}
	int p=0b=0c=0;
	int k=（r+1）/2;
    
	b=RandomizedSelect（ypr-1k）;
	
	for（int j=0;j		c+=abs（b-y[j]）;
    cout<	return 0;
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     目录          0  2012-05-22 17:15  shuyou\Debug

     文件       1253  2012-05-22 12:57  shuyou\shuyou.cpp

     文件       4284  2012-05-22 09:06  shuyou\shuyou.dsp

     文件        520  2012-05-22 08:53  shuyou\shuyou.dsw

     文件      41984  2012-05-22 17:14  shuyou\shuyou.ncb

     文件      48640  2012-05-22 17:14  shuyou\shuyou.opt

     文件       1276  2012-05-22 17:13  shuyou\shuyou.plg

     目录          0  2012-05-22 17:14  shuyou

----------- ---------  ---------- -----  ----

                97957                    8