circle-精度未设.cpp

给定n个大小不等的圆c , c , , cn 1 2 &#61516

/*圆排列问题求解程序*/
/*本程序运行前提：
  在源程序目录下存在input.txt文件，并且该文件已经按一定格式存储若干值
/*本程序在tc++3.0和vc++6.0上运行通过*/
#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 ouputtofile();//输出函数 
    ~circle();//析构函数 
};


void swap(float& a,float& b);//交换函数 


/*构造函数的定义*/ 
circle::circle()
{
  int i;//循环控制变量 
  ifstream fin("input.txt",ios::nocreate);//打开输入文件
  if(!fin) //如果文件不存在 
  {
    cerr<<"文件不存在";
    exit(-1);
  } 
  fin>>n;//读入圆个数 
  if(!(x=new float[n+1]))//分配x数组 
  {
    cerr<<"insufficient memory!"<<endl;//分配不成功，退出
    exit(-1);
  }
  if(!(r=new float[n+1]))//分配r数组 
  {
    cerr<<"insufficient memory!"<<endl;//分配不成功，退出
    exit(-1);
  }
  for(i=1;i<=n;i++) fin>>r[i];//读入各圆半径 
  min=100000;//设置min初始值 
  fin.close();//关闭输入文件
}
  

/*递归函数的定义*/ 
void circle::backtrack(int t)
{
  int j;//循环控制变量 
  if(t>n) compute();//所有圆已考虑，计算排列长度 
  else
    for(j=t;j<=n;j++)//考虑各种排列 
    {
      if(j!=t&&r[t]==r[j]) continue;//相同情况不在继续考虑 
      swap(r[t],r[j]);//考虑下一种排列情况 
      float centerx=center(t);//求得第t个圆的圆心相对第1个圆的圆心的横坐标 
      if(centerx+r[t]+r[1]<min)//判断此时排列长度是否已超过当前解，未超过继续递归 
      {
        x[t]=centerx;//修改圆t的圆心坐标 
        backtrack(t+1);//递归 
      }
      swap(r[t],r[j]);//还原排列情况 
    }
}


/*求圆心横坐标函数*/
float circle::center(int t)
{
  int j;//循环控制变量 
  float temp=0;
  for(j=1;j<t;j++)//考虑和1到t-1各个圆相切的情况 
  {
    float valuex=x[j]+2.0*sqrt(r[t]*r[j]);//求得各情况下的圆心坐标 
    if(valuex>temp) temp=valuex;//取较大值 
  }
  return temp;//返回圆t的圆心横坐标 
}


/*求圆排列的长度函数的定义*/
void circle::compute()
{
  int i;
  float low=0,high=0; //low表示圆排列的最左端坐标 
                     //high表示圆排列的最右端坐标
                     //此时的坐标是相对第一个圆的圆心而言的 
  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::ouputtofile()
{
  ofstream out("output.txt");//创建输出文件
  out<<min<<endl;//输出最优排列长度 
  out.close();//关闭输出文件 
}

/*析构函数的定义*/ 
circle::~circle()
{
  delete[] x;//释放x所占内存 
  delete[] r;//释放bestx所占内存 
}

/*主程序部分*/ 
int main()
{
  circle cir;//创建类clique的实例 
  cir.backtrack(1);//调用递归函数计算最优排列的长度 
  cir.ouputtofile();//输出解信息 
  return 0;
}

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