一个计数问题

medie2005 · 发表于 2008-5-12 14:48:30

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

原题链接:http://topic.csdn.net/u/20080510/12/e30fe78d-9503-495f-a24f-c85644a8346f.html
把一个多边形分成三角形和四边形的个数是多少，具体有啥公式啊？当然那些分割线不能相交，比如对于
3
4
5
6
7
8
9
10
对应的方法为：
1
3
10
38
154
654
2871
12925

zgg___ · 发表于 2008-5-12 16:38:55

http://www.research.att.com/~njas/sequences/A001002

medie2005 · 发表于 2008-5-12 16:57:56

呵呵,有点出乎意料.
我没有找出递归关系,所以怀疑公式的存在性.没想到zgg__找到了资料了.

mathe · 发表于 2008-5-12 17:02:48

假设n边形划分数为f(n),而且为方便起见，记f(2)=1
考虑一个指定的边（图最左边的边），这条边为一个三角形的边的情况如图:

这条边属于一个四边形的情况有如下几种

(其中上面这个图还有一个对称情况）

于是我们可以得到递推公式
$f(n)=sum_{i=2}^{n-1}f(i)f(n+1-i) + 2sum_{i=3}^{n-3}f(i)f(n-i)+sum_{i=2}^{n-2}f(i)f(n-i)+sum_{ {: (i+j+k=n+2),(i>=3),(j>=3),(k>=3) :} } f(i)f(j)f(k)$

medie2005 · 发表于 2008-5-12 17:45:26

呵呵,mathe原来一直在潜水啊.
明白了.这个递归式好象不好求.

medie2005 · 发表于 2008-5-12 17:47:08

我的意思是递归式不好解.

无心人 · 发表于 2008-5-12 18:30:39

觉得就是稍微复杂点
应该好解

无心人 · 发表于 2008-5-12 18:32:24

用函数式语言描述这个公式应该容易些

medie2005 · 发表于 2008-5-12 18:49:35

哦,无心人说说解法啊.

无心人 · 发表于 2008-5-12 19:54:56

我在学呢
还没学好呢
什么时候学会写了
我会写在我专门学习的haskell帖子里

账号		自动登录	找回密码
密码			欢迎注册

[求助] 一个计数问题

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

评分