李道强-6分.txt

这是很不错的计算机算法

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

template<class Type>
void swap(Type &a,Type &b)
{
  Type t=a;
  a=b;
  b=t;
}

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

class RandomNumber
{
  private:
    unsigned long randSeed;
  public:
    RandomNumber(unsigned long s=0);
    unsigned short Random(unsigned long n);
    double fRandom(void);
};

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);
}

class circlenode
{
  friend double Circle_search(int *r, int n);
  private:
    void random_perm(void);
    double center(int t);//计算第t个圆圆心坐标
    double compute(void);//计算排列长度
    int n;//圆的个数
    double *x; //圆心坐标
    int *r; //圆半径为
};

void circlenode::random_perm(void)
{
  static RandomNumber rnd;
	for(int i=n-1;i>0;i--)
		swap(r[i],r[rnd.Random(i)]);
}

double circlenode::center(int t)
{
	double temp=0;
	for (int j=0;j<t;j++)
	{
		double valuex=x[j]+2.0*sqrt(r[t]*r[j]);
		if (valuex>temp) temp=valuex;
	}
	return temp;
};

double circlenode::compute(void)
{
  double low=0,high=0;
  int i;
  for (i = 0; i < n; i++)
    x[i]=center(i);
  for (i = 0; i < n; i++)
  {
    if (x[i] - r[i] < low)
      low = (double)x[i] - r[i];
    if (x[i] + r[i] > high)
      high = (double)x[i] + r[i];
  }
  return (double)high - low;
};

double Circle_search(int *r, int n)
{
  circlenode c;

  c.n=n;
  c.r=r;
  double *x=new double [n];
  c.x=x;

  c.random_perm();

  double min,t;
  bool f;

  min=c.compute();
  do{
    f=false;
    for(int i=0;i<n;i++)
      for(int j=0;j<n;j++)
        if(r[i]!=r[j])
        {
          swap(r[i],r[j]);
          t=c.compute();
          if(t>=min)
            swap(r[i],r[j]);
          else
          {
            f=true;
            min=t;
          }
        }
  }while(f);
  delete[] x;
  return min;
}

void main()
{
  int i,n;
  ifstream fin("input.txt");
  fin>>n;
  int *r=new int [n];
  for(i=0;i<n;i++)fin>>r[i];
  fin.close();


  double len,mlen;

  mlen=Circle_search(r,n);
  for(i=0;i<=n+n+n;i++)//增加计数次数以便得到最小值
  if((len=Circle_search(r,n))<mlen)
    mlen=len;

  ofstream fout("output.txt");
  fout<<mlen<<endl;
  fout.close();

  delete[] r;
}