每個符號三角形都是由它的第一行“+,-”號分布決定的，據此可演算出所有分布的三角形，對其進行統計即可。
同時將一個n行三角形T的+，-號個數分別記為pos_num(n),neg_num(n)，其第一行中的+，-號個數記為x(n),y(n)，則可得到下式：
pos_num(n)=x(n)+pos_num(n-1)
neg_num(n)=y(n)+neg_num(n-1)
由此，我們可以從n=1開始，利用前面n=k-1的結果，迭代求出n=k的分布情形，然后對n=k的所有分布統計。
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
struct record
{
int pos,neg;
record(int a,int b){
pos=a; neg=b;
}
};
int main()
{
int n,i,j,k,sum;vector<record> v;
for(int m=1;m<=24;m++)
{
n=m;
if((n*(n+1))%4!=0){
cout<<n<<" 0"<<endl;
continue;
}
vector<record> v;
record r1(0,1);//n=1的情況
v.push_back(r1);
record r2(1,0);
v.push_back(r2);
for(i=2;i<=n;i++)//計算到n的所有情況
{
int * trip=new int[i];
int sum_i=(int)pow(2.0,i*1.0);
for(j=0;j<sum_i;j++)//第j種分布
{
int temp1=j, temp2=i;
int x=0, y=0; //記錄+，-的個數
while(temp1)
{
if(temp1%2==0){
trip[--temp2]=0; y++;
}
else {
trip[--temp2]=1; x++;
}
temp1/=2;
}
for(k=0;k<temp2;k++)
y++, trip[k]=0;
int idx=0;
for(k=0;k<i-1;k++)
{
if(trip[k]+trip[k+1]==1)
idx*=2;
else idx*=2,idx+=1;
}
x+=v[2*((int)pow(2.0,i-2.0)-1)+idx].pos;
y+=v[2*((int)pow(2.0,i-2.0)-1)+idx].neg;
record r(x,y);
v.push_back(r);
}
}
/**//*if(n==3){
int star=2*((int)pow(2.0,n-1.0)-1);
for(j=0;j<(int)pow(2.0,n*1.0);j++)
printf("---%d %d\n",v[star+j].pos,v[star+j].neg);
}*/
int base=2*((int)pow(2.0,n-1.0)-1);
int num=(int)pow(2.0,n*1.0);
sum=0;
for(i=0;i<num;i++){
if(v[base+i].pos==v[base+i].neg)
sum++;
}
cout<<n<<" "<<sum<<endl;
}
return 0;
}題中，n<=24，時間空間均有限制，我們可以先求出所有結果，然后保存到數組直接取來輸出。這是ACM題中很常見的情況。
1 #include<stdio.h>
2 int res[25]={0,0,0,4,6,0,0,12,40,0,0,171,410,
3 0,0,1896,5160,0,0,32757,59984,0,0,431095,822229};
4 int main()
5 {
6 int n;
7 while(scanf("%d",&n),n)
8 {
9 printf("%d %d\n",n,res[n]);
10 }
11 return 0;
12 }
posted on 2010-10-11 09:13
孟起 閱讀(537)
評論(0) 編輯 收藏 引用 所屬分類:
遞推 遞歸