openjudge_2.5基本算法之搜索_2990:符号三角形

题目

2990:符号三角形
总时间限制: 1000ms 内存限制: 65536kB
描述
符号三角形的第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

理解

字符串由±符号组成，两两异或运算（±=-，++=+，–=+）得到少一个字符的下一行，一直到一行只有一个字符。
问，最后字符三角形±号数量相同的情况有几种。
1.枚举
3位时加的情况有
+++=000=0
+±=001=1
±+=010=2
±-=011=3
-++=100=4
-±=101=5
–+=110=6
—=111=7
就是0到7对应的二进制，用异或运算得到所有行符号。
3+2+1=6，是偶数，有可能有±符号的数量相同的字符三角形。
但是5+4+3+2+1=15，奇数就不可能±号数相同。
负号或加号数等于3+2+1=6的一半，就是一样。
或者3*(3+1)/4=3也可以。

代码

#include <bits/stdc++.h>
using namespace std;
int x,l,r;
bool k[25][25];
void view(int n,int d){
cout<<d<<“长”<<n<<endl;
for(int i=1;i<=n;i++){
for(int j=1;j<=n-i+1;j++)cout<<k[i][j]<<" “;
cout<<endl;
}
}
int setk(int n,int d){
int he=0;//正号或负号数
for(int i=n;i>=1&&d;i–){//转换成对应二进制
k[1][i]=d%2;//如果是1是就是正号或符号
he+=k[1][i];
d/=2;
}
for(int i=2;i<=n;i++)//第二行开始
for(int j=1;j<=n-i+1;j++){
k[i][j]=k[i-1][j]^k[i-1][j+1];//当前行的正负号
he+=k[i][j];
}
return he;//
}
int main(){
freopen(“data.cpp”,“r”,stdin);
while(cin>>x&&x){
memset(k,0,sizeof(k));
r=0;
for(int i=0;i<x;i++)r+=pow(2,i);//二进制几位全是1时对应的十进制数
int he=0,f;
if((x*(x+1)/2)%2!=1)
for(int d=0;d<=r;d++){
//cout<<d<<endl;
f=setk(x,d);
if(f==x*(x+1)/4){//正号或符号的数时三角形的一半就对
//view(x,d);
he++;
}
}
cout<<x<<” "<<he<<endl;
}
return 0;
}

递归（回溯）

把所有可能数转换成对应二进制有些麻烦。可以用递归回溯。
该位置成1，
递归调用，传递正号或负号数，下位在深一层成1，一直到最后一位下一位。
此时没有字符可以成1，计算下几行，如果正号或负号数等于n*(n+1)/4(n个符号)就多个正负号数一样字符三角形。
递归出口是比字符数多两个。
递归后，回到上一层，刚才成1的字符再变回0，就可以凑出所有的二进制数。也达到了枚举的效果。只是不用每次将整数转换成二进制，只多一层就能多个二进制。

递归（回溯）代码

#include <bits/stdc++.h>
using namespace std;
int x,he;
bool k[25][25];
void go(int n,int f){//n是从几位开始，f是正号或负号数
if(f>x*(x+1)/4)return;//超过一半就作废，剪枝
if(n**>x+1**)return;//超过x位2个数是递归出口
for(int i=n;i<=x;i++){//每次遍历当前位到最后一位
k[1][i]=1;//成1
go(i+1,f+k[1][i]);//递归下一位，而且改变符号数
k[1][i]=0;//恢复
}
for(int i=2;i<=x;i++)//二行开始计算剩下的符号
for(int j=1;j<=x-i+1;j++){
k[i][j]=k[i-1][j]^k[i-1][j+1];
f+=k[i][j];
}
if(f==x*(x+1)/4){//全部n位递归后，如果正负号数相等
he++;
}
}
int main(){
//freopen(“data.cpp”,“r”,stdin);
while(cin>>x&&x){
memset(k,0,sizeof(k));
he=0;
if((x*(x+1)/2)%2!=1)go(1,0);
cout<<x<<" "<<he<<endl;
}
return 0;
}