`

10343 划分凸多边形(必做)

 
阅读更多

10343 划分凸多边形(必做)

时间限制:1000MS  内存限制:65535K
提交次数:0 通过次数:0

题型: 编程题   语言: C++;C

Description

问题描述:一个正凸N边形,可以用N-3条互不相交的对角线将正N边形分成N-2个三角形。
现在要求读入N边形的N(N≤20),输出不同划分方法的总数(要求解的是划分方法数,而不需要输出各种划分法)。
这里,注意:
1)顶点可编号,认为顶点皆不相同,因此不允许认为将凸N边形转置视为相同划分。
2)若输出是“No answer”,请注意大小写和无标点。
输入输出举例:
输入: N=3,               输出:1
输入: N=5,		输出:5
输入: N=2,		输出:No answer
输入: N=6,		输出:14
输入: N=8,		输出:132

例如:
当N=5时,共有5种分法。

当N=6时,对六边形的三角形所有划分,请看下图:





输入格式

N,代表正凸N边形。



输出格式

不同划分方法的总数。



输入样例

5



输出样例

5



提示

卡特兰数编辑

本词条缺少信息栏,补充相关内容使词条更完整,还能快速升级,赶紧来编辑吧!
卡特兰数又称卡塔兰数,是组合数学中一个常出现在各种计数问题中出现的数列。由以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)命名。

凸多边形三角划分

在一个凸多边形中,通过若干条互不相交的对角线,把这个多边形划分成了若干个三角形。任务是键盘上输入凸多边形的边数n,求不同划分的方案数f(n)。比如当n=6时,f(6)=14。[6] 
分析
如果纯粹从f(4)=2,f(5)=5,f(6)=14,……,f(n)=n慢慢去归纳,恐怕很难找到问题的递推式,我们必须从一般情况出发去找规律。
因为凸多边形的任意一条边必定属于某一个三角形,所以我们以某一条边为基准,以这条边的两个顶点为起点P1和终点Pn(P即Point),将该凸多边形的顶点依序标记为P1、P2、……、Pn,再在该凸多边形中找任意一个不属于这两个点的顶点Pk(2<=k<=n-1),来构成一个三角形,用这个三角形把一个凸多边形划分成两个凸多边形,其中一个凸多边形,是由P1,P2,……,Pk构成的凸k边形(顶点数即是边数),另一个凸多边形,是由Pk,Pk+1,……,Pn构成的凸n-k+1边形。
此时,我们若把Pk视为确定一点,那么根据乘法原理,f(n)的问题就等价于——凸k多边形的划分方案数乘以凸n-k+1多边形的划分方案数,即选择Pk这个顶点的f(n)=f(k)×f(n-k+1)。而k可以选2到n-1,所以再根据加法原理,将k取不同值的划分方案相加,得到的总方案数为:f(n)=f(2)f(n-2+1)+f(3)f(n-3+1)+……+f(n-1)f(2)。看到此处,再看看卡特兰数的递推式,答案不言而喻,即为f(n)=h(n-2) (n=2,3,4,……)。
最后,令f(2)=1,f(3)=1。
此处f(2)=1和f(3)=1的具体缘由须参考详尽的“卡特兰数”,也许可从凸四边形f(4)=f(2)f(3)+ f(3)f(2)=2×f(2)f(3)倒推,四边形的划分方案不用规律推导都可以知道是2,那么2×f(2)f(3)=2,则f(2)f(3)=1,又f(2)和f(3)若存在的话一定是整数,则f(2)=1,f(3)=1。(因为我没研究过卡特兰数的由来,此处仅作刘抟羽的臆测)。
  • 大小: 15 KB
分享到:
评论

相关推荐

    划分凸多边形(必做)

    一个正凸N边形,可以用N-3条互不相交的对角线将正N边形分成N-2个三角形。 现在要求读入N边形的N(N≤20),输出不同划分方法的总数(要求解的是划分方法数,而不需要输出各种划分法)。

    凸多边形三角划分

    算法的project,凸多边形三角划分。 代码c++编写 ,vc6编译。有mfc的画图,也是vc6. 有详细的文档报告。

    凸多边形的三角划分的C实现

    凸多边形的三角划分是动态规划的一个实例。 ps:输入数据还需要自己另外写过,因为我的代码里面是固定了数据的。代码不多,修改起来还是挺简单的。

    均衡划分凸多边形的代码,pku2839

    均衡划分凸多边形的代码,pku2839 可以在对数时间内解决三角型与多边形相交的面积。

    凸多边形的最优三角划分(java)

    凸多边形的最优三角划分(java)+报告说明

    凸多边形三角动态规划求最小弦长之和

    实现了求凸多边形中三角划分弦长之和最短的问题。其间可以进一步改进。

    polygonPartition:在目标 C 中将凹多边形划分为凸多边形

    多边形分区 在目标 C 中将凹多边形划分为凸多边形

    AcWing 1069 凸多边形的划分

    将这个凸多边形划分成 N−2个互不相交的三角形,对于每个三角形,其三个顶点的权值相乘都可得到一个权值乘积,试求所有三角形的顶点权值乘积之和至少为多少。 输入格式 第一行包含整数 N,表示顶点数量。 第二行包...

    一种简单的凸多边形三角形网格生成

    一种基于delaunay算法的凸多边形三角网格划分的实现

    论文研究-基于二维凸多边形内散乱点的三角划分新算法.pdf

    基于给定的平面散点数据,提出了逐层提取轮廓线,并将轮廓线之间的区域进行三角划分的新算法。实现这一算法的关键是在给定阈值的条件下逐层提取内部离散点的轮廓线,再在所提取的轮廓线间进行等比例三角划分。最后,...

    Opengl网格化绘制多边形

    网格化(tessellation)即把凹多边形,包含洞,岛的多边型,或者自交叉多边型划分为简单凸多边形的过程.

    Open CV 中的平面划分相关函数

    Delaunay三角剖分在工程应用中非常有用,开源库OpenCV也提供了相应的函数,但是由于原始文档不是很详细,在使用过程中仍然会遇到很多麻烦,笔者就自己的理解进行了相关的总结,并解决了实际应用中的相关问题

    论文研究-双重随机样本的结构风险最小化原则.pdf

    提出一种计算平面点集凸壳的快速算法。...再利用极点顺序法判断多边形顶点的凹凸性并删除所出现的凹顶点,最终得到一个凸多边形即为点集的凸壳。整个算法简洁明了,避免了乘法运算(除最坏情况外),从而节省计算时间。

    具有自治表面的深度约束测深映射的自适应路径规划

    为划分凸多边形引入了新算法,以实现有效的覆盖路径规划。 这些算法在模拟和现场使用为该任务建造的小型双体差推力船进行了测试。在本文中,我们开发并实现了一套算法,用于自主查找和跟踪测深轮廓和边界多边形的...

    高分辨率卫星影像与LiDAR数据的自动建筑物提取

    最后,利用二叉空间划分(BSP树)方法,根据数据驱动和模型驱动获取的直线将建筑物区域递归分割为一系列凸多边形,然后合并标识为建筑物的凸多边形,最终得到该建筑物的完整的轮廓描述。与 Ord-nance Survey's ...

    平面点集凸包的最优实时算法

    上海交通大学建筑工程与力学学王志强等的学术论文,在星形多边形性质的基础之上, 根据凸多边形是特殊的星形多边形, 以星点为中心, 以分别 平行于轴和轴的直线作为相对坐标系的坐标轴, 将平面区域划分为四个区, 依据...

    运用C语言实现每一位的卡特兰数计算(源码)

    卡特兰数通常用于描述许多组合结构的数量,如合法的括号序列、二叉树、凸多边形的三角划分等。 卡特兰数的递推公式为: � 0 = 1 , � � + 1 = ∑ � = 0 � � � ⋅ � � − � C 0 ​ =1,C n+1 ​ =∑ i...

    动态规划 屈婉玲 北京大学

    动态规划 屈婉玲 北京大学 最短路径 背包 矩阵链乘积 最长公共子序列 凸多边形最优三角剖分划分 图像压缩 电路布线 流水作业调度 最优二叉搜索树 旅行商 货郎担

    特殊数系列之卡特兰数

    将一个凸多边形区域分成三角形区域(划分线不交叉)的方法数? 类似:在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数? 3.出栈次序问题。一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同...

    全面的动态规划学习资料(内附习题及详细解答)

    凸多边形三角划分(HNOI’97) 6 系统可靠性(HNOI’98) 8 快餐问题(HNOI’99) 9 求函数最大值(CTSC'95) 14 石子合并(NOI’95) 15 游览街区(NOI’97) 17 积木游戏(NOI’97) 20 免费馅饼(NOI’98) 24 棋盘...

Global site tag (gtag.js) - Google Analytics