algorithm - 在 m 次迭代中均匀分布 n 个项目

Question

就上下文而言，这是在高精度应用中同时控制多个步进电机。

问题陈述
假设我有一个将运行 i 的循环迭代。在这些迭代过程中，表达式 E_x应评估为 true x次(保证 x <= i)。

要求
- E_x必须评估为 true 完全 x次
- E_x必须评估为 true或多或少均匀分布*

* "evenly spaced intervals"表示最小化最大间隔大小

示例
对于:i = 10 , x = 7
E_x将在标记为 1 的迭代中为真: 1101101101

对于:i = 10 , x = 3
E_x将在标记为 1 的迭代中为真: 0010010010

对于:i = 10 , x = 2
E_x将在标记为 1 的迭代中为真: 0001000100

获得E_x 的最佳(甚至是“好”)方式是什么？评估为 true在均匀间隔的同时保证它是真的 x次？

This question接近我的，但是它假设 E_x将始终评估为 true在第一次和最后一次迭代中，这不符合我的要求(参见上面的第二个示例)。

Answer 1

我将使用一些不同的命名约定:让我们以 T 间隔 [1..T] 和 N 事件为解雇了。也让我们把这个问题作为一个循环问题来解决。为此，让我们在保证触发事件的末尾添加一个假步骤(这也是时间 0 时的事件，即循环之前)。所以我的 T 是你的 i+1 而我的 N 是你的 x+1。

如果您将 T 除以 N 并带有提示，您将得到 T = w*N + r。如果 r=0 情况是微不足道的。如果 r != 0，您可以实现的最好结果是 r 大小为 w+1 和 (N-r) 的区间大小为 w 的间隔。快速简单但足够好的解决方案是这样的(伪代码):

events = []
w = T / N
r = T % N
current = 0
for(i = 1; i<=N; i++) {
   current += w;
   if (i <= r)
      current += 1;
   events[i] = current;
}

您可以看到数组中的最后一个值将是 T，正如我们作为循环问题重新声明所 promise 的那样。它将是 T 因为在循环中我们将 w 添加到 current N 次并添加 r 乘以 1，因此总和将为 w*N+r，即 T。

此解决方案的主要缺点是所有“长”间隔都将在开始处，而所有“短”间隔都将在结尾处。

如果你更聪明一点，你可以更均匀地分布间隔。结果逻辑将与 Bresenham's line algorithm 后面的逻辑基本相同。评论中引用。假设您在平面上画一条线，其中 X 轴代表时间，Y 轴代表事件，从 (0,0) (这是第 0 事件，在您的时间范围之前)到 (i+1, x+1)(这是 x+1-th 事件，就在您的时间范围之后)。引发事件的时刻是当您切换到下一个 Y 时，即在给定的 Y 处绘制第一个像素。