u*****r 发帖数: 39 | 1 我遇到一个数学难题,情教大牛们:
在一个圆的圆环上分布了n个点, n个点互不重合。 n个点中,每3点可以确定一个三角
形, 这样最多有n/3个三角形。 对于一个给定的n点分布, 问最多有多少个锐角三角
形? 如何计算。 |
s*****s 发帖数: 1559 | 2 你这个n/3.... 没学过中学排列组合?
【在 u*****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我遇到一个数学难题,情教大牛们: : 在一个圆的圆环上分布了n个点, n个点互不重合。 n个点中,每3点可以确定一个三角 : 形, 这样最多有n/3个三角形。 对于一个给定的n点分布, 问最多有多少个锐角三角 : 形? 如何计算。
|
u*****r 发帖数: 39 | 3 补充:每个点不能被重复利用,所以n个点,最有只能有n/3个三角形。 |
s*****s 发帖数: 1559 | 4 如果n个点集中在很短的一段弧上, 一个锐角三角形都没有。
不知道你的问题具体是什么? 是算法?
【在 u*****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我遇到一个数学难题,情教大牛们: : 在一个圆的圆环上分布了n个点, n个点互不重合。 n个点中,每3点可以确定一个三角 : 形, 这样最多有n/3个三角形。 对于一个给定的n点分布, 问最多有多少个锐角三角 : 形? 如何计算。
|
u*****r 发帖数: 39 | 5 楼上说的那种情况,是一个锐角三角形都没有。
我的问题就是找到一个算法:对一个给定的n点分布在圆环上,计算最多能组成多少个
锐角三角形。 每个点不能被重复利用。 |
j******n 发帖数: 271 | 6 brutal_force(): // not mathematics but programming
a:
for (int k=2; k
for (int j=1; j
for (int i=0; i
map[(i,j,k)] = acute_or_not;
b:
for p in {(j,k): j>0, j>k):
c:
count max number of acute triangles formed with {l,m,n not in 0, j, k}
d:
add 1 if (0, j, k) is acute
e:
take max from those in step b
note that step c calls b recursively with a reduced set
and that a 50% speed up can be obtained by also keep track of number of
obtuse triangles and abort a recursion when i |
i******t 发帖数: 370 | 7 If you are looking for an algorithm, try dynamic programming
【在 u*****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我遇到一个数学难题,情教大牛们: : 在一个圆的圆环上分布了n个点, n个点互不重合。 n个点中,每3点可以确定一个三角 : 形, 这样最多有n/3个三角形。 对于一个给定的n点分布, 问最多有多少个锐角三角 : 形? 如何计算。
|
c*******L 发帖数: 125 | 8 可以看看是不是能这样解
我觉得本质上就是把圆周分成两个半圆
其中一个半圆上有n个点,另外一个有m个
求这样一个半圆使得min(n-1,m)最大
求解这个问题是线性的,圆周上有N个点,只要比较N次就可以了
【在 u*****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我遇到一个数学难题,情教大牛们: : 在一个圆的圆环上分布了n个点, n个点互不重合。 n个点中,每3点可以确定一个三角 : 形, 这样最多有n/3个三角形。 对于一个给定的n点分布, 问最多有多少个锐角三角 : 形? 如何计算。
|
a***s 发帖数: 616 | 9 Agree
如果能够找到一条直径使得直径两侧的点尽可能相等就可以了。
【在 c*******L 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 可以看看是不是能这样解 : 我觉得本质上就是把圆周分成两个半圆 : 其中一个半圆上有n个点,另外一个有m个 : 求这样一个半圆使得min(n-1,m)最大 : 求解这个问题是线性的,圆周上有N个点,只要比较N次就可以了
|
s*****s 发帖数: 1559 | 10 not agree.
没这么简单呢
【在 a***s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Agree : 如果能够找到一条直径使得直径两侧的点尽可能相等就可以了。
|
|
|
u*****r 发帖数: 39 | 11 没有看懂,我觉得用brutal force search, time complexity is exponential.
【在 j******n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : brutal_force(): // not mathematics but programming : a: : for (int k=2; k: for (int j=1; j: for (int i=0; i: map[(i,j,k)] = acute_or_not; : b: : for p in {(j,k): j>0, j>k): : c: : count max number of acute triangles formed with {l,m,n not in 0, j, k}
|
u*****r 发帖数: 39 | 12 想过了, dynamic programming 在这个问题上行不通
【在 i******t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : If you are looking for an algorithm, try dynamic programming
|
i******t 发帖数: 370 | 13 why not? The vertices of the triangles are non-overlapping...
【在 u*****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 想过了, dynamic programming 在这个问题上行不通
|
j******n 发帖数: 271 | |
u*****r 发帖数: 39 | 15 要用dynamic programming也是可以的,只是复杂度还是exponential的
【在 i******t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : why not? The vertices of the triangles are non-overlapping...
|
u*****r 发帖数: 39 | 16 还没有找到polynomial time complexity 的最优算法。
【在 j******n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 做出来了吗?
|
i******t 发帖数: 370 | 17 恩,确实不好弄
【在 u*****r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 要用dynamic programming也是可以的,只是复杂度还是exponential的
|