u*****r
发帖数: 39 | 1 我遇到一个数学难题，情教大牛们：
在一个圆的圆环上分布了n个点， n个点互不重合。 n个点中，每3点可以确定一个三角
形， 这样最多有n/3个三角形。 对于一个给定的n点分布， 问最多有多少个锐角三角
形？ 如何计算。 |
s*****s
发帖数: 1559 | 2 你这个n/3.... 没学过中学排列组合？
【在 u*****r 的大作中提到】
: 我遇到一个数学难题，情教大牛们：
: 在一个圆的圆环上分布了n个点， n个点互不重合。 n个点中，每3点可以确定一个三角
: 形， 这样最多有n/3个三角形。 对于一个给定的n点分布， 问最多有多少个锐角三角
: 形？ 如何计算。
|
u*****r
发帖数: 39 | 3 补充：每个点不能被重复利用，所以n个点，最有只能有n/3个三角形。 |
s*****s
发帖数: 1559 | 4 如果n个点集中在很短的一段弧上， 一个锐角三角形都没有。
不知道你的问题具体是什么？ 是算法？
【在 u*****r 的大作中提到】
: 我遇到一个数学难题，情教大牛们：
: 在一个圆的圆环上分布了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 的大作中提到】
: 我遇到一个数学难题，情教大牛们：
: 在一个圆的圆环上分布了n个点， n个点互不重合。 n个点中，每3点可以确定一个三角
: 形， 这样最多有n/3个三角形。 对于一个给定的n点分布， 问最多有多少个锐角三角
: 形？ 如何计算。
|
c*******L
发帖数: 125 | 8 可以看看是不是能这样解
我觉得本质上就是把圆周分成两个半圆
其中一个半圆上有n个点，另外一个有m个
求这样一个半圆使得min(n-1,m)最大
求解这个问题是线性的，圆周上有N个点，只要比较N次就可以了
【在 u*****r 的大作中提到】
: 我遇到一个数学难题，情教大牛们：
: 在一个圆的圆环上分布了n个点， n个点互不重合。 n个点中，每3点可以确定一个三角
: 形， 这样最多有n/3个三角形。 对于一个给定的n点分布， 问最多有多少个锐角三角
: 形？ 如何计算。
|
a***s
发帖数: 616 | 9 Agree
如果能够找到一条直径使得直径两侧的点尽可能相等就可以了。
【在 c*******L 的大作中提到】
: 可以看看是不是能这样解
: 我觉得本质上就是把圆周分成两个半圆
: 其中一个半圆上有n个点，另外一个有m个
: 求这样一个半圆使得min(n-1,m)最大
: 求解这个问题是线性的，圆周上有N个点，只要比较N次就可以了
|
s*****s
发帖数: 1559 | 10 not agree.
没这么简单呢
【在 a***s 的大作中提到】
: Agree
: 如果能够找到一条直径使得直径两侧的点尽可能相等就可以了。
|
|
|
u*****r
发帖数: 39 | 11 没有看懂，我觉得用brutal force search, time complexity is exponential.
【在 j******n 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 想过了， dynamic programming 在这个问题上行不通
|
j******n
发帖数: 271 | |
u*****r
发帖数: 39 | 15 要用dynamic programming也是可以的，只是复杂度还是exponential的
【在 i******t 的大作中提到】
: why not? The vertices of the triangles are non-overlapping...
|
u*****r
发帖数: 39 | 16 还没有找到polynomial time complexity 的最优算法。
【在 j******n 的大作中提到】
: 做出来了吗?
|
i******t
发帖数: 370 | 17 恩，确实不好弄
【在 u*****r 的大作中提到】
: 要用dynamic programming也是可以的，只是复杂度还是exponential的
|
