triangle.cpp

算法设计中的经典问题

// Triangle.cpp: implementation of the CTriangle class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "符号三角形，n皇后，圆排列.h"
#include "Triangle.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CTriangle::CTriangle()
{

}

CTriangle::~CTriangle()
{

}


void CTriangle::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( j=2;j<=t;j++)
				count-=p[j][t-j+1];
			count-=i;
		}
}

int Compute(int n)
{
	CTriangle 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=0;i<=n;i++)
		p[i]=new int[n+1];
	
	for( i=0;i<=n;i++)
		for(int j=0;j<=n;j++)
			p[i][j]=0;
		x.p=p;
		x.Backtrack(1);
		delete[]p;
		
		return x.sum;
}