@TOC

题目详情

描述
符号三角形的第1行有n个由“+”和”-“组成的符号 ，以后每行符号比上行少1个，2个同号下面是”+“，2个异号下面是”-“ 。计算有多少个不同的符号三角形，使其所含”+“ 和”-“ 的个数相同。

n=7时的1个符号三角形如下:

• • • • • • +
• • • • • +
• • • • -
• • • -
• • -
• -

+
输入
每行1个正整数n<=24,n=0退出.
输出
n和符号三角形的个数.
样例输入
15
16
19
20
0
样例输出
15 1896
16 5160
19 32757
20 59984

AC代码（放心食用）

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
int n=1,cmd;
int a[404][404];
//0=+,1=-
void pd(){
    int s=0;
    for(int i=0;i<n;i++){
        s+=a[0][i];//首先将第一排单独拿出来算和
    }
    for(int i=1;i<n;i++)//从第二排开始
        for(int j=0;j<n-i;j++)//每次往下都会-1，所以n-i就可以完美处理
        {
            a[i][j]=(a[i-1][j]+a[i-1][j+1])%2; //这里是1+1和0+0都是0，所以只有异号才会为1
            s+=a[i][j];//记录总和
        }    
    if(s==n*(n+1)/2/2) {//（首项+末项）*项数/2，可以看看样例发现+-各一半所以在/2，如果s的值算出来和这个一样，那么这就是个符号三角形
        cmd++;
    }
}
void dfs(int x){
    if(x==n)//x代表第几排，当x等于n的时候，就该判断是不是一个成立的夫哈皮三角形
    {
        pd();
        return;
    }
    for(int i=0;i<2;i++){
        a[0][x]=i;//0代表+，1代表-，所以循环往后判断就好

        dfs(x+1);
    }
}
int main(){
    while(n!=0){
        cmd=0;
        cin>>n;
        if(n==0) break;
        if(n*(n+1)/2%2!=0)
            cout<<n<<" "<<0<<endl;//首先排除不可能的情况
        else{
            dfs(0);
            cout<<n<<" "<<cmd<<endl;
        }
    }
}

@^ _ ^@