The Fourth Dimension Space

枯叶北风寒，忽然年以残，念往昔，语默心酸。二十光阴无一物，韶光贱，寐难安； 不畏形影单，道途阻且慢，哪曲折，如渡飞湍。斩浪劈波酬壮志，同把酒，共言欢！ -如梦令

POJ 1095 卡特兰数+dfs

感觉和上次codeforce的第四题有点像，虽然没做出来，呵呵。
看来枚举左右子树这一招还是蛮常用的。其实我本来想练下卡特兰数的，结果变成练DFS了。
注意递归求解左右孩子时的那两个参数，一定要先加上1，否则就不对了。

#include<stdio.h>
long long a[20];  
long long b[20]; 
//定理：n个结点能形成的二叉树总数为 卡特兰数 C(2n,n)/(n+1) 或者由递推公式Ci+1=2*(2*i+1)/(i+2)*Ci 
//设计figure(n)，n代表这棵树整体的偏移量
//分别算出其左右子树各自的偏移量，递归求解即可
//由于先递归左儿子，输出顺序与题意相符
void figure(int n) 
{       
    int t,i,j;  
    if(n==1){printf("X");return;}     
    j=0;
    while(true) if(b[++j]>=n) break;         
    n=n-b[j-1];//j代表有几个结点，n此时代表在这些结点下的序号    
    for(i=0;i<j;i++)   
    {          
        t=a[i]*a[j-1-i];    
        if(t>=n)  break;           
        else n=n-t;   
    }     
    if(i!=0)    //i是此时左子树挂的节点数
    {        
        printf("(");  
        figure(b[i-1]+1+(n-1)/a[j-1-i]);//初始的时刻，只需要增加1，左子树的偏移量就增加1，而之后的部分，需要右子树变换a[j-i-1]次，左子树的偏移量才增加1  
        printf(")");
    }    
    printf("X");  
    if(i!=j-1)    
    {        
        printf("(");  
        figure(b[j-2-i]+1+(n-1)%a[j-1-i]);   
        printf(")");   
    }   
}        
int main()  
{      
    int n;   
    int i,j;     
    a[0]=1;     
    a[1]=1;       
    b[1]=1;     
    b[0]=0;     
    for(i=2;i<20;i++) 
    {        
        a[i]=2*(2*(i-1)+1)*a[i-1]/(i+1) ;//卡特兰数递推公式
        b[i]=b[i-1]+a[i];   
    }    
    while(scanf("%d",&n)&&n)   
    {      
        solve(n);   
        printf("\n");   
    }       
    return 0;  
}  

posted on 2010-04-13 17:33 abilitytao 阅读(2132) 评论(5)  编辑 收藏 引用

评论

# re: POJ 1095 卡特兰数+dfs 2010-04-13 19:37 abilitytao

srand(time(NULL))
是以当前到1970年的时间间隔的秒数为种子，time(NULL),指不需要保存一个时间对象
通常情况下可以Time tTime;然后time(&tTime)来将这个时间获取到。

而rand()是以刚才生成的种子为基础来产生一个随机数，每调用一次产生一个数，貌似如果期间没有再次调用srand来生成种子，rand()是接着前面的序列来产生下一个数。（个人想法）
因为：
srand(time(NULL))；
int x = rand();
int y = rand();
x和y的值不一样。而：
srand(time(NULL));
int x = rand();
srand(time(NULL));
int y = rand();
则是相同，因为后一种使用了同一个种子（运行期间时间很短，返回的秒数相同）  回复  更多评论   

# re: POJ 1095 卡特兰数+dfs[未登录] 2010-04-16 09:49 yoyo

I can understand a[i] stores catalan number when there are i nodes.
but what is b[] used for?

Thanks,
yoyo  回复  更多评论   

# re: POJ 1095 卡特兰数+dfs[未登录] 2010-04-16 10:59 abilitytao

@yoyo
b[i]=a[1]+a[2]+...a[i];  回复  更多评论   

# re: POJ 1095 卡特兰数+dfs[未登录] 2010-04-16 11:19 yoyo

@abilitytao
:-) I can know it from code, while no idea what's the purpose of b[i] = a[1]+...a[i]

Thanks for quick replying.

yoyo  回复  更多评论   

# re: POJ 1095 卡特兰数+dfs 2010-04-16 17:50 abilitytao

@yoyo
the intention is to find the node number of the the tree that you want.
you are not chinese? or you can understand it through my notes by Chinese.  回复  更多评论   


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