号码分发

Question

问题:我们有x个复选框,我们想要均匀地检查它们.

示例1:选择50个总共100个复选框.

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

示例2:选择总共100个的33个复选框.

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

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

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

但是我们很难想出一个公式来检查代码,特别是一旦你进入11/111或类似的东西.有人有想法吗？

Answer 1

这是使用整数算术的简单解决方案：

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每次迭代时至少增加 1，因为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不会发生被零除的情况，因为 ifcheck_count为 0，则相关循环的迭代次数为零。