一些数据结构的思想(3)
随机函数发生器的设计 假设你希望以各1/2的概率输出0和1.你可以自由使用一个输出0或1的过程BIASED-RANDOM。它以概率p输出1，以概率1 - p输出0，其中 0 < p < 1，但是你并不知道p的值。给出一个利用BIASED-RANDOM作为子程序的算法，返回一个无偏向的结果，即以概率1/2返回0，以概率1/2返回1。作为p的函数，你的算法的期望运行时间是多少？ 算法分析： 已知BIASED-RANDOM可产生0和1，那么 1 - BIASED-RANDOM也产生1和0，且以1 - p的概率输出1，以p的概率输出0。 如果我们将1 - BIASED-RANDOM看做另外一个函数发生器，和BIASED-RANDOM组合成对被调用，有以下结论： 调用结果 00 01 10 11 1的个数 0 1 1 2 出现概率 (1-p)*(1-p) (1-p)*(1-p) p*p p*(1-p) 那么，进行一次调用，出现1的个数的期望值为： 0 * (1-p)*(1-p) + 1 * (1-p)*(1-p) + 1 * p*p + 2 * p*(1-p) = 1。进行4次成对调用，则1的期望个数为4。为什么要调用4次呢？因为BIASED-RANDOM产生0的概率和 1 - BIASED-RANDOM产生1的概率相等；BIASED-RANDOM产生1的概率和 1 - BIASED-RANDOM产生0的概率相等，那么4次刚好覆盖了所有组合对（00,01,10,11），也可进行8次，16次等调用。当进行4次成对调用后，统计1出现的个数，若小于4次，则返回0；大于4次，则返回1（这里相当于将4次调用封装为了一个函数）。但有个问题，等于4次该返回0还是1呢？（因为1的可能次数为0至8）所以，可进行大量成对调用，以使单个现象可被忽略。如，进行1024次调用，统计1的个数，小于1024返回0，否则返回1。 随机概率发生器 题目： 已知一随机发生器，产生0的概率是p，产生1的概率是1-p，现在要你构造一个发生器，使得它构造0和1的概率均为1/2 解决方案： 这是随机概率发生器的典型题目。 由于需要产生1/2，而用1位0，或1位1无法产生等概率，因此，考虑将随机数扩展成2位： 00 p*p 01 p*(1-p) 10 (1-p)*p 11 (1-p)*(1-p) 有上述分析知道，01和10是等概率的，因此我们只需要产生01和10就行了。 于是可以，遇到00和11就丢弃，只记录01和10。可以令，01表示0,10表示1，则等概率1/2产生0和1了。 扩展： 已知一随机发生器，产生0的概率是p，产生1的概率是1-p，现在要你构造一个发生器，使得它构造0和1的概率均为1/2；构造一个发生器，使得它构造1、2、3的概率均为1/3；...，构造一个发生器，使得它构造1、2、3、...n的概率均为1/n，要求复杂度最低。 解答： 对n=2，认为01表示0、10表示1，等概率，其他情况放弃 对n=3，认为001表示1、010表示2，100表示3，等概率，其他情况放弃 对n=4，认为0001表示1、0010表示2，0100表示3，1000表示4，等概率，其他情况放弃 首先是1/2的情况，我们一次性生成两个数值，如果是00或者11丢弃，否则留下，01为1，10为0，他们的概率都是p*(1-p)是相等的，所以等概率了。然后是1/n的情况了，我们以5为例，此时我们取x=2，因为C(2x,x)=C(4,2)=6是比5大的最小的x，此时我们就是一次性生成4位二进制，把1出现个数不是2的都丢弃，这时候剩下六个:0011,0101,0110,1001,1010,1100，取最小的5个，即丢弃1100，那么我们对于前5个分别编号1到5，这时候他们的概率都是p*p*(1-p)*(1-p)相等了。 关键是找那个最小的x，使得C(2x,x)>=n这样能提升查找效率 平均要取多少个(0,1)中的随机数才能让和超过1 数学常数最令人着迷的就是，它们常常出现在一些看似与之毫不相干的场合中。 随便取一个 0 到 1 之间的数，再加上另一个 0 到 1 之间的随机数，然后再加上一个 0 到 1 之间的随机数⋯⋯直到和超过 1 为止。一个有趣的问题：平均需要加多少次，才能让和超过 1 呢？答案是 e 次。 #define NUM 9999999 int main() { int sum=0; srand(time(NULL)); for (int i=0;i<NUM;i++) { double val=0; while(val <1) { val+=(rand()/(double)RAND_MAX); sum++; } } printf("%f\n",sum/(double)NUM); return 0; } 为了证明这一点，让我们先来看一个更简单的问题：任取两个 0 到 1 之间的实数，它们的和小于 1 的概率有多大？容易想到，满足 x+y<1 的点 (x, y) 占据了正方形 (0, 1)×(0, 1) 的一半面积，因此这两个实数之和小于 1 的概率就是 1/2 。类似地，三个数之和小于 1 的概率则是 1/6 ，它是平面 x+y+z=1 在单位立方体中截得的一个三棱锥。这个 1/6 可以利用截面与底面的相似比关系，通过简单的积分求得： 可以想到，四个 0 到 1 之间的随机数之和小于 1 的概率就等于四维立方体一角的“体积”，它的“底面”是一个体积为 1/6 的三维体，在第四维上对其进行积分便可得到其“体积” ∫(0..1) (x^3)*1/6 dx = 1/24 依此类推， n 个随机数之和不超过 1 的概率就是 1/n! ，反过来 n 个数之和大于 1 的概率就是 1 - 1/n! ，因此加到第 n 个数才刚好超过 1 的概率就是 (1 - 1/n!) - (1 - 1/(n-1)!) = (n-1)/n! 因此，要想让和超过 1 ，需要累加的期望次数为 ∑(n=2..∞) n * (n-1)/n! = ∑(n=1..∞) n/n! = e x&(x-1)表达式的意义 求下面函数的返回值(微软) -- 统计1的个数 int func(int x) { int countx = 0; while(x) { countx++; x = x&(x-1); } return countx; } 假定x = 9999 10011100001111 答案: 8 思路: 将x转化为2进制，看含有的1的个数。 注:每执行一次x = x&(x-1)，会将x用二进制表示时最右边的一个1变为0，因为x-1将会将该位(x用二进制表示时最右边的一个1)变为0。 判断一个数(x)是否是2的n次方 #include <stdio.h> int func(int x) { if( (x&(x-1)) == 0 ) return 1; else return 0; } int main() { int x = 8; printf("%d\n", func(x)); } 注: (1)如果一个数是2的n次方，那么这个数用二进制表示时其最高位为1，其余位为0。 (2)== 优先级高于& 本文转自我爱物联网博客园博客，原文链接：http://www.cnblogs.com/yydcdut/p/3878319.html，如需转载请自行联系原作者
