algorithm - 号码分布

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

示例1:选择50个复选框(共100个)。

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

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

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

示例3:选择66个复选框(共100个):

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

但是我们很难提出一个公式来在代码中检查它们，尤其是当您使用11/111或类似的东西时。有人有主意吗？

最佳答案

这是使用整数算法的简单解决方案:

void check(char boxes[], int total_count, int check_count)
{
    int i;

    for (i = 0; i < total_count; i++)
        boxes[i] = '-';

    for (i = 0; i < check_count; i++)
        boxes[i * total_count / check_count] = 'x';
}

total_count是盒子的总数，而check_count是要检查的盒子的数量。

首先，它将每个复选框设置为未选中。然后，它检查check_count框，将计数器缩放到框数。

注意:这是左偏的，而不是像您的示例中的右偏。也就是说，它打印x--x--而不是--x--x。您可以通过更换来扭转它

        boxes[i * total_count / check_count] = 'x';

和:

        boxes[total_count - (i * total_count / check_count) - 1] = 'x';

正确性

假设0 <= check_count <= total_count，并且boxes至少可以容纳total_count项，我们可以证明:

没有复选标记将重叠。 i * total_count / check_count每次迭代至少增加一个，因为total_count >= check_count。

这不会使缓冲区溢出。下标i * total_count / check_count

将是>= 0。 i，total_count和check_count将全部为>= 0。

将是< total_count。当n > 0和d > 0时:

(n * d - 1) / d < n

换句话说，如果我们使用n * d / d，并将分子向下推，则商也会下降。

因此，按照上述假设，(check_count - 1) * total_count / check_count将小于total_count。除以零不会发生，因为如果check_count为0，则所讨论的循环将具有零迭代。

关于algorithm - 号码分布，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/8298708/