符號三角形中絮姆，有14個“+“和14個“-”醉冤。2個同號下面是+，兩個異號下面是-篙悯。 在一般情況下蚁阳，符號三角形的第一行有n個符號。符號三角形問題鸽照，要求對于給定的n螺捐，計算有多少個不同的符號三角形，使其所含的“+”和“-”相同矮燎。
如圖：
分析：
第一行安排好兩個后定血，就可以根據(jù)第一行的兩個，判斷第二行的第一個诞外；第一行的第3個安排好后澜沟，可以導(dǎo)出第二行第二個和第三行第一個。峡谊。茫虽。
就是這樣的一個基本思路
注意：
if(cut<=half && ((t+1)*t/2-cut)<=half)原本加到了外層，但是結(jié)果總出現(xiàn)6（n=7時既们，正確結(jié)果為12）濒析，把判斷條件挪到了里面就OK了
因為，判斷條件放外層贤壁，當(dāng)‘+’和‘-’的個數(shù)小于等于half時悼枢，都能進(jìn)入，但不要忘了脾拆，內(nèi)層的操作會增加‘+’和‘-’的個數(shù)馒索。就會存在外層小于half莹妒，內(nèi)層一系列操作后，個數(shù)大于half的情況绰上，而通過題目知道旨怠，這種情況是不應(yīng)該發(fā)生的，所以導(dǎo)致了最終結(jié)果不正確蜈块。
代碼：
#include<stdio.h>
#define n 7 //第一行的n個符號 鉴腻，也代表n行
int half,cut=0; //cut是減號的數(shù)量
int count=0;//方案數(shù)量
int p[n+1][n+1];
void traceback(int t){
if(t>n){ //第一行的n個符號全部安排好了
count++;
return;
}
for(int i=0;i<2;i++){ //0代表加號，1代表減號
p[1][t]=i;
cut+=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]; //無非是對坐標(biāo)出來的
cut+=p[j][t-j+1];
}
if(cut<=half && ((t+1)*t/2-cut)<=half){
traceback(t+1);
}
for(int j=2;j<=t;j++)
cut-=p[j][t-j+1];
cut-=i;
}
}
int main(){
if(((n+1)*n/2)%2==1) //當(dāng)n是5的時候百揭，（5+1）*5/2=15（15是加號和減號的總數(shù)）爽哎。15/2=7.5,
printf("the answer is 0"); //表示7.5個'+'，7.5個'-',顯然不符合要求
half=((n+1)*n/2)/2; //加號器一、減號各half個
traceback(1); //t代表第一行的第幾個符號，因為第一行確定幾個符號祈秕，下面相應(yīng)的確定幾行
printf("%d\n",count);
return 0;
}
運行截圖
