符号三角形「终于解决」

大家好，欢迎来到IT知识分享网。

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

Input

每行1个正整数n <=24,n=0退出. 

Output

n和符号三角形的个数. 

Sample Input

15
16
19
20
0

Sample Output

15 1896
16 5160
19 32757
20 59984

这道题应该用深搜去构造顶层，然后推算出其他的层，在推算的同时进行给其中一种符号的计数，最后判断该符号的数是不是总符号数的一半，剩下的一些细节(诸如符号总数是否可以整除2、如何在输入0时结束程序等)我就不解释了，不过代码里的注释中会有。

C++版本一

DFS

#include<iostream>
using namespace std;
int n,total,sum;
int word[30][30];   //存储符号的数组       
void wxy() //函数名没有含义
{
    int x=n,y=0; //x用于枚举层数，y用于计算其它层负号个数
    while(x--) //枚举层数
        for(int i=1;i<=x;i++)
        {
            word[x][i]=(word[x+1][i]+word[x+1][i+1])%2; //定义第n-x+1层的第i个符号
            if(word[x][i]) y++; //若word[x][i]为负号，其它层负号个数加1
        }
    if(sum+y==n*(n+1)/2/2) total++; //若负号的个数为符号总数的一半，情况数加1(运用了等差数列)
}
void dfs(int x)
{
    for(int i=0;i<2;i++) //0为正号，1为负号
    {
        if(i) sum++; //给题目中顶层的负号计数
        word[n][x]=i;   //定义顶层的第x个符号是正还是负
        if(x==n) wxy(); //若顶层的所有符号定义完毕，计算其它层的负号个数
        else dfs(x+1); //定义顶层的第x+1个符号
        if(i) sum--; //回溯
    }
}
main()
{
    while(cin>>n&&n) //输入n，判断n为不为0
    {
        cout<<n<<" ";
        if((n*(n+1)/2)%2) {cout<<"0"<<endl;continue;} //判断符号总数是否可以整除2,(n*(n+1)/2是运用等差数列来算总数的)
        dfs(1);
        cout<<total<<endl;
        total=sum=0;
    }
}

C++版本二

水题

#include <iostream>
#include <stdio.h>
#include <queue>
#include <string.h>
#include <math.h>
using namespace std;
int n;
int a[30][30];

int main()
{
    while(scanf("%d",&n)!=EOF){
        if(n==0)    break;
        //int ans=0;
        cout <<n<<" ";
        switch (n){
                case 3:cout <<"4"<< endl;break;
                case 4:cout <<"6"<< endl;break;
                case 7:cout <<"12"<< endl;break;
                case 8:cout <<"40"<< endl;break;
                case 11:cout <<"171"<< endl;break;
                case 12:cout <<"410"<< endl;break;
                case 15:cout <<"1896"<< endl;break;
                case 16:cout <<"5160"<< endl;break;
                case 19:cout <<"32757"<< endl;break;
                case 20:cout <<"59984"<< endl;break;
                case 23:cout <<"431095"<< endl;break;
                case 24:cout <<"822229"<< endl;break;
                default :cout <<"0"<< endl;break;
                }

    }
    //cout << "Hello world!" << endl;
    return 0;
}

C++版本三

这个应该会OLE

#include <iostream>
#include <stdio.h>
#include <queue>
#include <string.h>
#include <math.h>
using namespace std;
int n;
int a[30][30];

int main()
{
    while(scanf("%d",&n)!=EOF){
        if(n==0)    break;
        int ans=0;
       
        for(int i=0;i<1<<n;i++){
            int cnt1=0,cnt0=0;
            for(int j=0;j<n;j++){
                a[0][j]=i>>j & 1;
                if( a[0][j]==1) cnt1++;
                if( a[0][j]==0) cnt0++;

                //cout << a[0][n-j-1];
            }


            for(int k=1;k<n;k++){
                for(int j=0;j<n-k;j++){
                    if(a[k-1][j]==a[k-1][j+1]){
                        a[k][j]=1;
                        cnt1++;
                    }else{
                        a[k][j]=0;
                        cnt0++;
                    }
                    //cout << a[0][n-j-1];
                }
                //cout<< endl;
            }

//            for(int k=0;k<n;k++){
//                for(int j=0;j<n-k;j++){
//
//                    if( a[k][j]==1) cnt1++;
//                    if( a[k][j]==0) cnt0++;
//                }
//                //cout<< endl;
//            }

            if(cnt0==cnt1) ans++;
            //cout<< endl;
        }
        cout <<n<<" " <<ans<< endl;
    }
    cout << "Hello world!" << endl;
    return 0;
}