1.4.45

1.4.45 #

解答 #

建立一个布尔数组，将每次随机出来的数作为下标，将相应位置的布尔值改为 true，每次随机都检查一遍这个数组是否都是 true。

代码 #

// HN 指的是调和级数
var random = new Random();
var n = 10000;
var a = new bool[n];
var randomSize = 0;
int times;
for (times = 0; times < 20; times++)
{
    for (var i = 0; i < n; i++)
    {
        a[i] = false;
    }

    for (var i = 0; true; i++)
    {
        var now = random.Next(n);
        a[now] = true;
        if (IsAllGenerated(a))
        {
            randomSize += i;
            Console.WriteLine($"生成{i}次后所有可能均出现过了");
            break;
        }
    }
}

Console.WriteLine($"NHN={n * HarmonicSum(n)}，平均生成{randomSize / times}个数字后所有可能都出现");

// 计算 N 阶调和级数的和。
static double HarmonicSum(int n)
{
    double sum = 0;
    for (var i = 1; i <= n; i++)
    {
        sum += 1.0 / i;
    }

    return sum;
}

// 检查所有数字是否都生成过了。
static bool IsAllGenerated(bool[] a)
{
    foreach (var i in a)
    {
        if (!i)
            return false;
    }

    return true;
}