给定一个函数,它产生的是1到5之间的随机整数,写一个函数,它产生的是1到7之间的随机整数。
当前回答
以下是我的回答:
static struct rand_buffer {
unsigned v, count;
} buf2, buf3;
void push (struct rand_buffer *buf, unsigned n, unsigned v)
{
buf->v = buf->v * n + v;
++buf->count;
}
#define PUSH(n, v) push (&buf##n, n, v)
int rand16 (void)
{
int v = buf2.v & 0xf;
buf2.v >>= 4;
buf2.count -= 4;
return v;
}
int rand9 (void)
{
int v = buf3.v % 9;
buf3.v /= 9;
buf3.count -= 2;
return v;
}
int rand7 (void)
{
if (buf3.count >= 2) {
int v = rand9 ();
if (v < 7)
return v % 7 + 1;
PUSH (2, v - 7);
}
for (;;) {
if (buf2.count >= 4) {
int v = rand16 ();
if (v < 14) {
PUSH (2, v / 7);
return v % 7 + 1;
}
PUSH (2, v - 14);
}
// Get a number between 0 & 25
int v = 5 * (rand5 () - 1) + rand5 () - 1;
if (v < 21) {
PUSH (3, v / 7);
return v % 7 + 1;
}
v -= 21;
PUSH (2, v & 1);
PUSH (2, v >> 1);
}
}
它比其他的稍微复杂一点,但我相信它最小化了对rand5的调用。与其他解决方案一样,它有小概率会循环很长时间。
其他回答
与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。
你需要的函数是rand1_7(),我写了rand1_5(),这样你就可以测试它并绘制它。
import numpy
def rand1_5():
return numpy.random.randint(5)+1
def rand1_7():
q = 0
for i in xrange(7): q+= rand1_5()
return q%7 + 1
package CareerCup;
public class RangeTransform {
static int counter = (int)(Math.random() * 5 + 1);
private int func() {
return (int) (Math.random() * 5 + 1);
}
private int getMultiplier() {
return counter % 5 + 1;
}
public int rangeTransform() {
counter++;
int count = getMultiplier();
int mult = func() + 5 * count;
System.out.println("Mult is : " + 5 * count);
return (mult) % 7 + 1;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
RangeTransform rangeTransform = new RangeTransform();
for (int i = 0; i < 35; i++)
System.out.println("Val is : " + rangeTransform.rangeTransform());
}
}
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();
?>
因为1/7是一个以5为底的无限小数,所以没有(完全正确的)解可以在常数时间内运行。一个简单的解决方案是使用拒绝抽样,例如:
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; // result is now uniformly random between 1 and 7
这个循环的预期运行时间为25/21 = 1.19次迭代,但是永远循环的概率非常小。