三角形.c

算法分析ACM题目：符号三角形问题算法 保证能运行！算法分析课程必备！

#include "stdio.h"
#include "malloc.h"
int cnt;
int hf;
int n;
int sum;
int **p;
int a[100];
int total;

void backtrack(int t)
{    
	int i,j;
	if((cnt>hf)||(t*(t-1)/2-cnt>hf))
		return;
	if(t>n) 
		sum++;
	else
		for(i=0;i<2;i++)
		{
			p[1][t]=i;
			cnt+=i;
			for(j=2;j<=t;j++)
			{
				p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2];
				cnt+=p[j][t-j+1];
			}
            backtrack(t+1);
			for(j=2;j<=t;j++)
				cnt-=p[j][t-j+1];
			cnt-=i;
		}
}

int main()
{
	int i,j,k=0;
	scanf("%d",&n);
	while(n!=0)
	{
        cnt=0;
		total=n*(n+1)/2;
		sum=0;
		hf=total/2;
		p=(int **)malloc(sizeof(int *)*(n+1));
		for(i=0;i<=n;i++)
			p[i]=(int *)malloc(sizeof(int)*(n+1));
        for(i=0;i<=n;i++)
			for(j=0;j<=n;j++)
				p[i][j]=0;
			if(total%2==0)
			{
				backtrack(1);
			    a[k]=sum;
			}
			else a[k]=sum;
			k++;
            scanf("%d",&n);
	}
	for(i=0;i<k;i++)
	    printf("%d\n",a[i]);
	return 0;
}