大家对算法贴那么热,我也发条好了

小熊饼 发布于 2014/07/12 05:50
阅读 426
收藏 2
http://bbs.csdn.net/topics/390828369
加载中
0
小熊饼
我关注那个帖子几天,一直没回复。现在回复的两个是我们坛子的吧,问都什么问题。。。囧
da浪淘沙
da浪淘沙
人家问问题咋了?那些概念没弄清楚咋整?!
0
da浪淘沙
da浪淘沙
P(1)这样算把,1时只能是凸多边形,容易些
1. 顶点只取(-1,1),(1,1),(1,-1),(-1,-1),(0,1),(0,-1),(1,0),(-1,0)的多边形逐个检查一共有C(8,3)-4+C(8,4)+C(8,5)+C(8,6)+C(8,7)+C(8,8)=215个这样的多边形

2. 多每个多边形检查,看原点在不在里面,如果是Counter++,应该可以很快得出P(1)的结果。确是131,图如下


0
da浪淘沙
da浪淘沙
但P(n),n>1会有凹多边形,情况会复杂了。还在思考。。。
0
中山野鬼
中山野鬼

好吧,我承认,这道题目我没心思分析,以至于我心虚的说,题目好渣渣。哈。。。。我还没有想清楚,p(n)与p(n-k)的关系,当然从题目表述中, p(n)应该包含哪些p(n-k)的方案。当然余下的方案不代表任意顶点的x,y的最小绝对值 大于n-k。

至于楼上说的凹多边形,这个判定针对一个方案而言倒也不难,就是无论延那个方向旋转,原点到端点的斜率对于角度应该依次变化。哈


0
oreax
oreax
这图是什么软件画的?
0
da浪淘沙
da浪淘沙

Matlab画的

P(1)太特殊了,这种情形下“极多边形”就是“核”,而且如果顶点选定,只有一种形状

n变大后,1)很多情况下,顶点选定时,可以对应多种不同形状,而且对应的数目目前还没找到规律;2)题目说边不能相交,又要从可能的多边形筛选,目前也没找到规律;3)另外,“核”和多边形不重合,要求核所组成的新多边形

难怪P(2)比P(1)一下子就大了这么多。n变大后,如果像我处理P(1)那种方法,感觉计算量惊人。。。开始感觉这问题复杂了

返回顶部
顶部