算法设计与分析——回溯法——圆排列问题

「爱情、让人受尽委屈。」 2022-10-15 10:56 214阅读 0赞

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

![在这里插入图片描述][20210524230744447.png]

[20210524230744447.png]: /images/20221014/67d35de668f04a89b9473b380f7a3db3.png