c - for 循环中 rand() 的逻辑困惑

Question

我正在尝试执行跳过列表插入，因此我使用 rand() 来确定级别。我知道我需要连续抛硬币，所以我想如果我打印生成器的测试计数，每个连续级别的计数应该减少大约 50%。我不知何故搞乱了逻辑，但我无法发现我的错误。在最后一个级别上，它是 ~== 到之前的级别，而不是一半。

这是我的代码:

#define MAXLEVEL 5
srand(time(NULL));
int newLevel;
int a[6] = {0};
for (int i = 0; i < 100000; i++) {      
    for (newLevel = 0; (rand() < RAND_MAX/2) && (newLevel < MAXLEVEL); newLevel++);
    a[newLevel]++;
}
printf("0: %d   1: %d   2: %d   3: %d   4: %d   5: %d\n", a[0], a[1], a[2], a[3], a[4], a[5]);

这是输出:

0: 50018   1: 24969   2: 12532   3: 6334   4: 3094   5: 3053

我有点以为我的错误是愚蠢的，但我已经研究这个问题有一段时间了，但似乎无法理解它。

Answer 1

假设我们到达了i关卡。我们晋升到下一个级别的机会约为 0.5。这意味着，如果我们到达第 i 级 N 次，那么大约 0.5*N 次我们会在第 i 级停止，大约 0.5 次*我们N次晋升到下一个级别。同样，我们在级别 i 处停止约 0.5*N 次，并且所有其他级别值的总和也是约 0.5*N。因此，无论总级别有多少，最后两个级别都具有相似的值。

预计序列为 X、X/2、X/4、X/8、X/16、X/16。如果您希望最后一个成员为X/32，只需添加人工级别即可。