答对，我的分全送！问题：凸2n多边形，任意两顶点连一直线段（共n条线），要求任意两条线不相交的连法有多少？ - 编程论坛

#2

hahayezhe2010-09-11 10:54

解法：
一：你已经没分了啊！
二：我不会，但是我还是想要分！

#3

hipwang882010-09-12 21:58

给楼主一点提示，可以考虑三角形法，意思就是每次找两个相邻的边，然后画出一个三角形，然后去掉这个三角形就变成了一个2N-1多边形，如此递归应该可以解决，计算个数的话就在于开始选边的不同了

#4

cppzh2010-09-13 00:09

回复 3楼 hipwang88

线段不相交，根本没有三角形的情况。再说去掉三角形不是少了3个点吗？你题目看懂没？

#5

lintaoyn2010-09-13 07:45

楼主百度下“卡特兰数”我想它能提供你想要的答案
我这两天在看，没看懂
百度里的内容：
凸多边形的三角剖分问题
　　求将一个凸多边形区域分成三角形区域的方法数。　　类似：一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？
　　类似：在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数?
h(n)=((4*n-2)/(n+1))*h(n-1);
该递推关系的解为：
h(n)=C(2n,n)/(n+1) (n=1,2,3,...)
很弱的问下C(2n,n)是什么意思…哪位知道帮忙解释下，我会再开一个贴，给他一百分

#6

cppzh2010-09-14 11:33

回复 5楼 lintaoyn

你的个数的答案是对的。
C(2n,n)表示从2n个数中挑n个数的组合数。
很遗憾，我不能给你分数。因为你要还我50分。
如果你能想出怎么找出所有图形的方法，那么就是我欠你分了。
请问你是在哪里找到这个公式的或者是你自己知道怎么推导吗？

#7

promising2010-09-14 23:51

给3楼顶顶