给定一个函数,它产生的是1到5之间的随机整数,写一个函数,它产生的是1到7之间的随机整数。
当前回答
为什么不除以5再乘以7,然后四舍五入呢?(当然,你必须使用浮点数no.)
它比其他解决方案更简单、更可靠(真的吗?)例如,在Python中:
def ranndomNo7():
import random
rand5 = random.randint(4) # Produces range: [0, 4]
rand7 = int(rand5 / 5 * 7) # /5, *7, +0.5 and floor()
return rand7
这不是很容易吗?
其他回答
我想我有四个答案,两个给出了像@Adam Rosenfield那样的精确解决方案,但没有无限循环问题,另外两个几乎完美的解决方案,但执行速度比第一个更快。
最好的精确解决方案需要7次调用rand5,但为了理解,让我们继续。
方法一:精确
Adam的答案的优点在于它给出了一个完美的均匀分布,并且只需要两次调用rand5()的概率非常高(21/25)。然而,最坏的情况是无限循环。
下面的第一个解决方案也给出了一个完美的均匀分布,但总共需要对rand5进行42次调用。没有无限循环。
下面是一个R的实现:
rand5 <- function() sample(1:5,1)
rand7 <- function() (sum(sapply(0:6, function(i) i + rand5() + rand5()*2 + rand5()*3 + rand5()*4 + rand5()*5 + rand5()*6)) %% 7) + 1
对于不熟悉R的人,这里是一个简化版本:
rand7 = function(){
r = 0
for(i in 0:6){
r = r + i + rand5() + rand5()*2 + rand5()*3 + rand5()*4 + rand5()*5 + rand5()*6
}
return r %% 7 + 1
}
rand5的分布将被保留。如果我们计算一下,循环的7次迭代中的每一次都有5^6个可能的组合,因此可能组合的总数为(7 * 5^6)%% 7 = 0。因此,我们可以将生成的随机数分成7个相等的组。有关这方面的更多讨论,请参见方法二。
以下是所有可能的组合:
table(apply(expand.grid(c(outer(1:5,0:6,"+")),(1:5)*2,(1:5)*3,(1:5)*4,(1:5)*5,(1:5)*6),1,sum) %% 7 + 1)
1 2 3 4 5 6 7
15625 15625 15625 15625 15625 15625 15625
我认为这很容易证明亚当的方法运行得快得多。在Adam的解中有42次或更多的rand5调用的概率非常小((4/25)^21 ~ 10^(-17))。
方法2 -不精确
现在是第二个方法,它几乎是统一的,但需要6次调用rand5:
rand7 <- function() (sum(sapply(1:6,function(i) i*rand5())) %% 7) + 1
以下是一个简化版本:
rand7 = function(){
r = 0
for(i in 1:6){
r = r + i*rand5()
}
return r %% 7 + 1
}
这实际上是方法1的一次迭代。如果我们生成所有可能的组合,结果计数如下:
table(apply(expand.grid(1:5,(1:5)*2,(1:5)*3,(1:5)*4,(1:5)*5,(1:5)*6),1,sum) %% 7 + 1)
1 2 3 4 5 6 7
2233 2232 2232 2232 2232 2232 2232
一个数字将在5^6 = 15625次试验中再次出现。
现在,在方法1中,通过将1加到6,我们将数字2233移动到每个连续的点上。因此,组合的总数将匹配。这是可行的,因为5^ 6% % 7 = 1,然后我们做了7个适当的变化,所以(7 * 5^ 6% % 7 = 0)。
方法三:精确
如果理解了方法1和2的参数,接下来就是方法3,它只需要7次调用rand5。在这一点上,我觉得这是精确解决方案所需的最少调用数。
下面是一个R的实现:
rand5 <- function() sample(1:5,1)
rand7 <- function() (sum(sapply(1:7, function(i) i * rand5())) %% 7) + 1
对于不熟悉R的人,这里是一个简化版本:
rand7 = function(){
r = 0
for(i in 1:7){
r = r + i * rand5()
}
return r %% 7 + 1
}
rand5的分布将被保留。如果我们计算一下,循环的7次迭代中的每一次都有5个可能的结果,因此可能组合的总数为(7 * 5)%% 7 = 0。因此,我们可以将生成的随机数分成7个相等的组。有关这方面的更多讨论,请参见方法一和方法二。
以下是所有可能的组合:
table(apply(expand.grid(0:6,(1:5)),1,sum) %% 7 + 1)
1 2 3 4 5 6 7
5 5 5 5 5 5 5
我认为这很直接地证明了亚当的方法仍然运行得更快。在Adam的解中有7次或更多的rand5调用的概率仍然很小((4/25)^3 ~ 0.004)。
方法4 -不精确
这是第二种方法的一个小变化。它几乎是统一的,但需要7次调用rand5,这是一个额外的方法2:
rand7 <- function() (rand5() + sum(sapply(1:6,function(i) i*rand5())) %% 7) + 1
以下是一个简化版本:
rand7 = function(){
r = 0
for(i in 1:6){
r = r + i*rand5()
}
return (r+rand5()) %% 7 + 1
}
如果我们生成所有可能的组合,结果计数如下:
table(apply(expand.grid(1:5,(1:5)*2,(1:5)*3,(1:5)*4,(1:5)*5,(1:5)*6,1:5),1,sum) %% 7 + 1)
1 2 3 4 5 6 7
11160 11161 11161 11161 11161 11161 11160
在5^7 = 78125次试验中,有两个数字会少出现一次。在大多数情况下,我可以接受。
为什么不简单一点呢?
int random7() {
return random5() + (random5() % 3);
}
由于取模,在这个解中得到1和7的几率较低,然而,如果你只是想要一个快速和可读的解,这是一种方法。
上面引用了一些优雅的算法,但这里有一种方法可以接近它,尽管它可能是迂回的。我假设的值是从0开始的。
R2 =给出小于2的随机数生成器(样本空间= {0,1}) R8 =给出小于8的随机数生成器(样本空间= {0,1,2,3,4,5,6,7})
为了从R2生成R8,您将运行R2三次,并将所有3次运行的组合结果作为3位二进制数使用。下面是R2运行三次时的值范围:
0, 0, 0 --> 0 . . 1, 1, 1 --> 7
现在要从R8生成R7,我们只需再次运行R7,如果它返回7:
int R7() {
do {
x = R8();
} while (x > 6)
return x;
}
迂回的解决方案是从R5生成R2(就像我们从R8生成R7一样),然后从R2生成R8,然后从R8生成R7。
这类似于@RobMcAfee,除了我使用魔术数字而不是2维数组。
int rand7() {
int m = 1203068;
int r = (m >> (rand5() - 1) * 5 + rand5() - 1) & 7;
return (r > 0) ? r : rand7();
}
这个答案更像是一个从Rand5函数中获得最大熵的实验。因此,T有点不清楚,几乎可以肯定比其他实现慢得多。
假设0-4为均匀分布,0-6为均匀分布:
public class SevenFromFive
{
public SevenFromFive()
{
// this outputs a uniform ditribution but for some reason including it
// screws up the output distribution
// open question Why?
this.fifth = new ProbabilityCondensor(5, b => {});
this.eigth = new ProbabilityCondensor(8, AddEntropy);
}
private static Random r = new Random();
private static uint Rand5()
{
return (uint)r.Next(0,5);
}
private class ProbabilityCondensor
{
private readonly int samples;
private int counter;
private int store;
private readonly Action<bool> output;
public ProbabilityCondensor(int chanceOfTrueReciprocal,
Action<bool> output)
{
this.output = output;
this.samples = chanceOfTrueReciprocal - 1;
}
public void Add(bool bit)
{
this.counter++;
if (bit)
this.store++;
if (counter == samples)
{
bool? e;
if (store == 0)
e = false;
else if (store == 1)
e = true;
else
e = null;// discard for now
counter = 0;
store = 0;
if (e.HasValue)
output(e.Value);
}
}
}
ulong buffer = 0;
const ulong Mask = 7UL;
int bitsAvail = 0;
private readonly ProbabilityCondensor fifth;
private readonly ProbabilityCondensor eigth;
private void AddEntropy(bool bit)
{
buffer <<= 1;
if (bit)
buffer |= 1;
bitsAvail++;
}
private void AddTwoBitsEntropy(uint u)
{
buffer <<= 2;
buffer |= (u & 3UL);
bitsAvail += 2;
}
public uint Rand7()
{
uint selection;
do
{
while (bitsAvail < 3)
{
var x = Rand5();
if (x < 4)
{
// put the two low order bits straight in
AddTwoBitsEntropy(x);
fifth.Add(false);
}
else
{
fifth.Add(true);
}
}
// read 3 bits
selection = (uint)((buffer & Mask));
bitsAvail -= 3;
buffer >>= 3;
if (selection == 7)
eigth.Add(true);
else
eigth.Add(false);
}
while (selection == 7);
return selection;
}
}
每次调用Rand5添加到缓冲区的比特数目前是4/5 * 2,所以是1.6。 如果包括1/5的概率值,则增加0.05,因此增加1.65,但请参阅代码中的注释,我不得不禁用它。
调用Rand7消耗的比特数= 3 + 1/8 *(3 + 1/8 *(3 + 1/8 *(… 这是3 + 3/8 + 3/64 + 3/512…大约是3.42
通过从7中提取信息,我每次调用回收1/8*1/7位,大约0.018
这使得每次调用的净消耗为3.4比特,这意味着每一次Rand7调用到Rand5的比率为2.125。最优值应该是2.1。
我可以想象这种方法比这里的许多其他方法都要慢得多,除非调用Rand5的代价非常昂贵(比如调用一些外部熵源)。