lvjing2的专栏

随机数生成器

计算机使用的随机数生成器往往是伪随机的,为了达到统计意义上的真随机数,可以需要引入系统 外的变量等作为随机种子(如UNIX系统中熵池)。假设有一天出现了上帝的投硬币函数: int G(); 由于这里用到的上帝硬币可能不均匀。但可以保证是G()可以x概率返回1,1-x的概率返回0,其中x为未知常数(且x不等于0或1)。

请实现目标函数: int F(double p); 要求

F函数以概率p返回1,以1-p返回0。除了G之外,不使用的任何库函数。 PS:定义宏UINT_MAX=0xffffffff

基于前述类似思路,请构造函数求下述无理数近似值:

double pi(); //圆周率πdouble e(); // 自然对数函数的底数e。

提示:作为模拟过程,可引入最高重复试验次数,请简述思路并完成代码。

思路: 1. 构造p概率随机数生成函数

由G()生成等概率随机数生成函数,,可参考算法导论或这篇博客由等概随机函数进行多次数(例如10次)随机,那么就会产生1024种结果,而且每种结构都等概。那么我们可以分析每种随机结果,每种随机结果可以用十进制表示,

0 1 0 1 0 0 1 0 1 1

可以用十进制331表示,所有可能的十进制都在[0, 1024)范围里。所以只要生成的十进制数小于1024*p就返回1,大于就返回0,这样就可满足要求。

2. pi和e生成方法 这种方法不知道是不是满足出题人的意思呢?这一部分的代码就不贴上来了。

;int F(double p){int sum = 0;int t = 10;int all = 1024;int t1 = all * p;for (int i = 0; i < t; ++i)sum += U()<<i;if (sum < t1)return 1;else if (sum >= t1)return 0;}U(){int n1 = -1, n2 = -1;do{n1 = G();n2 = G();if (n1 == 0 && n2 == 1)return 1;else if (n1 = 1 && n2 == 0)return 0;}while((n1 == 0 && n2 == 0) || (n1 == 1 && n2 == 1))exit(-1);}

懂得接受失败的人,就是懂得人生真谛的人,

lvjing2的专栏

相关文章:

你感兴趣的文章:

标签云: