给定一个函数,它产生的是1到5之间的随机整数,写一个函数,它产生的是1到7之间的随机整数。
当前回答
这是我的,它试图从多个rand5()函数调用中重新创建Math.random(),通过使用“加权分数”(?)重新构造一个单位间隔(Math.random()的输出范围)。然后使用这个随机单位间隔产生一个1到7之间的随机整数:
function rand5(){
return Math.floor(Math.random()*5)+1;
}
function rand7(){
var uiRandom=0;
var div=1;
for(var i=0; i<7; i++){
div*=5;
var term=(rand5()-1)/div;
uiRandom+=term;
}
//return uiRandom;
return Math.floor(uiRandom*7)+1;
}
解释一下:我们取一个0-4之间的随机整数(只是rand5()-1),然后将每个结果乘以1/ 5,1 / 25,1 /125,…然后把它们加起来。这类似于二元加权分数的工作原理;相反,我认为我们将其称为五(以5为底)加权分数:产生一个从0 - 0.999999作为一系列(1/5)^n项的数字。
修改函数以获取任何输入/输出随机整数范围应该是简单的。上面的代码可以在重写为闭包时进行优化。
或者,我们也可以这样做:
function rand5(){
return Math.floor(Math.random()*5)+1;
}
function rand7(){
var buffer=[];
var div=1;
for (var i=0; i<7; i++){
buffer.push((rand5()-1).toString(5));
div*=5;
}
var n=parseInt(buffer.join(""),5);
var uiRandom=n/div;
//return uiRandom;
return Math.floor(uiRandom*7)+1;
}
我们不需要费力地构造一个五进制(以5为基数)加权分数,而是实际地构造一个五进制数,并将其转化为一个分数(0—0.9999…和前面一样),然后从那里计算随机的1- 7位数字。
上面的结果(代码片段#2:运行3次,每次100,000次调用):
1: 14263; 2: 14414; 3: 14249; 4: 14109; 5: 14217; 6: 14361; 7: 14387 1: 14205; 2: 14394; 3: 14238; 4: 14187; 5: 14384; 6: 14224; 7: 14368 1: 14425; 2: 14236; 3: 14334; 4: 14232; 5: 14160; 6: 14320; 7: 14293
其他回答
假设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
这里允许作业题吗?
这个函数进行粗略的“以5为基数”的数学运算,生成0到6之间的数字。
function rnd7() {
do {
r1 = rnd5() - 1;
do {
r2=rnd5() - 1;
} while (r2 > 1);
result = r2 * 5 + r1;
} while (result > 6);
return result + 1;
}
对于0-7的值,你有以下内容:
0 000
1 001
2 010
3 011
4 100
5 101
6 110
7 111
从左到右,Rand5()有p(1) ={2/ 5,2 / 5,3 /5}。因此,如果我们补这些概率分布(~Rand5()),我们应该能够使用它来生成我们的数字。我稍后会给出解决方案。有人有什么想法吗?
R
简单的解决方案已经被很好地覆盖了:为一个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的代价非常昂贵(比如调用一些外部熵源)。