给定一个函数,它产生的是1到5之间的随机整数,写一个函数,它产生的是1到7之间的随机整数。
当前回答
我想我有四个答案,两个给出了像@Adam Rosenfield那样的精确解决方案,但没有无限循环问题,另外两个几乎完美的解决方案,但执行速度比第一个更快。
最好的精确解决方案需要7次调用rand5,但为了理解,让我们继续。
方法一:精确
Adam的答案的优点在于它给出了一个完美的均匀分布,并且只需要两次调用rand5()的概率非常高(21/25)。然而,最坏的情况是无限循环。
下面的第一个解决方案也给出了一个完美的均匀分布,但总共需要对rand5进行42次调用。没有无限循环。
下面是一个R的实现:
rand5 <- function() sample(1:5,1)
rand7 <- function() (sum(sapply(0:6, function(i) i + rand5() + rand5()*2 + rand5()*3 + rand5()*4 + rand5()*5 + rand5()*6)) %% 7) + 1
对于不熟悉R的人,这里是一个简化版本:
rand7 = function(){
r = 0
for(i in 0:6){
r = r + i + rand5() + rand5()*2 + rand5()*3 + rand5()*4 + rand5()*5 + rand5()*6
}
return r %% 7 + 1
}
rand5的分布将被保留。如果我们计算一下,循环的7次迭代中的每一次都有5^6个可能的组合,因此可能组合的总数为(7 * 5^6)%% 7 = 0。因此,我们可以将生成的随机数分成7个相等的组。有关这方面的更多讨论,请参见方法二。
以下是所有可能的组合:
table(apply(expand.grid(c(outer(1:5,0:6,"+")),(1:5)*2,(1:5)*3,(1:5)*4,(1:5)*5,(1:5)*6),1,sum) %% 7 + 1)
1 2 3 4 5 6 7
15625 15625 15625 15625 15625 15625 15625
我认为这很容易证明亚当的方法运行得快得多。在Adam的解中有42次或更多的rand5调用的概率非常小((4/25)^21 ~ 10^(-17))。
方法2 -不精确
现在是第二个方法,它几乎是统一的,但需要6次调用rand5:
rand7 <- function() (sum(sapply(1:6,function(i) i*rand5())) %% 7) + 1
以下是一个简化版本:
rand7 = function(){
r = 0
for(i in 1:6){
r = r + i*rand5()
}
return r %% 7 + 1
}
这实际上是方法1的一次迭代。如果我们生成所有可能的组合,结果计数如下:
table(apply(expand.grid(1:5,(1:5)*2,(1:5)*3,(1:5)*4,(1:5)*5,(1:5)*6),1,sum) %% 7 + 1)
1 2 3 4 5 6 7
2233 2232 2232 2232 2232 2232 2232
一个数字将在5^6 = 15625次试验中再次出现。
现在,在方法1中,通过将1加到6,我们将数字2233移动到每个连续的点上。因此,组合的总数将匹配。这是可行的,因为5^ 6% % 7 = 1,然后我们做了7个适当的变化,所以(7 * 5^ 6% % 7 = 0)。
方法三:精确
如果理解了方法1和2的参数,接下来就是方法3,它只需要7次调用rand5。在这一点上,我觉得这是精确解决方案所需的最少调用数。
下面是一个R的实现:
rand5 <- function() sample(1:5,1)
rand7 <- function() (sum(sapply(1:7, function(i) i * rand5())) %% 7) + 1
对于不熟悉R的人,这里是一个简化版本:
rand7 = function(){
r = 0
for(i in 1:7){
r = r + i * rand5()
}
return r %% 7 + 1
}
rand5的分布将被保留。如果我们计算一下,循环的7次迭代中的每一次都有5个可能的结果,因此可能组合的总数为(7 * 5)%% 7 = 0。因此,我们可以将生成的随机数分成7个相等的组。有关这方面的更多讨论,请参见方法一和方法二。
以下是所有可能的组合:
table(apply(expand.grid(0:6,(1:5)),1,sum) %% 7 + 1)
1 2 3 4 5 6 7
5 5 5 5 5 5 5
我认为这很直接地证明了亚当的方法仍然运行得更快。在Adam的解中有7次或更多的rand5调用的概率仍然很小((4/25)^3 ~ 0.004)。
方法4 -不精确
这是第二种方法的一个小变化。它几乎是统一的,但需要7次调用rand5,这是一个额外的方法2:
rand7 <- function() (rand5() + sum(sapply(1:6,function(i) i*rand5())) %% 7) + 1
以下是一个简化版本:
rand7 = function(){
r = 0
for(i in 1:6){
r = r + i*rand5()
}
return (r+rand5()) %% 7 + 1
}
如果我们生成所有可能的组合,结果计数如下:
table(apply(expand.grid(1:5,(1:5)*2,(1:5)*3,(1:5)*4,(1:5)*5,(1:5)*6,1:5),1,sum) %% 7 + 1)
1 2 3 4 5 6 7
11160 11161 11161 11161 11161 11161 11160
在5^7 = 78125次试验中,有两个数字会少出现一次。在大多数情况下,我可以接受。
其他回答
算法:
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;
}
}
}
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]
这类似于@RobMcAfee,除了我使用魔术数字而不是2维数组。
int rand7() {
int m = 1203068;
int r = (m >> (rand5() - 1) * 5 + rand5() - 1) & 7;
return (r > 0) ? r : rand7();
}
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();
?>
为什么不简单一点呢?
int random7() {
return random5() + (random5() % 3);
}
由于取模,在这个解中得到1和7的几率较低,然而,如果你只是想要一个快速和可读的解,这是一种方法。