注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Hao的博客

I'm on my way……

 
 
 

日志

 
 
 
 

Catalan数的应用  

2009-04-08 16:54:52|  分类: Algorithm discov |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Game of Connections

Acceteped : 28   Submit : 86
Time Limit : 1000 MS   Memory Limit : 65536 KB
 

Description

This is a small but ancient game. You are supposed to write down the numbers 1, 2, 3, . . . , 2n - 1, 2n consecutively in clockwise order on the ground to form a circle, and then, to draw some straight line segments to connect them into number pairs. Every number must be connected to exactly one another.
And, no two segments are allowed to intersect.
It's still a simple game, isn't it? But after you've written down the 2n numbers, can you tell me in how many different ways can you connect the numbers into pairs? Life is harder, right?
 

Input

Each line of the input file will be a single positive number n, except the last line, which is a number -1.
You may assume that 1 <= n <= 100.
 

Output

For each n, print in a single line the number of ways to connect the 2n numbers into pairs.Since the number is too large,you should output it mod by 2007.
 

Sample Input

2
3
-1
 

Sample Output

2
5
 

Source

Shanghai 2004 Preliminary

 

题目大意:2n个点围成一个圆,用一些直线将它们两两连接,这样就把圆分成了几个段,每一个点只能被连接到唯一的一个点上,且每一个段都不相交。求对于给定的n有多少种方法将2n个点连接起来。

主要思想:假设n对点有f(n)种方法,则下图情况下分别有f(0)*f(n-1)、f(1)*f(n-2)种方法。

Catalan数的应用 - chhaj5236 - chhaj5236的博客Catalan数的应用 - chhaj5236 - chhaj5236的博客

依次类推,得出f(n)=f(0)*f(n-1)+f(1)*f(n-2)+...+f(n-1)*f(0),其中f(0)=1,f(1)=1。根据这个递推公式,就可以求出结果了。

代码如下:

#include<iostream>
#define MAX 101
using namespace std;
int main(){
    int c[MAX];
    int i,j,n;
    for(i=0;i<MAX;i++)c[i]=0;
    c[0]=c[1]=1;
    for(i=2;i<MAX;i++){         //根据递推公式预先处理c[i]数组
        for(j=0;j<i;j++){
            c[i]=(c[i]+c[j]*c[i-j-1])%2007;
        }
    }
    cin>>n;
    while(n!=-1){
        cout<<c[n]<<endl;
        cin>>n;
    }
    return 0;
}

后记:

1.Catalan数是组合数学中一个常出现在各种计数问题中出现的数列。Catalan数满足以下递推公式:

f(0)=1 and f(n+1)=f(0)*f(n)+f(1)*f(n-1)+...+f(n)*f(0),(n>=0)

2.Catalan数的另一个递推公式:

f(0)=1 and f(n+1)=(2(2n+1)/(n+2))*f(n)

3.Catalan数的非递推公式:

f(n)=(1/(n+1))*C(2n,n)=(2n)!/((n+1)!*n!)

  评论这张
 
阅读(245)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017