如何实现随机（A，B）仅具有随机（0,1）？

本文介绍了如何实现随机（A，B）仅具有随机（0,1）？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

可能重复：   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.