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

總結

以上是生活随笔為你收集整理的算法设计与分析——回溯法——圆排列问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。