我目前正在用C++实现Eller's Algorithm,有一个小细节困扰着我,那就是迷宫的随机性。
到目前为止,我使用以下代码生成一个随机bool
:
bool randomBool()
{
return 0 + (rand() % (1 - 0 + 1)) == 1;
}
// In main.cpp
time_t seconds;
time(&seconds);
srand((unsigned int) seconds);
但在调试时,我经常看到重复的true
或false
生成,有时一行多达30次。
这个算法真的是随机的吗?或者在C++中有更好的方法吗?
6条答案
按热度按时间sc4hvdpw1#
C++11中的STL内置了上级
rand()
的随机数生成方法。你可以通过一个0或1的随机整数来模拟一个随机布尔值:您可以在标准C++参考中找到有关此库的更多详细信息。例如,如果你想要的不是50/50的“真”和“假”值的比例,你可以创建一个0和1之间的随机浮点数,并调用小于某个阈值z的值为true,否则为false。
为什么你看到长长的条纹,我想
我还没有说明为什么你的代码会连续得到30个“true”或“false”值。虽然
rand()
不应该再被使用,而且你的代码中似乎有一些不必要的1和0的加减,但不应该有这样的问题。然而,我现在意识到你的问题中的文本是模糊的。如果您连续运行并退出程序30次,您应该会看到重复的值--即使是我的代码。大多数随机数生成器实际上是伪随机数生成器。每次你运行程序,它们都会产生 * 相同 * 的随机数序列;这对于结果的一致性是重要的。然而,当程序运行时(例如,将randomBool()
放入一个循环中),您不应该看到这样长度的条纹,因为它们是极不可能的。不可能出现长条纹
我很惊讶地收到不同意我的Assert的评论,即连续30个“真”或“假”随机布尔值是不可能的(当真或假的可能性相等时)。我意识到,对概率的一个常见误解是,“运气”试图使事情变得均匀,因此,如果抛硬币连续几次出现正面,那么宇宙将试图纠正这一点,使反面更有可能。由于这种误解,人们低估了得到所有正面和所有反面条纹的可能性,我认为对这个答案和主要问题的评论的动机是纠正这个常见的错误。
然而,有一个真实的的原因,长条纹(特别是长达30)越来越不可能。使用随机无偏抛硬币的语言,每个IID(独立同分布)抛硬币只有50%的机会与前一个相同。因此,长条纹的概率随着条纹的长度呈指数下降。对于长度为L的条纹,所有头的条纹的概率为1/2^L;任一类型的条纹的概率为2/2 ^L或1/2^(L-1)。下面是一些要演示的代码:
输出直方图为:
难以计算在多个翻转N中长度为L的条纹的预期数量,因为存在许多长度为L的重叠延伸,其中可能存在这样的条纹。然而,请注意,该直方图大致遵循指数分布,每个条目大约是前一条目的一半。
最大条纹为24 [注:上一版本中的一个错误将此计数为23]。在任意一串24次独立掷硬币的串中,出现这种长度的连续掷硬币的概率是1/2^(24-1),或者说大约是1/800万。由于在1 e8次投掷中,大约有1 e8/24 ~ 430万次这样的独立延伸,我们预计会有少量这样的条纹,所以这似乎是正确的[我上面的警告是计算精确的期望值是困难的]。与此同时,在任何30次翻转的独立延伸中,长度为30的连续概率为5.37亿分之一,甚至比长度为24的连续概率要小得多。
e7arh2l62#
这可能是将
rand()
的输出转换为布尔值的最糟糕的方法。在许多实现中,较低阶位比较高阶位随机性小得多。理想情况下,您可以完全使用其他东西,但如果您必须使用
rand()
,请尝试:csga3l583#
下面是一个C++11函数模板,它以指定的概率生成布尔结果(二项分布)(默认0.5表示均匀):
bd1hkmkf4#
伪随机数生成器的较低阶位倾向于提供较少的随机性。对于内置的
rand()
函数尤其如此,它通常被实现为LCG。生成随机bool
的最佳方法是使用MSB位。这实际上是标准的Bernoulli distribution,概率为1/2
。e0uiprwp5#
如果
rand()
是真正的伪随机,则它是真正的伪随机,尽管如果RAND_MAX
是偶数(即偶数比奇数多一个),则分布可能非常轻微地不均匀。但通常RAND_MAX
足够大,可以忽略差异。yi0zb3m46#
在现代C++中,有一种专门的方法来生成随机布尔值-通过伯努利分布:
详情请参见here