041221194circle.cpp

随机化算法解圆排列问题

//圆排列问题（随机化算法 ）

#include <fstream.h>
#include <iostream.h>
#include <math.h>
#include <time.h>

//==================构造随机数类RandomNumber===========================

const unsigned long maxshort=65536L;
const unsigned long multiplier=1194211693L;
const unsigned long adder=12345L;

class RandomNumber
{ public:
	RandomNumber(unsigned long s=0);  		//构造函数，缺省值0表示由系统自动产生种子
	unsigned short Random(unsigned long n);  	//产生0：n-1之间的随机整数
	double fRandom(void); 				//产生[0,1)之间的随机实数
  private:
	unsigned long randSeed;				//当前种子	
};

RandomNumber::RandomNumber(unsigned long s)
{
	if(s==0)
		randSeed=time(0);			//用系统时间产生种子
	else 
		randSeed=s;				//由用户提供种子
}

unsigned short RandomNumber::Random(unsigned long n)
{
	randSeed=multiplier*randSeed+adder;
	return(unsigned short)((randSeed>>16)%n);
}

double RandomNumber::fRandom(void)
{
	return Random(maxshort)/double(maxshort);
}

//===================交换函数===========================

void Swap(float& x,float& y)
{
	float temp;
	temp=x;
	x=y;
	y=temp;
}

//===================构造圆排列类===========================

class Circle
{
	friend float CirclePerm(int,float*);	//返回找到的最小圆排列长度
  private:
	void Center(void);		//计算当前所有的圆在当前圆排列中圆心的横坐标
	float Compute(void);		//计算当前圆排列的长度
	void Shuffle(void); 		//随机洗牌算法
	void CircleSearch(void); 	//解圆排列的随机算法
	float min,			//当前最优值
	      result, 			//最优值
	      *x,			//当前圆排列圆心横坐标
	      *r;			//当前圆排列
	int n;				//圆的个数
};

//计算当前所有的圆在当前圆排列中圆心的横坐标
void Circle::Center(void)
{
	for(int i=0;i<n;i++)
		{ float temp=0;
		  for(int j=0;j<i;j++)
			{ float valuex=x[j]+(float)(2.0*sqrt(r[i]*r[j]));
			  if(valuex>temp) temp=valuex;
			}
		x[i]=temp;
		}
}

//计算当前圆排列的长度
float Circle::Compute(void)
{
	float low=0;
	float high=0;
	for(int i=0;i<n;i++)
		{ if(x[i]-r[i]<low) low=x[i]-r[i];	//圆心在最左边的圆未必是左边界，因此函数要进行左边界的更新
		  if(x[i]+r[i]>high) high=x[i]+r[i];	//右边界更新
		}
	return (high-low);
}

//用随机洗牌算法对数组中的元素随机排列，使最坏的情况也能达到平均程度
void Circle::Shuffle(void)
{
	static RandomNumber rnd;
	for(int i=0;i<n;i++)
		{ int j=rnd.Random(n-i)+i;
		  Swap(r[i],r[j]);
		}
}

//解圆排列的随机算法：对生成的随机排列数进行调整，如果交换任意两个圆的位置能使圆排列的长度更短，则对两个圆的位置进行交换
void Circle::CircleSearch(void)
{
	Shuffle();
	Center();
	min=Compute();
	bool found=true;
	while(found)
		{found=false;
		 for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				{ Swap(r[i],r[j]);
				  Center();
				  float length=Compute();
				  if(length<min)
					{ min=length;
					  found=true;
					}
				  else 
					Swap(r[i],r[j]);
				}
		}
}

//返回找到的最小圆排列长度
float CirclePerm(int n,float* a)
{
	Circle X;
	X.n=n;
	X.r=a;
	float *x=new float[n];
	for(int i=0;i<n;i++)
		x[i]=0;
	X.x=x;
	X.CircleSearch();
	X.result=X.min;
	for(i=1;i<=50;i++)
		{X.CircleSearch();
		 if(X.result>X.min) 
			X.result=X.min;
		}
	delete []x;
	return X.result;
}


//===================主程序===========================

int main(void)
{
	int n;
	float result;
	ifstream in("input.txt");
        if(in.fail())
		{	cout<<"the input.txt is not exist!";
			return 0;	}
	in>>n;
	float *a=new float[n];
	for(int i=0;i<n;i++)
            in>>a[i];
	in.close();

	result=CirclePerm(n,a);
	

	ofstream out("output.txt");
	out<<result;
	out.close();

	delete []a;
	return 1;
}