给定一个函数，它产生的是1到5之间的随机整数，写一个函数，它产生的是1到7之间的随机整数。
当前回答
rand7() = (rand5()+rand5()+rand5()+rand5()+rand5()+rand5()+rand5())%7+1
编辑:这并不奏效。误差约为千分之二(假设是完美的rand5)。桶得到:
value Count Error%
1 11158 -0.0035
2 11144 -0.0214
3 11144 -0.0214
4 11158 -0.0035
5 11172 +0.0144
6 11177 +0.0208
7 11172 +0.0144
通过转换到的和
n Error%
10 +/- 1e-3,
12 +/- 1e-4,
14 +/- 1e-5,
16 +/- 1e-6,
...
28 +/- 3e-11
似乎每增加2就增加一个数量级
BTW:上面的误差表不是通过采样产生的，而是通过以下递归关系产生的:
P [x,n]是给定n次调用rand5，输出=x可能发生的次数。
p[1,1] ... p[5,1] = 1
p[6,1] ... p[7,1] = 0
p[1,n] = p[7,n-1] + p[6,n-1] + p[5,n-1] + p[4,n-1] + p[3,n-1]
p[2,n] = p[1,n-1] + p[7,n-1] + p[6,n-1] + p[5,n-1] + p[4,n-1]
p[3,n] = p[2,n-1] + p[1,n-1] + p[7,n-1] + p[6,n-1] + p[5,n-1]
p[4,n] = p[3,n-1] + p[2,n-1] + p[1,n-1] + p[7,n-1] + p[6,n-1]
p[5,n] = p[4,n-1] + p[3,n-1] + p[2,n-1] + p[1,n-1] + p[7,n-1]
p[6,n] = p[5,n-1] + p[4,n-1] + p[3,n-1] + p[2,n-1] + p[1,n-1]
p[7,n] = p[6,n-1] + p[5,n-1] + p[4,n-1] + p[3,n-1] + p[2,n-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范围内，就像预期的近似高斯分布一样)。
我想到了一个解决这个问题的有趣方法，想和大家分享一下。
function rand7() {
var returnVal = 4;
for (var n=0; n<3; n++) {
var rand = rand5();
if (rand==1||rand==2){
returnVal+=1;
}
else if (rand==3||rand==4) {
returnVal-=1;
}
}
return returnVal;
}
我构建了一个测试函数，循环rand7() 10,000次，将所有返回值相加，然后除以10,000。如果rand7()工作正常，我们计算的平均值应该是4 -例如，(1+2+3+4+5+6+7 / 7)= 4。在做了多次测试后，平均值确实是4:)
下面是一个利用c++ 11特性的答案
#include <functional>
#include <iostream>
#include <ostream>
#include <random>
int main()
{
std::random_device rd;
unsigned long seed = rd();
std::cout << "seed = " << seed << std::endl;
std::mt19937 engine(seed);
std::uniform_int_distribution<> dist(1, 5);
auto rand5 = std::bind(dist, engine);
const int n = 20;
for (int i = 0; i != n; ++i)
{
std::cout << rand5() << " ";
}
std::cout << std::endl;
// Use a lambda expression to define rand7
auto rand7 = [&rand5]()->int
{
for (int result = 0; ; result = 0)
{
// Take advantage of the fact that
// 5**6 = 15625 = 15624 + 1 = 7 * (2232) + 1.
// So we only have to discard one out of every 15625 numbers generated.
// Generate a 6-digit number in base 5
for (int i = 0; i != 6; ++i)
{
result = 5 * result + (rand5() - 1);
}
// result is in the range [0, 15625)
if (result == 15625 - 1)
{
// Discard this number
continue;
}
// We now know that result is in the range [0, 15624), a range that can
// be divided evenly into 7 buckets guaranteeing uniformity
result /= 2232;
return 1 + result;
}
};
for (int i = 0; i != n; ++i)
{
std::cout << rand7() << " ";
}
std::cout << std::endl;
return 0;
}
我玩了一下，我为这个Rand(7)算法写了“测试环境”。例如，如果你想尝试哪种分布给你的算法，或者需要多少次迭代才能生成所有不同的随机值(对于Rand(7) 1-7)，你可以使用它。
我的核心算法是:
return (Rand5() + Rand5()) % 7 + 1;
和亚当·罗森菲尔德的分布一样均匀。(我将其包含在代码片段中)
private static int Rand7WithRand5()
{
//PUT YOU FAVOURITE ALGORITHM HERE//
//1. Stackoverflow winner
int i;
do
{
i = 5 * (Rand5() - 1) + Rand5(); // i is now uniformly random between 1 and 25
} while (i > 21);
// i is now uniformly random between 1 and 21
return i % 7 + 1;
//My 2 cents
//return (Rand5() + Rand5()) % 7 + 1;
}
这个“测试环境”可以采用任何Rand(n)算法并测试和评估它(分布和速度)。只需将代码放入“Rand7WithRand5”方法并运行代码片段。
一些观察:
亚当·罗森菲尔德(Adam Rosenfield)的算法并不比我的算法分布得更好。不管怎样，两种算法的分布都很糟糕。 本机Rand7(随机的。Next(1,8))完成，因为它在大约200+迭代中生成了给定间隔内的所有成员，Rand7WithRand5算法的顺序为10k(约30-70k) 真正的挑战不是编写从Rand(5)生成Rand(7)的方法，而是生成几乎均匀分布的值。
算法:
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;
}
}
}
