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

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