符号三角形.cpp

算法分析中

#include<iostream>
using namespace std;
/*
算法设计：
我们用n元组x[1:n]表示符号三角形的第一行的n个符号。当x[i] = 1时，表示符号
三角形的第一行的第i个符号为"+",x[i]=0则表示第i个符号为"-"；1<=i<=n。由于
x[i]是二值的，所以在回溯法解符号三角形问题时，可以用一棵完全二叉树来表示其解空间
。
在符号三角形第一行的前i个符号x[1:i]确定后，就确定了一个由i * ( i + 1 ) /2个符号
组成的符号三角形。下一步确定了x[i+1]的值后，只要在前面已经确定的符号三角形的右边
增加一条边，就可以扩展为x[1:i+1]所相应的符号三角形。最终由x[1:n]所确定的符号三角形
包含的"+"号个数与"-"号个数同为n*(n+1)/4。因此回溯搜索过程中可用当前符号三角形所包含的"+"号个数
与“-"号个数均不超过n*(n+1)/4作为可行性约束，用于剪去不满足约束的树，对于给定的
n,当n*(n+1)/2为奇数时，显然不存在所包含的"+"号个数与"-"号个数相同的符号三角形。
这种情况下可以通过简单的判断加以处理。
*/
class Triangle
{
	friend int Compute(int);
private:
	void Backtrack(int t);
	int n;
	//the number of characters in first line
	int half;
	//n*(n+1)/4
	int count;
	//the number of current '+'
	int **p;
	//the matrix of triangle
	long sum;
	//the number of triangle
};

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];
				//第一行的下标与下面每个下标的关系，也就是第一行有t
				//个，则第j行有t-j+1个字符
				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)
{
	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 )
	{
		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);
	return X.sum;
}
/*
算法效率：
由于计算可行性约束需要O(n)时间，在最坏情况下有O(2^n)个结点需要计算可行性约束
，故解符号三角形问题的回溯算法Backtrack所需的计算时间为O(n*2^n)。
*/
int main()
{
	return 0;
}