java - 从 1-50 的生成器生成 1-100 的随机数

Question

在最近的一次采访中，有人问我以下问题:

Print random numbers from 1-100 using the given getrnd50() method which generates the random numbers from 1-50. Each random number should be printed only once and in random order. Use of no other random number generator is allowed and i was not allowed to change the definition of getrnd50().

我想出了下面的代码，它给出了正确的输出。

import java.util.Random;

public class Test {

public static void main(String[] args) {
    int[] rs = new int[100];
    int count = 0;
    int k;
    while (count != 100) {

        // I decided to simply multiply the result of `getrnd50()` by 2. 
        // But since that would generate only even numbers,

        k = getrnd50() * 2;

        // I decided to randomly subtract 1 from the numbers. 
        // Which i accomlished as follows.          

        if (getrnd50() <= 25) // 25 is to half the possibilities.
            k--;

        // Every number is to be stored in its own unique location 
        // in the array `rs`, the location is `(number-1)`. 
        // Every time a number is generated it is checked whether it has 
        // already been generated. If not, it is saved in its position, printed and 
        // `count` is incremented.

        if (rs[k-1] == 0) {
            rs[k-1] = k;
            count++;
            System.out.print(k + " ");
        }
    }
}
// This is the method and i am not supposed to touch it.
static int getrnd50() {
    Random rand = new Random();
    return (1 + rand.nextInt(50));
}

}

虽然它在那一轮被接受，但在下一轮面试官告诉我 getrnd50() 是一种昂贵的方法，即使在最好的情况下我也必须为每个生成的数字调用它两次.即 1-100 为 200 次。在最坏的情况下，它将是无穷大，在平均情况下将是数万。他让我优化代码以显着改善平均情况。

当我表示自己做不到的时候，他给了我一个提示，他说:

To consider the number of numbers generated while generating a new number. For ex. if count becomes 99 i don't have to call getrnd50() I can simply find the remaining number and print it.

虽然我理解他的想法，但我不知道这对我有什么帮助，所以很明显我被拒绝了。现在我很想知道答案。帮我!提前致谢!

注意:如果有人懒得写冗长的代码，只需指出数字生成部分，剩下的就很简单了。我们也不一定要听从提示。

Answer 1

关键是不要检查你之前是否生成过号码，这在只查找剩余号码时会非常昂贵，而是按顺序生成号码 1-100，然后洗牌。

在您的代码中，当您生成 100 个数字中的 99 个时，您将循环生成随机数，直到找到剩余的 1 个数字。这就是为什么您的版本中的平均情况如此糟糕。

如果相反，您只是打乱一个数组，则您只需要拥有与打乱操作一样多的随机数，并且只需要与需要数字输出一样多的打乱操作。

(有关洗牌的完整详细信息，请查看 Fisher-Yates 洗牌，特别是可以就地生成洗牌数组的由内而外变体)

要生成随机数，您需要一个变量生成器，而不是一个固定的 1-50 生成器。您可以通过多种方式解决这个问题，但如果您真的希望输出在可能的状态之间具有良好的分布，请务必小心将偏斜引入结果。

例如，我会建议使用整数位并进行移位，而不是尝试使用模数。如果值超出所需范围，这确实涉及一定数量的循环，但无法修改原始随机数生成，您的手有些束缚。

static int bits = 0;
static int r100 = 0;

static int randomInt(int range)
{
    int ret;

    int bitsneeded = 32 - Integer.numberOfLeadingZeros(range - 1);

    do {
            while(bits < bitsneeded)
            {
                    int r = (getrnd50()-1) * 50 + getrnd50()-1;
                    if(r < 2048)
                    {
                            r100 <<= 11;
                            r100 |= r;
                            bits += 11;
                    }
            }
            ret = r100 & ((1 << bitsneeded) - 1);
            bits -= bitsneeded;
            r100 >>=  bitsneeded;
    } while(ret >= range); 

        return ret + 1;
}

这个实现将使用 150 个随机数区域中的一些东西来作为 100 值随机排列的数组。这比模数版本差，但好于输入范围的 2 倍，这是原始版本的最佳情况。如果随机生成真的是随机的，那么最坏的情况仍然是无穷大，但随机生成通常不会那样工作。如果是这样，考虑到限制条件，我不确定未偏斜的结果是否现实。

为了说明，由于结果很微妙，下面是我建议的随机例程与模数版本的图表:

所以总而言之，我认为虽然你的随机生成效率有点低，并且可以改进，但面试官想要的真正大的胜利是首先不需要那么多随机数，通过做一个以不断降低的概率随机而不是重复搜索。