RANDOM(a,b)の実装
11974 ワード
ソースアドレス:http://buptdtt.blog.51cto.com/2369962/676880
アルゴリズム導論の5.1-2題.RANDOM(a,b)は、aとbの間の整数を返し、各整数が現れる機会は等しい.RANDOM(0,1)を呼び出すことができます.RANDOM(0,1)が0と1を生成する確率はいずれも0.5である.本にはRANDOM(0,1)への実装プログラムはないが、プログラムの調整を容易にするためにRANDOM(0,1)の代わりにrandom関数を自分で書いたので、正しいかどうかは分からない.
この問題の実現構想:
この問題は0,1をランダムに生成できる前提の下で,ランダム生成を要求することに相当する. n=b-a+1 個の整数 1、生成する数を a, a+1, a+2,..., b-a+1,…,b-1,b 2、最小のmを取って、2^m>=n 3、ランダムに0,1の関数を生成する mビット整数(各ビットをランダムに生成)をランダムに生成 [0,2^m]内の整数. 4、ランダムに1つの[0,2^m)の中の整数を生成して、もしこの数がaの大きさをプラスして[a,b]内にあるならば、この数を取って結果にします.この数がaをプラスして[a,b]の外にあるならば、それを捨てて、再び1つを生成します.
プログラム1
1～6の数字を10個生成
プログラム2:
プログラム1よりも簡潔であり,バイナリ数に対する処理と区別される.
アルゴリズム導論の5.1-2題.RANDOM(a,b)は、aとbの間の整数を返し、各整数が現れる機会は等しい.RANDOM(0,1)を呼び出すことができます.RANDOM(0,1)が0と1を生成する確率はいずれも0.5である.本にはRANDOM(0,1)への実装プログラムはないが、プログラムの調整を容易にするためにRANDOM(0,1)の代わりにrandom関数を自分で書いたので、正しいかどうかは分からない.
この問題の実現構想:
この問題は0,1をランダムに生成できる前提の下で,ランダム生成を要求することに相当する. n=b-a+1 個の整数 1、生成する数を a, a+1, a+2,..., b-a+1,…,b-1,b 2、最小のmを取って、2^m>=n 3、ランダムに0,1の関数を生成する mビット整数(各ビットをランダムに生成)をランダムに生成 [0,2^m]内の整数. 4、ランダムに1つの[0,2^m)の中の整数を生成して、もしこの数がaの大きさをプラスして[a,b]内にあるならば、この数を取って結果にします.この数がaをプラスして[a,b]の外にあるならば、それを捨てて、再び1つを生成します.
プログラム1
1～6の数字を10個生成
- #include "iostream.h "
- #include <time.h>
- #include <math.h>
- #include <stdlib.h>
- #include <iostream>
- using namespace std;
-
- int random() // 0 1
- {
- int a;
- a=rand()%2; //rand()%2 0 1,
- return a;
- }
- int FindMinExp(int n) // random(a, b) n=b-a+1， m, //2^m >= n.
- {
-
- int m=0; // m
-
- int n1 = n; // n
-
- while(n>=2)
-
- {
-
- n /= 2;
-
- m ++;
-
- }
-
- if(pow(2, m)<n1)
-
- m ++;
-
- return m; // m.
-
- }
-
- int BinaryToDecimal(char bin[]) // 。
-
- {
-
- int result = 0;
-
- char *p = bin;
-
- while (*p)
-
- {
-
- result = (result << 1 ) + (*p - '0');
-
- p++;
-
- }
-
- return (result);
-
- }
-
- int Random(int a, int b)// a b -1
-
- {
-
- char string[20];
-
- int i=0, m=0, n = b - a+1;
-
- m = FindMinExp(n); // m, 2^m >= n.
-
- while(m)
-
- {
-
- int l=random();
- itoa(l,&string[i++],10);// 01
- m --;
-
- }
-
- int generate_data = BinaryToDecimal (string);//m 。
-
- if(generate_data+a >= a && generate_data +a<=b)// [a,b] ， ， ，// 。
-
- return generate_data+a;
- else
- return -1;
-
- }
-
- void main()
- {
- srand((unsigned)time(0)); //
- for(int i=0;i<10;)
- {
- int k=Random(1,6);
- if(k!=-1)
- {printf("%d ",k);
- i++;
- }
- }
- }
プログラム2:
プログラム1よりも簡潔であり,バイナリ数に対する処理と区別される.
- #include "iostream.h "
- #include <time.h>
- #include <math.h>
- #include <stdlib.h>
- #include <iostream>
- using namespace std;
-
- int random() // 0 1
- {
- int a;
- a=rand()%2; //rand()%2 0 1,
- return a;
- }
-
-
- int FindMinExp(int n) // random(a, b) n=b-a+1， m, //2^m >= n.
-
- {
-
- int m=0; // m
-
- int n1 = n; // n
-
- while(n>=2)
-
- {
-
- n /= 2;
-
- m ++;
-
- }
-
- if(pow(2, m)<n1)
-
- m ++;
-
- return m; // m.
-
- }
-
-
-
- int Random(int a, int b)
-
- {
-
- char string[20];
-
- int i=0, m=0, n = b - a+1;
-
- m = FindMinExp(n); // m, 2^m >= n.
- int generate_data=0;
- while(m)
-
- {
- generate_data<<=1; // “<<1”?
- generate_data=generate_data+ random();
- m --;
-
- }
-
- if(generate_data+a >= a && generate_data+a <=b)// [a,b] ， ， ，// 。
-
- return generate_data+a;
- else
- return -1;
-
- }