Problem C:排列树问题
Time Limit:5000MS Memory Limit:65536KTotal Submit:55 Accepted:3
Description
试设计一个用回溯法搜索排列空间树的函数。该函数的参数包括结点可行性判定函数和上界函数等必要的函数，并将此函数用于解圆排列问题。 圆排列问题描述如下：给定n 个大小不等的圆c1 , c2 ,..., cn ，现要将这n 个圆排进一个矩形框中，且要求各圆与矩形框的底边相切。圆排列问题要求从n 个圆的所有排列中找出有最小长度的圆排列。例如，当n=3，且所给的3 个圆的半径分别为1，1，2 时，这3 个圆的最小长度的圆排列是1,2,1，其最小长度为2 + 4*sqr(2)。 编程任务： 对于给定的n(n≤≡10)个圆，编程计算最小长度排列。
Input
输入由多组测试数据组成。 每组测试数据输入的第一行是1 个正整数n，表示有n个圆。第2行有n个正数，分别表示n个圆的半径。
Output
对应每组输入，输出的每行是计算出的最小长度，保留3 位小数。
Sample Input
3 1 1 2
Sample Output
7.657
[Submit] [Go Back] [Status] [Clarify]
#include < iostream > #include < cmath > #define MAX 13 using namespace std; int nn; class Circle{ private : double mmin, // ?????????? x[MAX], // ???????????????????? r[MAX]; // ?????????? int n; // ?????????????? public : Circle() { mmin = 100000000 ; } void Set(); void Swap( int i, int j); double Center( int t); void Computer(); void Backtrack( int t); double GetMmin();}; void Circle::Set(){ int i; n = nn; for (i = 1 ;i <= n;i ++ ) { scanf( " %lf " , & r[i]); x[i] = 0 ; }} void Circle::Swap( int i, int j){ double temp; temp = r[i]; r[i] = r[j]; r[j] = temp;} double Circle::Center( int t) // ???????????????????????????? { int j; double temp = 0 ,valuex; for (j = 1 ;j < t;j ++ ) { valuex = x[j] + 2.0 * sqrt(r[t] * r[j]); if (valuex > temp) temp = valuex; } return temp;} void Circle::Computer() // ?????????????????? { double low = 0 ,high = 0 ; int i; 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 < mmin) mmin = high - low;} void Circle::Backtrack( int t){ int j; double centerx; if (t > n) Computer(); else { for (j = t;j <= n;j ++ ) { Swap(t,j); centerx = Center(t); if (centerx + r[t] + r[ 1 ] < mmin) { x[t] = centerx; Backtrack(t + 1 ); } Swap(t,j); } }} double Circle::GetMmin(){ return mmin;} /* double Circle::CirclePerm(int n,double *a){ Circle X; X.n=n; X.r=a; X.mmin=1000000000; double *x=new double[n+1]; X.x=x; X.Backtrack(1); delete [] x; return X.mmin;} */ int main(){ while (cin >> nn) { Circle X; X.Set(); X.Backtrack( 1 ); printf( " %0.3lf\n " ,X.GetMmin()); } return 0 ;}
转载于:https://www.cnblogs.com/forever4444/archive/2009/06/04/1495970.html
相关资源：数据结构—成绩单生成器