算法设计与分析——回溯法——符号三角形问题

淡淡的烟草味﹌ 2022-10-20 12:16 223阅读 0赞

#include<iostream>
    using namespace std;
    
    class Triangle{
        
    	public:
    		void Backtrack(int t);
    		
    		int n;//第一行的符号个数 
    		int half;//n*(n+1)/4 
    		int count;//当前—的个数 
    		int **p;//符号三角形矩阵 
    		long sum; //已找到的符号三角形数 
    };
    
    
    void Triangle::Backtrack(int t)
    {
        
    	if((count>half)||(t*(t-1)/2-count>half))
    		return ;
    	if(t>n)
    		sum++;
    	else
    	{
        
    		for(int i=0;i<2;i++)
    		{
        
    			p[1][t] = i;
    			count +=i;
    			for(int j=2;j<=t;j++)
    			{
        
    			p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2];
    			count+=p[j][t-j+1];
    			}
    		Backtrack(t+1);
    		for(int j=2;j<=t;j++)
    			{
        
    			count-=p[j][t-j+1];	
    			}
    		count-=i;
    		}
    		
    	}
    	
    	
      }  
      
    int Compute(int n)
    {
        
    	Triangle X;
    	X.n=n;
    	X.count=0;
    	X.sum=0;
    	X.half=n*(n+1)/2;
    	if(X.half%2 == 1)
    		return 0;
    	X.half=X.half/2;
    	int **p = new int *[n+1];
    	for(int i=1;i<=n;i++)
    	{
        
    		p[i] = new int [n+1];
    	}
    	for(int i=0;i<=n;i++)
    	{
        
    		for(int j=0;j<=n;j++)
    		{
        
    			p[i][j]=0;
    		}
    	}
    	
    	X.p=p;
    	X.Backtrack(1);
    	return X.sum; 
    }
    int main()
    {
        
    	int n;
    	cout<<"输入第一行符号的个数：";
    	cin>>n;
    	cout<<"当符号的个数为"<<n<<"共有"<<Compute(n)<<"符号三角形"<<endl;
     }

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

[20210517231800934.png]: /images/20221020/96e06a02a9b546249d5df06a5e83c47c.png