根据一系列硬币翻转生成0到9之间的随机数

Question

根据一系列硬币翻转生成0到9之间的随机数

mathrandom

4

我应该使用什么方法来最小化抛硬币的数量，以生成从0到9的均匀分布数字？

我做了一些研究，但是我还没有能够解决如何适应这个具体问题的方法：

- TheHappyBukkit

平均数最小化还是上限最小化？ - Joachim Isaksson

@JoachimIsaksson 我想的是翻转的平均次数。 - TheHappyBukkit

那么最有效的变体是使用10次翻转来生成一个小于1024的二进制数，拒绝大于999的结果，并将3个数字作为该范围内的3个随机数。这应该很难且不切实际去改进它。 - Lutz Lehmann

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Sendhilkumar Alalasundaram · Accepted Answer

你需要至少翻转硬币10次以获得至少10种可能的组合。如果将硬币翻转4次，我们将有16种排列方式。因此，所需最小翻转次数为4。

通过参考您提到的参考资料中提到的算法，我们可以按照以下方式实现该问题。

变量randNum返回0-9之间均匀分布的随机数。

函数rand2通过将T和H分配为0和1或反之来模拟抛硬币的过程。

int[][][][] fourDimArr = { { { {1, 2},{3, 4} }, {{5, 6} ,{7, 8} } }, { { {9,10},{0,0} }, { {0,0},{0,0} } } };
int result = 0;
    while (result == 0)
    {
        int i = rand2();
        int j = rand2();
        int k = rand2();
        int l = rand2();
        result = fourDimArr[i][j][k][l];
    }
int randNum = result-1;

下面的评论中，James K Polk 提出了一种更简单和更直观的实现方法。它涉及使用硬币翻转的结果作为四位数字的位。

通过拒绝大于等于10的值，我们可以生成一个0-9之间均匀分布的随机数。有关实现，请参考下面的代码片段。

int result = 11;
        while(result>=10){
            result = 0;
            for(int j = 0; j < 4; j++){
                result = (result<<1)|rand2();
            }
        }
randNum = result;

rand2的一个示例实现如下：

private static int rand2() {
    if(Math.random()>0.5)return 1;
    return 0;
}

注意：最少需要翻转4次。在最坏情况下，需要的翻转次数仍然是无限的，但这种情况永远不会出现。