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

Question

在最近的一次采访中,我被问到以下问题:

使用给定getrnd50()方法打印1-100中的随机数,该方法生成1-50的随机数.每个随机数应仅以随机顺序打印一次.不允许使用其他随机数生成器,我不允许更改其定义 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次.在最坏的情况下,它将是无限的,平均情况下数万.他要求我优化代码,以便显着改善平均情况.

当我表示无法做到时,他给了我一个暗示,他说:

考虑生成新数字时生成的数字的数量.对于前者 如果count变成99我不必打电话getrnd50()我可以简单地找到剩余的数字并打印出来.

虽然我理解他的漂移我不知道它会如何帮助我,所以显然我被拒绝了.现在我很想知道答案.帮我!Thanx提前!

注意:如果有人懒得写一个冗长的代码只是指出数字生成部分,其余的很容易.此外,我们不一定遵循提示.

Answer 1

关键是不检查你之前是否已经生成了这个数字,当只查找剩余数字时会变得非常昂贵,但要按顺序生成数字1-100,然后进行随机播放.

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

相反,如果您只是随机播放一个数组,您只需要拥有与随机数一样多的随机数,并且只需要与您需要数字输出一样多的随机操作.

(有关改组的详细信息,请查看Fisher-Yates shuffle,特别是可以生成洗牌阵列的内向外变体)

要生成随机数,您需要一个变量生成器,而不是固定的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倍,这是原始版本的最佳情况.如果随机生成是真正随机的,那么仍然是无穷大的最坏情况,但随机生成通常不会那样工作.如果确实如此,我不确定在给定约束的情况下,未经证实的结果是否真实.

为了说明,由于结果很微妙,这里是我建议的随机例程与模数版本的关系图:

总而言之,我认为虽然你的随机生成效率有点低,并且可以得到改善,但是面试官正在寻找的真正大赢家,首先不需要这么多随机数,通过洗牌而不是以不断下降的概率重复搜索.

Answer 2

由于 100 / 50 是一个整数，所以这很容易。由于 50 / (100 / 50) 是一个整数，所以更容易。

如果您不太明白，这里有一些示例代码：

int rnd1 = getrnd50();
int rnd2 = getrnd50();
if (rnd1 % 2 == 0)
{
    rnd2 += 50;
}
return rnd2;

这是一个大纲：

• 在 1 到 50 之间随机选择的两个数字，称为a和b。
• 如果a是偶数，则b加 50 。
• 返回b .

如果您愿意，您可以将其设为单行：

return getrnd50() + getrnd50() % 2 * 50;

但这有点太混乱了。

编辑：我发现问题实际上是要求一个经过排序的列表，而不是随机整数序列。

这可以通过创建一个从 1 到 100 的列表并进行 100 次随机交换来完成，就像 Fisher-Yates 洗牌一样。我想象，使用 Fisher-Yates 洗牌，绝对最小调用次数是 93（用公式 给出ceil(log50(100!))），但使用更简单的算法，您可以使用 200。

简单的算法涉及将 100 个元素中的每一个与 100 个元素中的一个随机元素进行交换。要选择的数字将使用上述生成器从 1 到 100 生成。

例如：

for (int i = 0; i < 100; i++)
{
    swap(i, getrnd100() - 1); // - 1 for zero base!
}

这是一些完整的代码：

int[] result = new int[100];
for (int i = 0; i < 100; i++)
{
    result[i] = i + 1;
}
for (int i = 0; i < 100; i++)
{
    int j = (getrnd50() + getrnd50() % 2 * 50) - 1;
    int tmp = result[i];
    result[i] = result[j];
    result[j] = tmp;
}
return result;

（免责声明：我不懂Java，也没有测试过。）

最好情况 200，最差情况 200，平均情况 200。