我要招人

去企业版

首页 > 试题广场 >

一个凸N边形，可以用N-3条互不相交的对角线将凸N边形分成N

[单选题]

一个凸N边形，可以用N-3条互不相交的对角线将凸N边形分成N-2个三角形，这称为凸N边形的一种三角剖分。例如N＝5时，共有以下5种三角剖分：

当N＝8时，总共有（）种三角剖分。

```
8
```
```
132
```
```
14
```
```
140
```

查看答案及解析

雨落新生

这是我见过的最让我信服的解释了

https://blog.csdn.net/qq_42995099/article/details/82193505

发表于 2021-03-17 23:59:58 回复(1)

biubiu-425

h(n)=C(2n,n)/(n+1);

发表于 2018-11-12 13:17:43 回复(0)

风景旧曾谙！

可以搜索卡特兰数，也可以点开下边的链接 https://m.baidu.com/from=0/bd_page_type=1/ssid=0/uid=0/pu=usm%402%2Csz%40320_1001%2Cta%40iphone_2_8.1_22_2.11/baiduid=E3F7EC5D643EAC49D9BC2D13C4D7ED1B/w=0_10_/t=iphone/l=3/tc?ref=www_iphone&lid=8528061512878411534&order=3&fm=alop&isAtom=1&is_baidu=0&tj=www_normal_3_0_10_title&vit=osres&m=8&srd=1&cltj=cloud_title&asres=1&title=10343%E5%88%92%E5%88%86%E5%87%B8%E5%A4%9A%E8%BE%B9%E5%BD%A2(%E5%BF%85%E5%81%9A)-%E7%BB%9D%E5%AF%B9%E7%BB%8F%E5%85%B8%E6%AC%BE%E7%A6%8F%E5%85%8B%E6%96%AF-IT...&dict=32&wd=&eqid=7659c2c329cc5000100000035ba9e017&w_qd=IlPT2AEptyoA_yk663Ad5uaxGFrtqnxro5hT_KirrLtpW1dDQxqiU63XorQpofx3vc1C03NYRUebV_I9db76O5LFMnboZL7MY5A6_nYh4oRLdWH0F7EKNgFGo3egGUZ7S5jv_EZhbVaMsfvbHjsuAyv7&tcplug=1&sec=32983&di=f7edca91a2a02d53&bdenc=1&tch=124.332.291.585.1.291&nsrc=IlPT2AEptyoA_yixCFOxXnANedT62v3IIhOPKzVB0XS8iUiefbrgHtkfEFXxLHSVZpPPdj4LsxwGwq&clk_info=%7B%22srcid%22%3A1599%2C%22tplname%22%3A%22www_normal%22%2C%22t%22%3A1537860976363%2C%22xpath%22%3A%22div-article-section-div-div-a-div-div-span2-em3%22%7D&sfOpen=1

发表于 2018-09-25 15:53:18 回复(0)

learner111111

卡特兰数是组合数学中一个常出现在各种计数问题中的数列。
卡特兰数的公式：h(0)=1,h(1)=1,h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)*h(0) (n>=2)即
h(n)=h(n-1)*(4*n-2)/(n+1)即h(n)=C(2n,n)/(n+1);
卡特兰数可以运用的地方有：
1.括号化
矩阵连乘： P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，
试问有几种括号化的方案；
2.出栈次序
一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列；
3.凸多边形三角划分
在一个凸多边形中，通过若干条互不相交的对角线，把这个多边形划分成了若干个三角形。任务是
键盘上输入凸多边形的边数n，求不同划分的方案数f（n）？
一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她
从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？
在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数；
4.给定节点组成二叉搜索树
给定N个节点，能构成多少种不同的二叉搜索树；
5.n对括号正确匹配数目
给定n对括号，求括号正确配对的字符串数。

发表于 2018-10-02 16:34:28 回复(0)

左庶长

Dn+1=（4n-6)/n*Dn

则

D8=(4*7-6)/7 *D7

D7=(4*6-6)/6 *D6

D6=(4*5-6)/5 *D5

因为

D5=5

故

D8=132

发表于 2018-01-16 09:56:00 回复(1)

赞花婆

多边形三角剖分公式

D(n+1)\Dn =(4n-6)\n (Dn表示凸n边形的三角剖分数）

D8=(D8\D7)*(D7\D6)*(D6\D5)=(22\7)*(3)*(14\5)=132

发表于 2017-08-05 10:12:27 回复(2)

愿梦醒

将八边形分割：

1.先分割成两个五边形，有4种分法，已知五边形有5种剖分，种数4*5*5 = 100；

2.先分割成三个四边形，有8种分法，易知四边形有1种剖分，且其中一个四边形分割与上面重复，种数8*2*2*1 = 32；

总数：132。

发表于 2020-02-29 17:14:40 回复(1)

Eden_Zhou

不知道公式的话感觉不会做啊

Dn+1/Dn=（4n-6)/n

n = 4, D4 = 2;

n = 5, D5 = 5; D5 = ((4*4-6)/4)*D4 = 2.5 * 2 = 5;

n = 6, D6 = 14; D6 = ((4*5-6)/5)*D5 = 14;

n = 7, D7 = 42; D7 = ((4*6-6)/6)*D6 = 42;

n = 8, D8 = ; D8 = ((4*7-6)/7)*D7 = 132;

编辑于 2020-07-16 00:35:45 回复(0)

rubbishdog

等于第n-2个卡特兰数。

发表于 2021-09-09 21:18:55 回复(0)

TTT爱吃糖

h(n)=C(2n,n)/(n+1) (n=0,1,2,...)

发表于 2018-10-11 21:06:34 回复(0)

虚拟小菜鸟

个人感觉用公式计算出来，还需要编程吗？这就不是计算机思维了，而是自己推导计算。我本来想用递归去做的，想把8边形转成更小的多边形，可惜失败了。看答案，好多人都是用公式，emm

发表于 2021-10-25 11:54:02 回复(0)

万用勇者鲁卡

卡塔兰数的公式可以百度一下然后观察一下，当有4条边的时候，对应卡塔兰数的第3项即h(3)=2; 当有5条边的时候，对应的是卡塔兰数的第4项，也就是h(4)=5; 如果在自己画一下有6条边的情况，可以发现有14种划分，对应h(5)=4; 可以发现，当有n条边时，结果对应卡塔兰数的第n-1项，所以我们可以通过计算卡塔兰数的第7项来计算出结果。

发表于 2019-03-18 13:06:32 回复(1)

梦境迷离

真没见过....

发表于 2018-01-30 12:47:35 回复(0)

提交观点

问题信息

递归

上传者：赞花婆

难度：

13条回答 573收藏 8589浏览

一个凸N边形，可以用N-3条互不相交的对角线将凸N边形分成N

问题信息

热门推荐

相关试题