这个问题可以作为一个数学问题发布,但由于我想实现这个,我认为这将是一个更好的地方。
我有一个需要解决的问题,我正在尝试以最好的方式解决它。
我有两个单位,我想预测这些单位何时到达确定的点并相遇。这些单元以圆形/椭圆的方式移动,预测每个单元何时到达该点的方程很容易计算。时间是离散的,这意味着系统以滴答为单位工作,所以我们有 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 的排序数组,并且我们可以通过每个数组一次获得交集。
模组,请随时纠正英语错误,这不是我的主要语言。