0

我想用 Java 编写一个程序，生成 1 到 100 万之间的数字，不应该重复任何数字，也不应该错过任何人。我不知道从哪里开始。我不能记录我用过的所有数字，那是不切实际的。我该怎么做呢？

4

5 回答 5

2

所以你需要：

  • 输出数字 1 - 1,000,000（含）
  • 以随机顺序
  • 没有重复或重复
  • 不跟踪您输出了哪些数字

这是那些令人沮丧的问题之一，答案是：你不能那样做。

所以我将挑战这个问题的基础：一百万个数字，每个字节 8 位，即 122k 来存储数字的位标志。除非您在微控制器中运行，否则这应该不是问题。因此，即使在相当受限的环境中，您也应该能够执行NPE 建议的操作。

但除非你能存储这些数字，否则你就无法做到这一点。

（将其设为 CW 是因为我只是在总结社区在评论中所说的话，并且因为除了“你不能那样做”之外，它只是在说“看看 NPE 的答案”。）

于 2012-11-28T11:21:32.463 回答
2

一种方法是使用伪随机游走。一个简单的伪随机游走使用任何大素数（以确保它与极限没有公因数）和模数来包装该值，以便在重复之前获取所有 N 个值。

这是一个较小的示例，使用 100 作为极限，47 作为素数。您可以将其更改为使用 1000000 作为限制和更大的素数，如 513239

int last = 0;
for (int i = 0; i < 100; i++) {
    last = (last + 47) % 100;
    System.out.println(last + 1);
}

印刷

48 95 42 89 36 83 30 77 24 71 18 65 12 59 6 53 100 47 94 41 88 35 82 29 76 23 70 17 64 11 58 5 52 99 46 93 40 87 34 4 81 28 6 75 2 0 4 71 28 6 75 2 98 45 92 39 86 33 80 27 74 21 68 15 62 9 56 3 50 97 44 91 38 85 32 79 26 73 20 67 14 61 8 55 2 49 96 43 90 37 84 31 4 68 25 6 72 1

为了使这看起来更随机，您可以使用两个伪随机游走的组合。

于 2012-11-28T12:26:33.113 回答
2

将 1 到 1,000,000 的整数存储在数组列表中。随机打乱列表并打印出其内容。

于 2012-11-28T11:11:59.220 回答
1

取决于您所说的“随机”是什么意思。您可以执行一些操作，例如生成 1 到 100 之间的随机数，然后说生成的随机数是否为 52 打印当前数字 + 52，然后打印当前数字 + 52 之间的所有数字并继续重复直到达到 100 万。

于 2012-11-28T11:26:03.100 回答
0

好的，这就是您的请求的问题。

根据我读到的内容，您似乎想要获得一个 O(1)，您只需执行 1,000,000 次循环。现在，通过一个非常好的随机数来做到这一点的唯一方法是返回并从大小为 1,000,000 的数组中引用它。当您打印出一个时，您只需将该特定点设置为 1，除非该点已经是 1 或类似的东西。但是从您所说的来看，您不想保留记录，这现在会使您的随机性变得可怕，甚至几乎不是随机的

看看真的没有什么真正随机的。总是有一种模式，但使用某些数学运算，您可以创建一个非常难以识别的模式。

您必须使用的随机数的问题在于，它只能在打印 1,000,000 次后才能自我重复。

这可以这样做：

Example randomizing 20 numbers

1 3 5 7 9 11 13 15 17 19 2 4 6 8 10 12 14 16 18 20

Now all that is, is num = (num + 2) % 20

现在当然你可以使差异更大，但情况是一样的。这可能看起来很像哈希映射的工作方式。但主要是我想指出如何通过保存记录并以 O(1) 打印来完成此操作，但它根本不是一个好的随机数。

于 2012-11-28T12:16:11.893 回答