给定一个函数,它产生的是1到5之间的随机整数,写一个函数,它产生的是1到7之间的随机整数。
当前回答
//返回0-5之间概率相等的随机数 函数rand5() { return Math.floor(Math.random() * 6); } //返回0-7之间概率相等的随机数 函数rand7() { If (rand5() % 2 == 0 && rand5() % 2 == 0) { 返回6 + rand5() % 2; }其他{ 返回rand5 (); } } console.log (rand7 ());
其他回答
什么是简单的解决方案?(rand5() + rand5()) % 7 + 1 减少内存使用或在较慢的CPU上运行的有效解决方案是什么?是的,这是有效的,因为它只调用rand5()两次,空间复杂度为O(1)
考虑rand5()给出从1到5(包括)的随机数。 (1 + 1) % 7 + 1 = 3 (1 + 2) % 7 + 1 = 4 (1 + 3) % 7 + 1 = 5 (1 + 4) % 7 + 1 = 6 (1 + 5) % 7 + 1 = 7
(2 + 1) % 7 + 1 = 4 (2 + 2) % 7 + 1 = 5 (2 + 3) % 7 + 1 = 6 (2 + 4) % 7 + 1 = 7 (2 + 5) % 7 + 1 = 1 .
(5 + 1) % 7 + 1 = 7 (5 + 2) % 7 + 1 = 1 (5 + 3) % 7 + 1 = 2 (5 + 4) % 7 + 1 = 3 (5 + 5) % 7 + 1 = 4 .
等等
简单的解决方案已经被很好地覆盖了:为一个random7结果取两个random5样本,如果结果超出了产生均匀分布的范围,就重新做一次。如果你的目标是减少对random5的调用次数,这是非常浪费的——对于每个random7输出,对random5的平均调用次数是2.38,而不是2,这是由于丢弃样本的数量。
你可以通过使用更多的random5输入一次生成多个random7输出来做得更好。对于使用31位整数计算的结果,最优结果是使用12次调用random5生成9个random7输出,平均每个输出调用1.34次。它是高效的,因为244140625个结果中只有2018983个需要废弃,或者不到1%。
Python演示:
def random5():
return random.randint(1, 5)
def random7gen(n):
count = 0
while n > 0:
samples = 6 * 7**9
while samples >= 6 * 7**9:
samples = 0
for i in range(12):
samples = samples * 5 + random5() - 1
count += 1
samples //= 6
for outputs in range(9):
yield samples % 7 + 1, count
samples //= 7
count = 0
n -= 1
if n == 0: break
>>> from collections import Counter
>>> Counter(x for x,i in random7gen(10000000))
Counter({2: 1430293, 4: 1429298, 1: 1428832, 7: 1428571, 3: 1428204, 5: 1428134, 6: 1426668})
>>> sum(i for x,i in random7gen(10000000)) / 10000000.0
1.344606
这个答案更像是一个从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的代价非常昂贵(比如调用一些外部熵源)。
假设rand(n)在这里表示“从0到n-1均匀分布的随机整数”,下面是使用Python的randint的代码示例,它具有这种效果。它只使用randint(5)和常量来产生randint(7)的效果。其实有点傻
from random import randint
sum = 7
while sum >= 7:
first = randint(0,5)
toadd = 9999
while toadd>1:
toadd = randint(0,5)
if toadd:
sum = first+5
else:
sum = first
assert 7>sum>=0
print sum
function Rand7
put 200 into x
repeat while x > 118
put ((random(5)-1) * 25) + ((random(5)-1) * 5) + (random(5)-1) into x
end repeat
return (x mod 7) + 1
end Rand7
3次调用Rand5,平均125次中只重复6次。
把它想象成一个5x5x5的3D数组,一遍又一遍地填满1到7,还有6个空格。重新滚动空白。rand5调用在该数组中创建一个以5为基数的三位索引。
4D或更高的n维数组的重复次数会更少,但这意味着对rand5函数的更多调用将成为标准。你会在更高维度上得到递减的效率回报。在我看来,三个似乎是一个很好的折衷方案,但我还没有对它们进行测试。它是特定于rand5实现的。