郑凌-6分.txt

这是很不错的计算机算法

//圆排列的最小长度算法 040000003 郑凌

#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&,float&);
void shuffle(float *,int);             //随机洗牌算法
void center(float *,float *,int);          //计算当前所有的圆在当前圆排列中圆心的横坐标		
float compute(float *,float *,int);        //计算当前圆排列的长度
float circle_search(float *,float *,int);  //求一次随机排列的最小值
void swap(float& x,float& y)
{
	float temp;
	temp=x;
	x=y;
	y=temp;
}

void shuffle(float *r,int n)	//产生r的一个随机排列
{
	static RandomNumber rnd;
	for(int i=n;i>1;i--) 
	    swap(r[i],r[rnd.Random(i)+1]);
}
void center(float *r,float *x,int n)
{
	for(int i=1;i<=n;i++){
		float temp=0;
		for(int j=1;j<i;j++){
			float valuex=x[j]+(float)(2.0*sqrt(r[i]*r[j]));
			if(valuex>temp) temp=valuex;
		}
		x[i]=temp;
	}
}

float compute(float *r,float *x,int n)
{
	float low=0;
	float high=0;
	for(int i=1;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);
}

float circle_search(float *r,float *x,int n)
{
	float min=9999999, result;
	shuffle(r,n);
	bool found=true;
	while(found)
	{
		found=false;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
			{
				swap(r[i],r[j]);
				center(r,x,n);
				result=compute(r,x,n);
				if(result<min) 
				{
					min=result;
					found=true;
				}
				else swap(r[i],r[j]);
			}
	}
	return min;
}

void main()
{
	int n;
	float *r,*x,result=9999999,min;

	ifstream inf("input.txt"); //打开输入文件input.txt
    if (inf.fail())
	{
  	  cerr << "读入input.txt文件时出错！";
  	  return;
  	}
	inf>>n;
	r=new float[n+1];
	for(int i=1;i<=n;i++) inf>>r[i];
	x=new float[n+1];

	for(i=1;i<=30;i++)
	{
		min=circle_search(r,x,n);
		if(min<result) result=min;
	}
	

	ofstream outf("output.txt"); //创建输出文件output.txt
	if (outf.fail())
	{
  	  cerr << "创建output.txt文件时出错！";
  	  return;
  	}
	outf<<result;
	inf.close();
	outf.close();

	delete[] x;
	delete[] r;
}