梁淘-3分.txt

这是很不错的计算机算法

#include <iostream.h>
#include <math.h>
#include <fstream.h>

class triangle
{
	friend int compute(int);//私有变量初始化函数
private:
	void backtrack(int);		
	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>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 j1=2;j1<=t;j1++)
				count-=p[j1][t-j1+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=0;i<=n;i++)
		if (!(p[i]=new int [n+1]))
		{ 
			cout<<"无法提供更多的内存空间"<<endl;
			return 0;
		}
	for (int i1=0;i1<=n;i1++)
		for(int j=0;j<=n;j++) p[i1][j]=0;
	x.p=p;
	x.backtrack(1);		//调用回溯搜索算法
	delete[] *p;
	return x.sum;
}


		
	
void main(void)
{

/*从文件中读出数据*/
	int nn;
	ifstream  fopen("input.txt");
	if (! fopen)
	{
		cout<<"无法打开INPUT.TXT文件"<<'\n';
		return ;
	}
	fopen>>nn;
	fopen.close();
	if (nn<=0||nn>30)
	{
		cout<<"给定数据超出范围0＜n≤30"<<'\n';
		return;
	}

/*调用递归函数*/
	int pn;
	pn=compute(nn);

/*数据写入文件*/
	ofstream outf("output.txt");
	if (! outf)
	{
		cout<<"数据无法写入output.TXT文件"<<'\n';
		return ;
	}
    outf<<pn<<'\n';
	outf.close();
	return ;

}