以下代碼思路一樣，第一個處理手段比較容易想到，只在最后一位比較與第一位的大小；第二個空間換時間，第三個在遞歸過程中進行處理篩選。算法解法容易想到，難點在于處理全排列鏡像方面，當然做出來也不難，難的是如何全排列出需要的一半并降低一半的時間復雜度 。主要的思路就是讓第一位小于等于最后一位，這個可以在遞歸中制定規則來篩選，如第三種方法；也可以在開始時就篩選出來，確定第一位和最后一位，那么是需要對2~n-1進行全排列就可以了，時間復雜度自然就下去了。三種方法的不同之處在于對于全排列去除鏡像的處理上。方法二速度較快，但沒有很好的去除重復。方法一去除了鏡像和重復但速度較慢。方法三同時去除了鏡像和重復，速度較方法一快了些。

第一種方法

#include <iostream> #include <math.h> #define LENGTH 10using namespace std;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++){float valuex = x[j] + 2.0 * sqrt(r[t]*r[j]);if(valuex>temp)temp = valuex;}return temp; }void Circle::Compute(void) {float low = 0,high = 0; //low表示左邊第一個圓的最左邊坐標，肯定為負值（因為左邊第一個圓圓心為0），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&&high-low<min){min = high-low; //high-low的值為當前序列圓的總長度 } } /* 全排列去重條件 每一位置的元素，只可以與其之后的相同的元素交換一次。比如之后又兩個2，那么只與第一個2交換。 */ int isSwap(float *r,int start,int end) {for(int i=start;i<end;i++){if(fabs(r[i]-r[end])<1e-6){return 0;}}return 1; }/**遞歸求全排列 * */ void Circle::Backtrack(int t) {if(t>n) {Compute();}else{for(int j = t;j<=n;j++) {if(t==n&&r[1]>r[n]) break;if(isSwap(r,t,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 CirclePerm(int n,float *a) {Circle X;X.n = n;X.r = a;X.min = 999999;float *x = new float[n+1];X.x = x;X.Backtrack(1);delete[] x;return X.min;}int main(void) {Circle circle;float a[LENGTH+1] = {0,1,2,3,4,5,6,7,8,9,10};cout<<"最小值為："<<CirclePerm(LENGTH,a)<<endl;return 0; }

第二種方法

#include <iostream> #include <ctime>#include <iostream> #include <math.h> #include <ctime>#define LENGTH 10using namespace std;class Circle {friend float CirclePerm(int,float *); private:float Center(int t); //計算當前序列中圓心得坐標 void Compute(void); //計算距離 void Backtrack(int t); //遞歸，全排列 void solve();float min, //最優解*x, //記錄院系坐標 *r; //記錄全排列過程中的圓序列（用半徑表示） 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]);if(valuex>temp)temp = valuex;}return temp; }void Circle::Compute(void) {float low = 0,high = 0; //low表示左邊第一個圓的最左邊坐標，肯定為負值（因為左邊第一個圓圓心為0），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&&high-low<min){min = high-low; //high-low的值為當前序列圓的總長度 } } /* 全排列去重條件 每一位置的元素，只可以與其之后的相同的元素交換一次。比如之后又兩個2，那么只與第一個2交換。 */ int isSwap(float *r,int start,int end) {for(int i=start;i<end;i++){if(fabs(r[i]-r[end])<1e-6){return 0;}}return 1; }/**遞歸求全排列 * */ void Circle::Backtrack(int t) {if(t>n-1) {x[n] = Center(n);Compute();}else{for(int j = t;j<n;j++) //只全排列到n-1 {if(isSwap(r,t,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]);}}} }void Circle::solve() {int num[LENGTH*LENGTH][2];int count = 0;for(int i=1;i<=LENGTH;i++){for(int j=1;j<=LENGTH;j++){if(r[i]<=r[j]&&i!=j){num[count][0] = i;num[count++][1] = j;}}}for(int i=0;i<count;i++){int a = num[i][0],b = num[i][1];swap(r[a],r[1]);swap(r[b],r[n]);x[1] = 0;Backtrack(2);} }float CirclePerm(int n,float *a) {Circle X;X.n = n;X.r = a;X.min = 999999;float *x = new float[n+1];X.x = x;X.solve(); // 先把符合條件的第一位和第n位保存在num數組中，然后直接全排列 2~n-1位 delete[] x;return X.min;}int main(void) {clock_t start,end;Circle circle;start = clock();float a[LENGTH+1] = {0,1,2,3,4,5,6,7,8,9,10};cout<<"最小值為："<<CirclePerm(LENGTH,a)<<endl;end = clock();cout<<"time is: "<<end-start<<" ms"<<endl;return 0; }

第三種方法

#include <iostream> #include <ctime> #include <math.h> using namespace std; 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,flag=0; //flag為 1，表示進入2~n-1全排列（不再干擾），為 0表示正在篩選第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]);if(valuex>temp)temp = valuex;}return temp; }void Circle::Compute(void) {float low = 0,high = 0; //low表示左邊第一個圓的最左邊坐標，肯定為負值（因為左邊第一個圓圓心為0），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; //high-low的值為當前序列圓的總長度 } }int isSwap(float* r, int start, int end) {for (int i = start; i < end; i++){if (fabs(r[i]-r[end])<1e-6){return 0;}}return 1; } /* 去除鏡像思路：去除鏡像，保證第一位小于等于第n位。 以下代碼思路：第一位正常與其后元素交換，到第二位時篩選出比第一位大的數，然后交換給n位元素，從而保證首尾達到去除鏡像條件，然后全排列 2~n-1位。去除重復思路：每一位元素只與其后相同數值的元素交換一次 */ void Circle::Backtrack(int t) {if (t > n-1) {x[n] = Center(n);Compute();}else {for (int j = t; j <= n-flag; j++) {if(isSwap(r,t,j)) //去除重復 {if(t==1||flag){//全排列交換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]);}else {if (r[j] >= r[1]) {flag = 1;swap(r[j], r[n]);Backtrack(2); //篩選成功后，進入 2 ~ n-1 位元素的全排列（不再干擾） swap(r[j], r[n]);flag = 0;}}} }} }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;X.flag = 0; X.Backtrack(1);delete[] x;return X.min; }int main() {clock_t start, stop;int n;cout << "輸入圓的個數：";cin >> n;float*a = new float[n + 1];cout << "輸入各個圓的半徑：";for (int i = 1; i <= n; i++) {cin >> a[i];}start = clock();float result = CirclePerm(n, a);stop = clock();cout << "最小排列長度：" << result << endl;cout << "去鏡像后的時間：" << stop - start << "ms" << endl;system("pause");return 0; }

?

總結

以上是生活随笔為你收集整理的圆排列（去除全排列重复、全排列镜像）的全部內容，希望文章能夠幫你解決所遇到的問題。

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