给定一个函数,它产生的是1到5之间的随机整数,写一个函数,它产生的是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。
其他回答
int rand7()
{
return ( rand5() + (rand5()%3) );
}
rand5() -返回1-5之间的值 rand5()%3 -返回0-2之间的值 所以,当加起来时,总价值将在1-7之间
就是这样,均匀分布,零rand5调用。
def rand7:
seed += 1
if seed >= 7:
seed = 0
yield seed
需要事先播种。
int randbit( void )
{
while( 1 )
{
int r = rand5();
if( r <= 4 ) return(r & 1);
}
}
int randint( int nbits )
{
int result = 0;
while( nbits-- )
{
result = (result<<1) | randbit();
}
return( result );
}
int rand7( void )
{
while( 1 )
{
int r = randint( 3 ) + 1;
if( r <= 7 ) return( r );
}
}
算法:
7可以用3位的序列表示
使用rand(5)随机地用0或1填充每一位。 例如:调用rand(5)和
如果结果是1或2,则用0填充位 如果结果是4或5,则用1填充位 如果结果是3,则忽略并重新执行(拒绝)
这样,我们可以用0/1随机填充3位,从而得到1-7中的数字。
编辑:这似乎是最简单和最有效的答案,所以这里有一些代码:
public static int random_7() {
int returnValue = 0;
while (returnValue == 0) {
for (int i = 1; i <= 3; i++) {
returnValue = (returnValue << 1) + random_5_output_2();
}
}
return returnValue;
}
private static int random_5_output_2() {
while (true) {
int flip = random_5();
if (flip < 3) {
return 0;
}
else if (flip > 3) {
return 1;
}
}
}
Here's a solution that fits entirely within integers and is within about 4% of optimal (i.e. uses 1.26 random numbers in {0..4} for every one in {0..6}). The code's in Scala, but the math should be reasonably clear in any language: you take advantage of the fact that 7^9 + 7^8 is very close to 5^11. So you pick an 11 digit number in base 5, and then interpret it as a 9 digit number in base 7 if it's in range (giving 9 base 7 numbers), or as an 8 digit number if it's over the 9 digit number, etc.:
abstract class RNG {
def apply(): Int
}
class Random5 extends RNG {
val rng = new scala.util.Random
var count = 0
def apply() = { count += 1 ; rng.nextInt(5) }
}
class FiveSevener(five: RNG) {
val sevens = new Array[Int](9)
var nsevens = 0
val to9 = 40353607;
val to8 = 5764801;
val to7 = 823543;
def loadSevens(value: Int, count: Int) {
nsevens = 0;
var remaining = value;
while (nsevens < count) {
sevens(nsevens) = remaining % 7
remaining /= 7
nsevens += 1
}
}
def loadSevens {
var fivepow11 = 0;
var i=0
while (i<11) { i+=1 ; fivepow11 = five() + fivepow11*5 }
if (fivepow11 < to9) { loadSevens(fivepow11 , 9) ; return }
fivepow11 -= to9
if (fivepow11 < to8) { loadSevens(fivepow11 , 8) ; return }
fivepow11 -= to8
if (fivepow11 < 3*to7) loadSevens(fivepow11 % to7 , 7)
else loadSevens
}
def apply() = {
if (nsevens==0) loadSevens
nsevens -= 1
sevens(nsevens)
}
}
如果你将一个测试粘贴到解释器中(实际上是REPL),你会得到:
scala> val five = new Random5
five: Random5 = Random5@e9c592
scala> val seven = new FiveSevener(five)
seven: FiveSevener = FiveSevener@143c423
scala> val counts = new Array[Int](7)
counts: Array[Int] = Array(0, 0, 0, 0, 0, 0, 0)
scala> var i=0 ; while (i < 100000000) { counts( seven() ) += 1 ; i += 1 }
i: Int = 100000000
scala> counts
res0: Array[Int] = Array(14280662, 14293012, 14281286, 14284836, 14287188,
14289332, 14283684)
scala> five.count
res1: Int = 125902876
分布很好,很平坦(在每个箱子中,10^8的1/7大约在10k范围内,就像预期的近似高斯分布一样)。