在书中 算法简介，有一个消费税：
描述只调用Random（0,1）的过程Random（a，b）的实现。作为a和b的函数，您的程序的预期运行时间是多少？ Random（a，b）结果的概率应该是纯粹均匀分布的，如Random（0,1）
对于Random函数，结果是a和b之间的整数，包括在内。例如，Random（0,1）生成0或1;随机（a，b）生成a，a + 1，a + 2，...，b
我的解决方案是这样的：
for i = 1 to b-a
r = a + Random(0,1)
return r
运行时间是 T = B-A
它是否正确？我的解决方案的结果是否均匀分布？
谢谢
如果我的新解决方案如下所示：
r = a
for i = 1 to b - a //including b-a
r += Random(0,1)
return r
如果不正确，为什么r + = Random（0,1）使r不均匀分布？
其他人解释了为什么你的解决方案不起作用。这是正确的解决方案：
1）找到最小的数字， p这样的 2^p > b-a。
2）执行以下算法：
r=0
for i = 1 to p
r = 2*r + Random(0,1)
3）如果 r 大于 b-a，转到第2步。
4）你的结果是 r+a
那么让我们试试随机（1,3）。
所以 b-a 是2。
2^1 = 2所以 p 必须是2才这样 2^p 大于2。
所以我们将循环两次。让我们尝试所有可能的输出：
00 -> r=0, 0 is not > 2, so we output 0+1 or 1.
01 -> r=1, 1 is not > 2, so we output 1+1 or 2.
10 -> r=2, 2 is not > 2, so we output 2+1 or 3.
11 -> r=3, 3 is > 2, so we repeat.
所以1/4的时间，我们输出1. 1/4我们输出的时间2. 1/4我们输出的时间3.而1/4的时间我们必须再次重复算法。看起来不错。
请注意，如果您必须执行此操作，则可以使用两个优化：
1）如果你经常使用相同的范围，有一个计算的类 p 一旦这样你就不必每次都计算它。
2）许多CPU具有执行步骤1的快速方法，这些方法未在高级语言中公开。例如，x86 CPU有 BSR 指令。
不，这不正确，该方法将集中精力 (a+b)/2。这是一个二项分布。
你确定吗？ Random(0,1) 产生整数？如果它产生0到1之间的浮点值，那将更有意义。然后解决方案将是仿射变换，运行时间独立于 a 和 b。
我刚才有一个想法，如果它是关于整数值：使用二分法。在每一步，你都有一个范围 low-high。如果 Random(0,1) 返回0，下一个范围是 low-(low+high)/2否则 (low+high)/2-high。
细节和复杂性留给你，因为它是功课。
这应该创造（近似）均匀分布。
编辑： 约 是那里的重要词汇。制服如果 b-a+1 是2的幂，如果接近则不太远，但一般不够好。啊，这是一个自发的想法，不能让他们没事。
我读了其他的答案。为了好玩，这是找到随机数的另一种方法：
使用分配数组 b-a 元素。
将所有值设置为 1。
遍历数组。对于每个非零元素，按原样翻转硬币。如果它出现了 0，将元素设置为 0。
每当完成一次迭代后，你只剩下1个元素，你就得到了你的随机数： a+i 哪里 i 是非零元素的索引（假设我们开始索引 0）。那么所有数字都是同样可能的。 （你必须处理它是一个平局的情况，但我把它作为练习留给你。）
这会有 O(infinity) ...... :)
但平均而言，一半的数字将被消除，因此它的平均案例运行时间为 log_2 (b-a)。
首先，我假设您实际上正在累积结果，而不是在每一步上添加0或1。 使用一些概率可以证明您的解决方案不是均匀分布的。结果值r为（a + b）/ 2的可能性最大。例如，如果a为0且b为7，则获得值4的机会是（7的组合4）除以2提升到7的幂。原因是无论7个值中的哪4个值是1，结果仍然是4。
您估计的运行时间是正确的。
在您创建的算法中，它实际上并不是均匀分布的。
结果“r”将始终为“a”或“a + 1”。它永远不会超越它。
它应该看起来像这样：
r=0;
for i=0 to b-a
r = a + r + Random(0,1)
return r;
通过在计算中包含“r”，您可以包含所有先前“for”循环运行的“随机性”。
不，您的解决方案不正确。这个总和将具有二项分布。
但是，您可以生成0,1的纯随机序列，并将其视为二进制数。
repeat
result = a
steps = ceiling(log(b - a))
for i = 0 to steps
result += (2 ^ i) * Random(0, 1)
until result <= b
KennyTM：我的坏。
您的解决方案的伪代码应如下所示：
r=a
for i = 0 to b-a
r+=Random(0,1)
return r
至于均匀分布，假设该随机数发生器基于的随机实现是完全一致的，获得0或1的几率是50％。因此，获得您想要的数字是一遍又一遍的选择的结果。
因此，对于a = 1，b = 5，有5个选择。
获得1的几率涉及5个决定，均为0，其可能性为0.5 ^ 5 = 3.125％
获得5的几率涉及5个决定，全部为1，其可能性为0.5 ^ 5 = 3.125％
从中可以看出，分布不均匀 - 任何数字的几率应为20％。