題目

2990:符號(hào)三角形
總時(shí)間限制: 1000ms 內(nèi)存限制: 65536kB
描述
符號(hào)三角形的第1行有n個(gè)由“+”和”-“組成的符號(hào) ，以后每行符號(hào)比上行少1個(gè)，2個(gè)同號(hào)下面是”+“，2個(gè)異號(hào)下面是”-“ 。計(jì)算有多少個(gè)不同的符號(hào)三角形，使其所含”+“ 和”-“ 的個(gè)數(shù)相同。

n=7時(shí)的1個(gè)符號(hào)三角形如下:

輸入
每行1個(gè)正整數(shù)n<=24,n=0退出.
輸出
n和符號(hào)三角形的個(gè)數(shù).
樣例輸入
15
16
19
20
0
樣例輸出
15 1896
16 5160
19 32757
20 59984

理解

字符串由±符號(hào)組成，兩兩異或運(yùn)算（±=-，++=+，–=+）得到少一個(gè)字符的下一行，一直到一行只有一個(gè)字符。
問，最后字符三角形±號(hào)數(shù)量相同的情況有幾種。
1.枚舉
3位時(shí)加的情況有
+++=000=0
+±=001=1
±+=010=2
±-=011=3
-++=100=4
-±=101=5
–+=110=6
—=111=7
就是0到7對(duì)應(yīng)的二進(jìn)制，用異或運(yùn)算得到所有行符號(hào)。
3+2+1=6，是偶數(shù)，有可能有±符號(hào)的數(shù)量相同的字符三角形。
但是5+4+3+2+1=15，奇數(shù)就不可能±號(hào)數(shù)相同。
負(fù)號(hào)或加號(hào)數(shù)等于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<<“長(zhǎng)”<<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;//正號(hào)或負(fù)號(hào)數(shù)
for(int i=n;i>=1&&d;i–){//轉(zhuǎn)換成對(duì)應(yīng)二進(jìn)制
k[1][i]=d%2;//如果是1是就是正號(hào)或符號(hào)
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];//當(dāng)前行的正負(fù)號(hào)
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);//二進(jìn)制幾位全是1時(shí)對(duì)應(yīng)的十進(jìn)制數(shù)
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){//正號(hào)或符號(hào)的數(shù)時(shí)三角形的一半就對(duì)
//view(x,d);
he++;
}
}
cout<<x<<” "<<he<<endl;
}
return 0;
}

遞歸（回溯）

把所有可能數(shù)轉(zhuǎn)換成對(duì)應(yīng)二進(jìn)制有些麻煩?？梢杂眠f歸回溯。
該位置成1，
遞歸調(diào)用，傳遞正號(hào)或負(fù)號(hào)數(shù)，下位在深一層成1，一直到最后一位下一位。
此時(shí)沒有字符可以成1，計(jì)算下幾行，如果正號(hào)或負(fù)號(hào)數(shù)等于n*(n+1)/4(n個(gè)符號(hào))就多個(gè)正負(fù)號(hào)數(shù)一樣字符三角形。
遞歸出口是比字符數(shù)多兩個(gè)。
遞歸后，回到上一層，剛才成1的字符再變回0，就可以湊出所有的二進(jìn)制數(shù)。也達(dá)到了枚舉的效果。只是不用每次將整數(shù)轉(zhuǎn)換成二進(jìn)制，只多一層就能多個(gè)二進(jìn)制。

遞歸（回溯）代碼

#include <bits/stdc++.h>
using namespace std;
int x,he;
bool k[25][25];
void go(int n,int f){//n是從幾位開始，f是正號(hào)或負(fù)號(hào)數(shù)
if(f>x*(x+1)/4)return;//超過一半就作廢，剪枝
if(n**>x+1**)return;//超過x位2個(gè)數(shù)是遞歸出口
for(int i=n;i<=x;i++){//每次遍歷當(dāng)前位到最后一位
k[1][i]=1;//成1
go(i+1,f+k[1][i]);//遞歸下一位，而且改變符號(hào)數(shù)
k[1][i]=0;//恢復(fù)
}
for(int i=2;i<=x;i++)//二行開始計(jì)算剩下的符號(hào)
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位遞歸后，如果正負(fù)號(hào)數(shù)相等
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;
}