给定一个函数,它产生的是1到5之间的随机整数,写一个函数,它产生的是1到7之间的随机整数。
当前回答
以下是我的发现:
Random5产生1~5的范围,随机分布 如果我们运行3次并将它们加在一起,我们将得到3~15个随机分布的范围 在3~15范围内执行算术 (3~15) - 1 = (2~14) (2~14)/2 = (1~7)
然后我们得到1~7的范围,这是我们正在寻找的Random7。
其他回答
Here is a solution that tries to minimize the number of calls to rand5() while keeping the implementation simple and efficient; in particular, it does not require arbitrary large integers unlike Adam Rosenfield’s second answer. It exploits the fact that 23/19 = 1.21052... is a good rational approximation to log(7)/log(5) = 1.20906..., thus we can generate 19 random elements of {1,...,7} out of 23 random elements of {1,...,5} by rejection sampling with only a small rejection probability. On average, the algorithm below takes about 1.266 calls to rand5() for each call to rand7(). If the distribution of rand5() is uniform, so is rand7().
uint_fast64_t pool;
int capacity = 0;
void new_batch (void)
{
uint_fast64_t r;
int i;
do {
r = 0;
for (i = 0; i < 23; i++)
r = 5 * r + (rand5() - 1);
} while (r >= 11398895185373143ULL); /* 7**19, a bit less than 5**23 */
pool = r;
capacity = 19;
}
int rand7 (void)
{
int r;
if (capacity == 0)
new_batch();
r = pool % 7;
pool /= 7;
capacity--;
return r + 1;
}
def rand5():
return random.randint(1,5) #return random integers from 1 to 5
def rand7():
rand = rand5()+rand5()-1
if rand > 7: #if numbers > 7, call rand7() again
return rand7()
print rand%7 + 1
我想这将是最简单的解决方案,但到处都有人建议5*rand5() + rand5() - 5,如http://www.geeksforgeeks.org/generate-integer-from-1-to-7-with-equal-probability/。 有人能解释一下rand5()+rand5()-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
与Martin的答案相似,但却很少抛弃熵:
int rand7(void) {
static int m = 1;
static int r = 0;
for (;;) {
while (m <= INT_MAX / 5) {
r = r + m * (rand5() - 1);
m = m * 5;
}
int q = m / 7;
if (r < q * 7) {
int i = r % 7;
r = r / 7;
m = q;
return i + 1;
}
r = r - q * 7;
m = m - q * 7;
}
}
在这里,我们在0到m-1之间建立一个随机值,并尝试通过添加尽可能多的状态来最大化m,而不会溢出(INT_MAX是C中适合int的最大值,或者您可以将其替换为任何在您的语言和体系结构中有意义的大值)。
然后;如果r落在能被7整除的最大可能区间内,那么它包含一个可行的结果,我们可以将这个区间除以7,取余数作为我们的结果,并将剩余的值返回到熵池。否则r在另一个不均匀的区间内我们就必须抛弃这个不拟合区间重新启动熵池。
与这里的流行答案相比,它调用rand5()的频率平均减少了一半。
为了提高性能,可以将除法分解为琐碎的比特旋转和lut。
int rand7()
{
return ( rand5() + (rand5()%3) );
}
rand5() -返回1-5之间的值 rand5()%3 -返回0-2之间的值 所以,当加起来时,总价值将在1-7之间