0102circle.txt

圆排列的概率算法

//圆排列的随机化算法 

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

//==================随机数类===========================

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 input;
	input.open("input.txt");
	input>>n;
	float *a=new float[n];
	for(int i=0;i<n;i++) input>>a[i];
	input.close();

	result=CirclePerm(n,a);
	

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

	delete []a;
	return 0;
}