随笔-19  评论-1  文章-0  trackbacks-0
        每个符号三角形都是由它的第一行“+,-”号分布决定的,据此可演算出所有分布的三角形,对其进行统计即可。

        同时将一个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 孟起 阅读(485) 评论(0)  编辑 收藏 引用 所属分类: 递推 递归

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理