0

这个问题可以作为一个数学问题发布,但由于我想实现这个,我认为这将是一个更好的地方。

我有一个需要解决的问题,我正在尝试以最好的方式解决它。

我有两个单位,我想预测这些单位何时到达确定的点并相遇。这些单元以圆形/椭圆的方式移动,预测每个单元何时到达该点的方程很容易计算。时间是离散的,这意味着系统以滴答为单位工作,所以我们有 times = t0, t1, t2, ... 等等。

所以例子是这样的,让我们称他们将遇到P的点。

单元 1 有两个方程,因此对于任何 x,t 是单元 1 在 P 上的时间。

 t = 10x + 1
 t = 10x + 9

单元 1 将在 P 上:1, 9, 11, 19, ...

与第 2 单元相同:

 t = 6y + 1
 t = 6y + 5

单元 1 将在 P 上:1, 5, 7, 11, 17, ...

所以在 t = 11 时,各单位将在 P 会面。可能会有更多的会面时间,但只发生了一次。

由于这些等式可能会产生无限数量的会议时间,因此引入了一个时间限制,我们称这个时间限制为 L。因此,鉴于这些等式,我想计算所有小于 L 的时间(滴答声),其中单位彼此相遇.

请注意,我们可以为每对方程构建一个排序列表/数组并计算交集,但我认为这可以以更智能的方式解决。

我们如何使用方程来解决这个问题?有可能还是我们真的需要构建数组?这个问题的下限是多少?这可以在 O(1) 中完成吗?如果我们对问题添加一些限制,我们可以让它在 O(1) 中工作吗?比如,如果我们只想知道第一次见面的时间,或者任何一次见面的时间。

我相信这最终会在 O(L) 中结束,因为我们最多有两个大小为 L 的排序数组,并且我们可以通过每个数组一次获得交集。

模组,请随时纠正英语错误,这不是我的主要语言。

4

1 回答 1

1

查看所有组合:

  • 10x + 16y + 130k + 1 = {1, 31, 61, ...}
  • 10x + 16y + 530k + 11 = {11, 41, 71, ...}
  • 10x + 96y + 130k + 19 = {19, 49, 79, ...}
  • 10x + 96y + 530k + 29 = {29, 59, 89, ...}
于 2013-06-15T10:31:09.647 回答