林政-3.5分.txt

这是很不错的计算机算法

#include<fstream.h>
#include<stdlib.h>
#include<iomanip.h>
#include<math.h>

class circle
{
  private:
    float min;	//当前最优值 
    float *x;	//当前圆排列圆心横坐标 
    float *r;	//当前圆排列 
    int n;	//圆个数 
  public:
    circle();
    float center(int t);
    void compute();
    void backtrack(int t);
    void outfile();
};


void swap(float& a,float& b);

circle::circle()
{
  int i;
  ifstream infile("input.txt",ios::nocreate);
  if(!infile)
  {
    cerr<<"读取文件错误";
    exit(-1);
  } 
  infile>>n;
  x=new float[n+1];
  r=new float[n+1];
  for(i=1;i<=n;i++) infile>>r[i];
  min=100000;
  infile.close();
}

void circle::backtrack(int t)
{
  int j;
  if(t>n) compute();
  else
    for(j=t;j<=n;j++)
    {
      swap(r[t],r[j]);
      float centerx=center(t);
      if(centerx+r[t]+r[1]<min)	    //下界约束
      {
        x[t]=centerx;
        backtrack(t+1);
      }
      swap(r[t],r[j]);
    }
}


//当前选择圆的圆心横坐标
float circle::center(int t)
{
  int j;
  float temp=0;
  for(j=1;j<t;j++)
  {
    float valuex=x[j]+2.0*sqrt(r[t]*r[j]);
    if(valuex>temp) temp=valuex;
  }
  return temp;
}

void circle::compute()
{
  int i;
  float low=0,high=0;
  for(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];
  }
  if(high-low<min) min=high-low;
}

void circle::outfile()
{
  ofstream out("output.txt");//创建输出文件
  out<<min<<endl;//输出最优排列长度 
  out.close();//关闭输出文件 
}

int main()
{
  circle yuan;
  yuan.backtrack(1);
  yuan.outfile();
  return 0;
}

//交换函数 
void swap(float& a,float& b)
{
  float temp;
  temp=a;
  a=b;
  b=temp;
}