19

これは、私が最近参加したインタビューの 1 つで聞かれた質問でした。

私の知る限り、2つの数値間の乱数は次のように生成できます

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

しかし、ここでは Math.random() を使用して 0 から 1 の間の乱数を生成し、それを使用して低から高の間で生成しています。外部関数を使用せずに直接できる他の方法はありますか?

4

9 に答える 9

42

典型的な擬似乱数ジェネレーターは、以前の数値に基づいて新しい数値を計算するため、理論的には完全に決定論的です。適切なシード (乱数生成アルゴリズムの初期化) を提供することによって、唯一のランダム性が保証されます。乱数がセキュリティ上それほど重要でない限り (これには「実際の」乱数が必要です)、このような再帰的な乱数ジェネレーターは多くの場合、ニーズを満たします。

再帰的生成は、シードが提供されると、「外部」関数なしで表現できます。この問題を解決するアルゴリズムがいくつかあります。良い例はLinear Congruential Generatorです。

疑似コードの実装は次のようになります。

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

ここで私はコメント付きのいくつかの情報源があなたが役立つと思うかもしれないことを提案しています：

  • システム時間 ：1日で単調でランダムではありません。速くて簡単。
  • マウスポイント ：ランダムですが、スタンドアロンシステムでは役に立ちません。
  • Raw Socket / Local Network （Packet's info-part）：優れたランダム技術的で時間がかかる-ランダム性を減らすために攻撃モードをモデル化することが可能です。
  • 順列のある入力テキスト：高速、一般的な方法、そして良い（私の意見では）。
  • キーボード、ディスクドライブ、およびその他のイベントによる割り込みのタイミング： 一般的な方法–注意深く使用しないとエラーが発生しやすくなります。
  • 別のアプローチは、アナログノイズ信号を供給することです：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からのランドはログインキーに対して安全ですか？

`

于 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 に答える
-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 に答える