本文共 1934 字，大约阅读时间需要 6 分钟。

1.有一个随机数发生器，能以概率p生成0，以概率1-p生成1，问如何做一个随机数发生器使得生成0和1的概率相等。

int f2(){ int a, b; do { a = f(); b = f(); }while(a == b); return (a - b + 1) / 2;}

 

2.用上面那个生成0和1的概率相等的随机数发生器，怎样做一个随机数发生器使得它生成的数在1...N之间均匀分布。

#include <iostream>#include <math.h>#include <time.h>using namespace std;srand ( time(NULL) );int qrand(){ return rand()%2;}int TonRand(int n){ int array_size; array_size = log(n)/log(2)+1; int *p = new int[array_size]; int i; int score; do{ score =0; for (i=0;i<array_size;i++){ p[i] = qrand(); } for (i=0;i<array_size;i++){ score+=(p[i]?pow(2,array_size-i-1):0); } } while (score>n||score==0); return score;}

 

3. 已有可以生成1到7均匀分布随机整数的函数f1t7()，写一个调用函数f1t7()产生1到10之间均匀分布随机整数的函数。

调用两次f1t7()，可能产生49种等概率的结果，将前40种结果均匀映射到1至10；产生后9种结果再调用两次f1t7()直到产生前40中情况为止。

(/frac{40}{49}*/frac{4}{40})+/frac{9}{49}*((/frac{40}{49}*/frac{4}{40})+/frac{9}{49}*((/frac{40}{49}*/frac{4}{40})+/cdots))//=(/frac{40}{49}*/frac{4}{40})*(1+/frac{9}{49}+/frac{9}{49}^{2}+/cdots)//=/frac{4}{49}*/frac{1}{1-/frac{9}{49}}//=/frac{4}{49}*/frac{49}{40}//=/frac{1}{10}

#include <stdio.h>#include <stdlib.h>#include <time.h>#include <string.h>int f1t7(){ return rand() % 7 + 1;}int f1t10(){ int t1 = f1t7(); int t2 = f1t7(); while((t1*10+t2) > 65){ t1 = f1t7(); t2 = f1t7(); } int t = t1*10+t2; if(t < 15) return 1; else if (t < 22) return 2; else if (t < 26) return 3; else if (t < 33) return 4; else if (t < 37) return 5; else if (t < 44) return 6; else if (t < 51) return 7; else if (t < 55) return 8; else if (t < 62) return 9; else if (t < 66) return 10; else return -1;}int main (){ int i; const int size = 10000000; const int range = 10; int iSecret; /* initialize random seed: */ srand ( time(NULL) ); int * keep = new int[range+1]; memset(keep,0,sizeof(int)*(range+1)); for(i = 0; i < size; i++){ iSecret = f1t10(); keep[iSecret]++; } for(i = 1; i <= range; i++){ printf("num=%d/tcount=%d/n", i, keep[i]); } return 0;}

 

转载地址：http://qhntb.baihongyu.com/