#include<iostream>#include<math.h> using namespace std;class Circle{public:float Center(int t);void Compute(void );void BackTrack(int t);float min; //当前最优值 float *x;//当前圆排列圆心横坐标 float *r;//当前圆排列 float *result; //记录最终 的圆半径排序 int n;//待排列圆的个数 };float Circle::Center(int t)//计算当前所选圆的圆心横坐标 {float temp = 0;//记录临时的圆心的横坐标for(int j=1;j<t;j++){float valuex = x[j]+2.0*sqrt(r[t]*r[j]);//算一下前面所有的圆心到目前第T个圆的圆心的距离 //因为可能这里有陷阱 if(valuex > temp)temp = valuex; } return temp;} void Circle::Compute(void)//计算当前圆排列的长度 {float low = 0,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];}if(high-low<min)min = high - low;} void Circle::BackTrack(int t){if(t>n){Compute();}else{for(int j=t;j<=n;j++){swap(r[t],r[j]);float centerx = Center(t);if(centerx+r[t]+r[1]<min){result[j]=r[t];x[t] = centerx;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;float *x =new float [n+1];X.x= x;float *result = new float [n+1]; X.result= result;X.BackTrack(1);cout<<"输出圆排列后圆半径的序列：";for(int i=1;i<=n;i++){cout<<X.result[i]<<" ";}cout<<endl;delete[] x;return X.min;}int main(){int n;cout<<"输入圆的个数:";cin>>n; cout<<"输入圆半径序列：";float a[n+1];for(int i=1;i<=n;i++){cin>>a[i];}cout<<CirclePerm(n,a);}
如果觉得《算法设计与分析——回溯法——圆排列问题》对你有帮助，请点赞、收藏，并留下你的观点哦！
