给定一个函数,它产生的是1到5之间的随机整数,写一个函数,它产生的是1到7之间的随机整数。
当前回答
假设rand给予所有位相同的权重,然后用上界进行掩码。
int i = rand(5) ^ (rand(5) & 2);
Rand(5)只能返回:1b, 10b, 11b, 100b, 101b。有时候你只需要考虑设置2位。
其他回答
int rand7()
{
int zero_one_or_two = ( rand5() + rand5() - 1 ) % 3 ;
return rand5() + zero_one_or_two ;
}
PHP解决方案
<?php
function random_5(){
return rand(1,5);
}
function random_7(){
$total = 0;
for($i=0;$i<7;$i++){
$total += random_5();
}
return ($total%7)+1;
}
echo random_7();
?>
function rand7() {
while (true) { //lowest base 5 random number > 7 reduces memory
int num = (rand5()-1)*5 + rand5()-1;
if (num < 21) // improves performance
return 1 + num%7;
}
}
Python代码:
from random import randint
def rand7():
while(True):
num = (randint(1, 5)-1)*5 + randint(1, 5)-1
if num < 21:
return 1 + num%7
100000次运行的测试分布:
>>> rnums = []
>>> for _ in range(100000):
rnums.append(rand7())
>>> {n:rnums.count(n) for n in set(rnums)}
{1: 15648, 2: 15741, 3: 15681, 4: 15847, 5: 15642, 6: 15806, 7: 15635}
int getOneToSeven(){
int added = 0;
for(int i = 1; i<=7; i++){
added += getOneToFive();
}
return (added)%7+1;
}
亚当·罗森菲尔德正确答案的前提是:
X = 5^n(在他的例子中,n=2) 操作n个rand5次调用以获得范围[1,x]内的数字y Z = ((int)(x / 7)) * 7 如果y > z,再试一次。否则返回y % 7 + 1
当n = 2时,有4种可能:y ={22,23,24,25}。如果你使用n = 6,你只有1个扔掉的东西:y ={15625}。
5^6 is 15625 7 times 2232 is 15624
你又给rand5个电话。但是,您获得一个丢弃值(或无限循环)的机会要低得多。如果有办法让y没有可能的一次性值,我还没有找到它。