乱数生成問題のまとめ

乱数は多くのプログラムで使用され、最も一般的な乱数を生成する方法はcの標準関数ライブラリが提供する乱数生成器rand(stdlib.hで定義)であり、0-RAND_を返すことができる.MAX間に均等に分布する擬似ランダム整数(RAND_MAXは少なくとも32767であり、一般的には32767がデフォルトである).rand()を直接呼び出すと、生成された乱数が実行されるたびに同じになります.これはrand()が擬似乱数を生成する際にシード(シードのデフォルト値は1)を必要とし、擬似乱数を計算する初期値としてシードが同じであれば生成された乱数も同じになるからです.この特徴は暗号化と復号化に使用されるソフトウェアがある.暗号化時、あるシード数を用いて擬似ランダムシーケンスを生成してデータを処理する.復号時には,同じシードを再利用して同じランダムシーケンスで暗号化データを復元する.このように、種を知らない人が解読するにはもっと手間がかかります.
もちろん、このような完全に同じ擬似ランダムシーケンスは、私たちのプログラムにとって非常に悪いです.この問題を解決するには、ランダムシーケンスが生成されるたびに、異なるシード値を指定する必要があります.srand()関数はrand()が擬似乱数を生成するときのシードを設定するために使用されます.この2つの関数の作業手順は次のとおりです.
1)まずsrand()に0~65535の値範囲をとるunsigned intタイプの種子を提供する.2)次にrand()が呼び出され、srand()に与えられたシード値に基づいてランダム数(0から32767の間)3が返され、必要に応じてrand()が複数回呼び出され、新しいランダム数が間欠的に得られる.4)いつでもsrand()に新しいシードを提供し,rand()の出力結果をさらに「ランダム化」することができる.
シード値は人為的に指定できますが、最も一般的な方法はシステム時間を使用して最もシードされ、具体的な方法は

        srand((unsigned int)time(NULL));
        rand();

time()(time.hで定義)現在のシステム時間を取得し、time_を返します.t型の大きな整数で、1970年1月1日を表す
00:00:00から現在時刻までの秒数.
       
複数の乱数を生成する必要がある場合は、srand()をループの外に配置します.そうしないと、乱数が発生するたびにsrand()が呼び出されます.コンピュータの動作速度が速すぎて、time値が同じになります.
 
******************************************************************************************************
こうして生成されるのは0~RAND_MAX間のランダム整数ですが、多くの場合、ある範囲(例えばx~y)間のランダム数が必要です.一般的な方法は2つあります.
        

           ：(int)((double)rand()/(double)RAND_MAX*(y-x))+x
           ：rand()%(y-x)+x

その中の方法の1つはx~y間の数値を得る確率をより均一にすることができるが、浮動小数点演算であるため複雑性が高い.メソッド2の演算はより高速ですが、前RAND_MAX%(y-x)個数の確率はやや大きい.またrand()を直接呼び出す場合,精度に対する要求はあまり高くないことを考慮して,通常第2の方法が用いられる.(自分で乱数生成器を作る必要がある場合は、線形同余法が一般的で、『コンピュータプログラム設計芸術』(第2巻)を参照してください.自分はまだ见たことがないので、机会を见てみましょう.
*****************************************************************************************************
乱数を生成する問題については,「繰り返さない乱数を生成する」ことがよくある(『プログラミング珠玉』第1章問題3参照).この問題に対して、関連資料を探した後、3つの構想をまとめた:1つ目は、ランダム数が発生するたびに、前の数と比較し、繰り返したら、この数を取り除いて、再び発生します;第2に、1つの配列を乱数範囲内で繰り返さないすべての数に初期化し、1つの乱数を生成するたびにテーブル内のデータを削除し、次は残りの配列から新しい乱数を生成する.3つ目は、1つの配列を乱数範囲内で繰り返さないすべての数に初期化し、ある方法を使用して、その配列の要素の順序を乱し、前から必要な数の乱数を取ります.
構想を実現する:

srand((unsigned)time(NULL));
for (j=0;j<m;j++)
{
    a[j]=rand()%n;
    for(i=0;i<j;i++)
    {
        if(a[i]==a[j])
        {
            j-=1;
            break；
        }
    }
}

            
これは最も考えやすい方法であるが,比較回数は線形に増加し,後になるほど比較回数が多くなり,繰り返す可能性が高い.
構想二実現:

	int a[n]={0},b[m];            //a[n]      0
	srand((unsigned)time(NULL));
	for (i=0;i<m;i++)
	{
		while(a[x=rand()%n]);     //           ，    
		b[i]=x;
		a[x]=1;                   //               1
	}

       
小規模入力では、この方法は良いが、場合によっては問題もあり、1つの範囲内の大部分の数が生成された場合(フラグビットが1)、新しい乱数が生成され、whileサイクルで非常に多くの時間を浪費する可能性がある.これは方法と同様に、後になるほど乱数重複が生成される可能性が高い.新しい乱数を生成するコストも大きくなります.
 
構想三実現:

	for (i=0;i<n;i++)
		a[i]=i+1;                    //      n    
	srand((unsigned)time(NULL));
	for (i=0;i<m;i++)                //           ， m          
	{
		w=rand()%(n-i)+i;
		t=a[i];
		a[i]=a[w];
		a[w]=t;
	}

        
数値範囲が比較的小さく,範囲配列がターゲット配列の要素個数に近い場合,上記のアルゴリズムは非常に有効であり,ターゲット配列の要素個数が数値範囲よりはるかに小さい場合,この方法は余分な空間を浪費する.