符号三角形问题.cpp

回溯算法的一些题目的源代码

// 符号三角形问题

#include <iostream.h>
#include <iomanip.h>

class Triangle
{
	friend int Compute(int);
private:
	void Backtrack(int t);
	int	n,	// 第一行符号的个数
		half,	// n(n+1)/4
		count,	// 当前"+"的个数
		**p;	// 符号三角形矩阵
	long	sum;	// 已找到的符号三角形
};

void Triangle::Backtrack(int t)
{
	if ((count>half)||(t*(t+1)/2-count>half)) return;
	if (t+1>n) sum++;
	else
		for (int i=0; i<=1; i++)
		{
			p[0][t]=i;
			count+=i;
			for (int j=1; j<=t; j++)
			{
				p[j][t-j]=p[j-1][t-j]^p[j-1][t-j+1];
				count+=p[j][t-j];
			}
			Backtrack(t+1);
			for (j=1; j<=t; j++) count-=p[j][t-j];
			count-=i;
		}
}

int Compute(int n)
{
	Triangle X;
	X.n=n;
	X.count=X.sum=0;
	X.half=n*(n+1)/4;
	if (2*X.half%2==1) return 0;
	int **p=new int *[n];
	for (int i=0; i<n; i++) p[i]=new int [n];
	for (i=0; i<n; i++)
		for (int j=0; j<n; j++) p[i][j]=0;
	X.p=p;

	X.Backtrack(0);
	return X.sum;
}

void main()
{
	int n=0;
	while (n<1)
	{
		cout<<"n = ";
		cin>>n;
	}
	cout<<"\nSum = "<<Compute(n);
	cout<<"\n\n";
}