041321233circle.cpp

回溯法搜索排列树算法园排列问题,算法设计与分析课程

#include <iostream.h>
#include <fstream.h>
#include <stdio.h>
#include<math.h>
#include<iomanip.h>

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

class Circle{
	friend float CirclePerm(int,float *);
private:
	float Center(int t);
	void Compute(void);
	void Backtrack(int t);
	float min, //当前最优值
		  * x,//当前圆排列圆心横坐标
		  * r;//当前圆排列
	int n;//待排列圆的个数
};

float Circle::Center(int t)
{//计算当前所选择圆的圆心横坐标
	float temp = 0;
	for (int 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(void)
{//计算当前圆排列的长度
	float low = 0, high = 0;//low表示圆排列的最左端坐标 high表示圆排列的最右端坐标
	//此时的坐标是相对第一个圆的圆心建立的
    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];//计算最右端
	}
   if (high-low<min) min=high-low;//右-左即为排列长度
}

void Circle::Backtrack(int t)
{
	if (t>n) Compute();//完成所有圆，计算排列长度
	else
		for (int 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 CirclePerm(int n,float *a)
{//返回找到的最小圆排列长度
	Circle X;
	X.n=n;
	X.r=a;
	X.min=100000;//设置min初始值
	float *x=new float[n+1];//分配x数组
	X.x=x;
	X.Backtrack(1);
	delete [] x;
	return X.min;
}

void main()
{
	int n;
	ifstream fin("input.txt",ios::nocreate);
	fin>>n;
	float *a= new float[n];
	for(int i=1;i<=n;i++) fin>>a[i];
	fin.close();
	ofstream fout("output.txt");
	fout<<setiosflags(ios::fixed)<<setprecision(5)<<CirclePerm(n,a)<<endl;
	fout.close();
}