如何实现随机（A，B）仅具有随机（0,1）？ [英] How to implement Random(a,b) with only Random(0,1)?

问题描述

可能重复：
  <一href="http://stackoverflow.com/questions/8458392/how-to-get-uniformed-random-between-a-b-by-a-known-uniformed-random-function-ra">how让穿制服的任意一间，B用已知的穿制服的随机函数随机的（0,1）

在这本书算法导论的，有消费税：

描述的程序随机（A，B），只有让调用随机（0,1）的实现。什么是你的程序的预期运行时间，作为一个函数和b？随机的（A，B）应纯净均匀分布，结果的概率是随机的（0,1）

有关的随机功能，其结果是a和b之间的整数（含）。用于例如，随机（0,1）产生0或1;随机的（A，B）产生一，一个+ 1，A + 2，...，B

For the Random function, the results are integers between a and b, inclusively. For e.g., Random(0,1) generates either 0 or 1; Random(a, b) generates a, a+1, a+2, ..., b

我的解决方案是这样的：

My solution is like this:

for i = 1 to b-a
    r = a + Random(0,1)
return r

运行时间 T = B-A

这是正确的？是我的解决方案的结果均匀分布的？

Is this correct? Are the results of my solutions uniformly distributed?

感谢

如果我的新的解决方案是这样的：

What if my new solution is like this:

r = a
for i = 1 to b - a //including b-a
    r += Random(0,1)
return r

如果这是不正确的，为什么R + =随机（0,1），使R值不要均匀分布的？

If it is not correct, why r += Random(0,1) makes r not uniformly distributed?

推荐答案

也有人解释了为什么你的解决方案是行不通的。下面是正确的解决办法：

Others have explained why your solution doesn't work. Here's the correct solution:

1）找到最小的数， P ，使得 2 ^ P＆GT; B-A 。

1) Find the smallest number, p, such that 2^p > b-a.

2）执行以下的算法：

2) Perform the following algorithm:

r=0
for i = 1 to p
    r = 2*r + Random(0,1)

3）如果研究大于 BA ，转到步骤2。

3) If r is greater than b-a, go to step 2.

4）你的结果是 R + A

因此​​，让我们尝试随机（1,3）。
因此， B-A 为2
2 ^ 1 = 2 ，所以 P 将不得不为2，使 2 ^ P 大于2。
因此，我们将循环两次。让我们尝试所有可能的输出：

So let's try Random(1,3).
So b-a is 2.
2^1 = 2, so p will have to be 2 so that 2^p is greater than 2.
So we'll loop two times. Let's try all possible outputs:

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时间，我们不得不重复算法第二时间。看起来很不错。

So 1/4 of the time, we output 1. 1/4 of the time we output 2. 1/4 of the time we output 3. And 1/4 of the time we have to repeat the algorithm a second time. Looks good.

请注意，如果你必须这样做了很多，两人的优化都得心应手：

Note that if you have to do this a lot, two optimizations are handy:

1），如果使用相同的范围很多，有计算类 P 键，这样你就不必每次计算它。

1) If you use the same range a lot, have a class that computes p once so you don't have to compute it each time.

2）许多处理器有快速的方式来执行步骤1中未高级语言露出。例如，x86 CPU的有 BSR 的指令。

2) Many CPUs have fast ways to perform step 1 that aren't exposed in high-level languages. For example, x86 CPUs have the BSR instruction.

这篇关于如何实现随机（A，B）仅具有随机（0,1）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！