19

这是我最近参加的一次采访中提出的问题。

据我所知，两个数字之间的随机数可以生成如下

public static int rand(int low, int high) {
    return low + (int)(Math.random() * (high - low + 1));
}

但是在这里我使用 Math.random() 来生成一个介于 0 和 1 之间的随机数，并使用它来帮助我在低和高之间生成。有没有其他方法可以在不使用外部函数的情况下直接执行？

4

9 回答 9

42

典型的伪随机数生成器根据之前的数计算新数，因此理论上它们是完全确定的。通过提供良好的种子（随机数生成算法的初始化）来保证唯一的随机性。只要随机数不是非常安全关键（这将需要“真正的”随机数），这样的递归随机数生成器通常可以满足需求。

一旦提供了种子，就可以在没有任何“外部”函数的情况下表示递归生成。有几种算法可以解决这个问题。一个很好的例子是线性同余生成器。

伪代码实现可能如下所示：

long a = 25214903917;   // These Values for a and c are the actual values found
long c = 11;            // in the implementation of java.util.Random(), see link
long previous = 0;

void rseed(long seed) {
    previous = seed;
}

long rand() {
    long r = a * previous + c;
    // Note: typically, one chooses only a couple of bits of this value, see link
    previous = r;
    return r;
}

您仍然需要为这个生成器播种一些初始值。这可以通过执行以下操作之一来完成：

  • 使用像当前时间这样的东西（在大多数非安全关键的情况下，比如游戏）
  • 使用硬件噪声（有利于安全关键随机性）
  • 使用一个常数（有利于调试，因为你总是得到相同的序列）
  • 如果您不能使用任何函数并且不想使用常量种子，并且如果您使用的语言允许这样做，您还可以使用一些未初始化的内存。例如，在 C 和 C++ 中，定义一个新变量，不要给它赋值，而是使用它的值来为生成器播种。但请注意，这远非“好种子”，而只是满足您要求的黑客。永远不要在实际代码中使用它。

请注意，没有一种算法可以为具有相同输入的不同运行生成不同的值，而无需访问某些外部资源（如系统环境）。每个种子良好的随机数生成器都使用一些外部资源。

于 2013-02-23T07:26:42.257 回答
7

在这里，我建议一些带有评论的来源可能对您有帮助：

  • 系统时间 ：单调的一天差随机。快速，简单。
  • 鼠标点 ：随机但在独立系统上没有用。
  • 原始套接字/本地网络 （数据包的信息部分）：良好的随机技术和耗时 - 可以模拟攻击模式以减少随机性。
  • 一些带有排列的输入文本：快速，通用的方式并且也很好（在我看来）。
  • 由于键盘、磁盘驱动器和其他事件导致的中断时间： 常见方式 - 如果不小心使用，容易出错。
  • 另一种方法是输入模拟噪声信号：例如 temp。

  • /proc 文件数据：在 Linux 系统上。我觉得你应该使用这个。

    /proc/sys/kernel/random: 该目录包含控制文件操作的各种参数/dev/random。

    字符特殊文件/dev/random和/dev/urandom（从 开始出现Linux 1.3.30）为内核的随机数生成器提供了一个接口。

    试试这个逗号： 

    $cat /dev/urandom

    和 

    $cat /dev/random

    您可以编写一个从该文件读取的文件读取函数。

    阅读（也建议）：来自 /dev/urandom 的 rand 对于登录密钥是否安全？

`

于 2013-02-23T12:21:28.947 回答
5

System.currentTimeMillis()算不算外挂？你总是可以得到这个并通过一些最大值计算 mod：

int rand = (int)(System.currentTimeMillis()%high)+low;
于 2013-02-23T07:28:14.090 回答
2

从 和之间x = 4x(1-x)的“非理性”开始，您可以从逻辑图中获得接近随机性（实际上是混乱且绝对不均匀*）。x01

“随机性”的出现是因为浮点表示精度边缘的舍入误差。

(*)一旦你知道它在那里，你可以撤消倾斜。

于 2013-02-23T12:54:12.390 回答
1

您可以使用变量的地址或组合更多变量的地址来制作更复杂的...

于 2013-02-23T07:23:21.800 回答
0

您可以获得当前系统时间，但这也需要大多数语言的函数。

于 2013-02-23T07:26:15.847 回答
0

如果您被允许使用某些外部状态（例如，使用当前系统时间初始化的长），您可以在没有外部函数的情况下执行此操作。这足以让您实现一个简单的伪随机数生成器。

在对随机函数的每次调用中，您将使用状态来创建一个新的随机值，并更新状态，以便后续调用得到不同的结果。

您只需使用常规 Java 算术和/或按位运算即可完成此操作，因此不需要外部函数。

于 2013-02-23T07:30:18.253 回答
-2 
public class randomNumberGenerator {

    int generateRandomNumber(int min, int max) {
        return (int) ((System.currentTimeMillis() % max) + min);
    }

    public static void main(String[] args) {
        randomNumberGenerator rn = new randomNumberGenerator();
        int cv = 0;
        int min = 1, max = 4;
        Map<Integer, Integer> hmap = new HashMap<Integer, Integer>();

        int count = min;
        while (count <= max) {
            cv = rn.generateRandomNumber(min, max);
            if ((hmap.get(cv) == null) && cv >= min && cv <= max) {
                System.out.print(cv + ",");
                hmap.put(cv, 1);
                count++;
            }
        }

    }
}
于 2018-09-12T06:49:59.003 回答
-3

泊松随机发生器

假设我们从随机数的期望值“v”开始。然后说一个非负整数序列满足具有期望值 v 的泊松分布意味着在子序列上，该值的平均值（平均值）将出现“v”。泊松分布是统计数据的一部分，详细信息可以在维基百科上找到。但是这里使用这个函数的主要优点是： 1. 只生成整数值。2. 这些整数的平均值将等于我们最初提供的值。

它在小数值没有意义的应用程序中很有帮助。就像 1 分钟内到达机场的飞机数量是 2.5（没有意义），但这意味着 2 分钟内有 5 个计划到达。

int poissonRandom(double expectedValue) {
  int n = 0; //counter of iteration
  double limit; 
  double x;  //pseudo random number
  limit = exp(-expectedValue);
  x = rand() / INT_MAX; 
  while (x > limit) {
    n++;
    x *= rand() / INT_MAX;
  }
  return n;
}

线

rand() / INT_MAX

应该生成一个介于 0 和 1 之间的随机数。所以我们可以使用系统的时间。秒 / 60 将达到目的。我们应该使用哪个功能完全取决于应用程序。

于 2013-03-11T03:00:41.590 回答