魔方吧·中文魔方俱乐部 › 论坛 › 『其它智力游戏』 › ★ 数学、算术趣题 (Math Puzzles) › n点连线问题

查看: 1033|回复: 4

n点连线问题 [复制链接]

骰迷

红魔

All Blue

Rank: 4

积分: 1196
帖子: 999
精华: 2
UID: 38845
性别: 男

电梯直达

1^#

发表于 2011-7-20 21:26:28 |只看该作者 |倒序浏览

若平面上有n点,最多能连多少条互不相交的线段?
什么连线方案最优?

比如一点是0条线,两点1条,三点3条,四点6条,五点就好像只能连9条之类的

收藏0

公式D F2 U L2 U B2 U R2 U R' F2 R L U L' R' U R L' U L U L U2 L' U' L U2 L'
数列11121131221231321332223233311

使用道具举报

superacid

银魔

Rank: 7 Rank: 7 Rank: 7

积分: 2520
帖子: 3072
精华: 7
UID: 62890
性别: 男

2^#

发表于 2011-7-20 21:58:41 |只看该作者

题目应该是问这n个点成如何状态的时候连线能最多吧
只要这n个点的凸包是三角形且任意3点不共线就可以了，能连3n-6条线(n≥3)

突然想起来。。。这就是著名的e≤3n-6

想法是根据V+F-E=1，然后用三角形内角和来考虑F的最大值

19events = 644days
PB (2 3 4 5)B = 1200seconds
北大魔方爱好者QQ群74893945
mf8最少步讨论群：RP与公式的绝佳配合QQ群5652935

使用道具举报

42752277

透魔

阿V

Rank: 6 Rank: 6

积分: 7732
帖子: 6459
精华: 2
UID: 1253084
WCA ID: 2010ZHAN17

3^#

发表于 2011-7-20 23:10:02 |只看该作者

没有太听懂

.

静坐常思己过，闲谈莫论人非

使用道具举报

konami赚了钱

黄魔

Rank: 3 Rank: 3

积分: 713
帖子: 693
精华: 0
UID: 1287999
性别: 保密

4^#

发表于 2011-7-23 12:42:04 |只看该作者

n*(n－1)/2

使用道具举报

superacid

银魔

Rank: 7 Rank: 7 Rank: 7

积分: 2520
帖子: 3072
精华: 7
UID: 62890
性别: 男

5^#

发表于 2011-7-23 20:29:22 |只看该作者

回复 4# 的帖子

线段互不相交。。。

19events = 644days
PB (2 3 4 5)B = 1200seconds
北大魔方爱好者QQ群74893945
mf8最少步讨论群：RP与公式的绝佳配合QQ群5652935

使用道具举报

返回列表

		自动登录	找回密码
密码			注册

n点连线问题 [复制链接]

回复 4# 的帖子

中国纪录

八年元老

论坛建设奖

爱心大使

十年元老

十二年元老