什么是简单的解决方案?(rand5() + rand5()) % 7 + 1 减少内存使用或在较慢的CPU上运行的有效解决方案是什么?是的，这是有效的，因为它只调用rand5()两次，空间复杂度为O(1)

考虑rand5()给出从1到5(包括)的随机数。 (1 + 1) % 7 + 1 = 3 (1 + 2) % 7 + 1 = 4 (1 + 3) % 7 + 1 = 5 (1 + 4) % 7 + 1 = 6 (1 + 5) % 7 + 1 = 7

(2 + 1) % 7 + 1 = 4 (2 + 2) % 7 + 1 = 5 (2 + 3) % 7 + 1 = 6 (2 + 4) % 7 + 1 = 7 (2 + 5) % 7 + 1 = 1 .

(5 + 1) % 7 + 1 = 7 (5 + 2) % 7 + 1 = 1 (5 + 3) % 7 + 1 = 2 (5 + 4) % 7 + 1 = 3 (5 + 5) % 7 + 1 = 4 .

等等

我想我有四个答案，两个给出了像@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次试验中，有两个数字会少出现一次。在大多数情况下，我可以接受。

int rand7()
{
    int zero_one_or_two = ( rand5() + rand5() - 1 ) % 3 ;
    return rand5() + zero_one_or_two ;
}

就是这样，均匀分布，零rand5调用。

def rand7:
    seed += 1
    if seed >= 7:
        seed = 0
    yield seed

需要事先播种。

这里是我的一般实现，在给定一个范围为[0,B-1]的均匀发生器的情况下，生成范围为[0,N-1]的均匀。

public class RandomUnif {

    public static final int BASE_NUMBER = 5;

    private static Random rand = new Random();

    /** given generator, returns uniform integer in the range 0.. BASE_NUMBER-1
    public static int randomBASE() {
        return rand.nextInt(BASE_NUMBER);
    }

    /** returns uniform integer in the range 0..n-1 using randomBASE() */
    public static int randomUnif(int n) {
        int rand, factor;
        if( n <= 1 ) return 0;
        else if( n == BASE_NUMBER ) return randomBASE();
        if( n < BASE_NUMBER ) {
            factor = BASE_NUMBER / n;
            do
                rand = randomBASE() / factor;
            while(rand >= n);
            return rand;
        } else {
            factor = (n - 1) / BASE_NUMBER + 1;
            do {
                rand = factor * randomBASE() + randomUnif(factor);
            } while(rand >= n);
            return rand;
        }
    }
}

不是特别高效，但一般和紧凑。对基生成器的均值调用:

 n  calls
 2  1.250 
 3  1.644 
 4  1.252 
 5  1.000 
 6  3.763 
 7  3.185 
 8  2.821 
 9  2.495 
10  2.250 
11  3.646 
12  3.316 
13  3.060 
14  2.853 
15  2.650 
16  2.814 
17  2.644 
18  2.502 
19  2.361 
20  2.248 
21  2.382 
22  2.277 
23  2.175 
24  2.082 
25  2.000 
26  5.472 
27  5.280 
28  5.119 
29  4.899 

int rand7()
{
    return ( rand5() + (rand5()%3) );
}

rand5() -返回1-5之间的值 rand5()%3 -返回0-2之间的值 所以，当加起来时，总价值将在1-7之间