algorithm - 号码分布

Question

问题:我们有 x 个复选框，我们想均匀地检查其中的 y 个。

示例 1:从总共 100 个复选框中选择 50 个。

[-]
[x]
[-]
[x]
...

示例 2:选择 33 个复选框，共 100 个复选框。

[-]
[-]
[x]
[-]
[-]
[x]
...

示例 3:从总共 100 个复选框中选择 66 个:

[-]
[x]
[x]
[-]
[x]
[x]
...

但是我们很难想出一个公式来在代码中检查它们，尤其是当您进行 11/111 或类似操作时。有人有想法吗？

Answer 1

让我们首先假设 y可以被 x 整除.然后我们表示 p = y/x解决方案很简单。遍历列表，每个p元素，标记其中的 1 个。

现在，假设r = y%x是非零的。还是p = y/x其中 /是整数除法。所以，你需要:

• 在第一个p-r元素，标记1个元素
• 在最后r元素，标记2个元素

注意:这取决于您如何定义均匀分布。你可能想传播 r带有 x+1 的部分p-r 之间的元素带有 x 的部分元素，这确实又是同一个问题，可以递归解决。

好吧，它实际上并不正确。我认为这样做可以:

不管可分性:

• 如果y > 2*x , 然后每 p = y/x 标记 1 个元素元素，x次。
• 如果y < 2*x ，然后标记所有，并执行上一步取消标记 y-x来自 y复选框(与前面的情况一样，但是 x 被 y-x 代替)

注意:这取决于您如何定义均匀分布。您可能希望在 p 之间切换和 p+1例如元素以更好地分发它们。