当前位置 博文首页 > 爱新觉罗?炒饭的博客:符号三角形数量(子集树回溯法)
问题描述
可行性约束条件:
当前符号三角形所包含的“+”和“-”个数均不超过n*(n+1)/4
限界函数(无解的判断)
n*(n+1)/2为奇数
确定x[i+1]的值后,只要在前面确定的符号三角形的右边加一条边就扩展为x[1:i+1]所相应的符号三角形
代码
#include <iostream>
using namespace std;
int n = 0; //第一行符号的个数
int half = 0; //符号总数的一半
int count = 0; //"+"符号的数量
int p[100][100]; //符号三角形矩阵,用1表示+,0表示-
int sum = 0; //符合题意的符号三角形的个数
void Backtrack(int t)
{
if((count>half)||(t*(t-1)/2-count>half)) //当"+"或者"-"数量超过总数的一半时,直接剪去
return;
if(t>n) //到达叶子节点,表示找到一个符合条件的符号三角形,数量加一
{
sum++;
for (int i = 1; i <= n;i++) //打印符合条件的符号三角形
{
int k = 1;
while(k++<i)
cout << " ";
for (int j = 1; j <= n + 1 - i;j++)
{
if(p[i][j]==1)
cout << "+";
else
cout << "-";
}
cout << endl;
}
}
else
{
for (int i = 0; i <= 1;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])?1:0; //注意搞清楚这个是怎么来的
count += p[j][t - j + 1];
}
Backtrack(t + 1);
for (int j = 2; j <= t;j++)
count -= p[j][t - j + 1];
count -= i;
}
}
}
int main()
{
cout << "请输入第一行符号的数量" << endl;
cin >> n;
for (int i = 0; i <= n;i++)
for (int j = 0; j <= n;j++)
p[i][j] = 0;
half = (n + 1) * (n) / 2;
if(half%2==1)
cout << "输入的n有问题,不存在符号条件的符号三角形" << endl;
else
{
half /= 2;
Backtrack(1);
cout << "符号条件的符号三角形有" << sum << "个" << endl;
}
return 0;
}
cs