算法导论： 第5章

5.1-2 生成Random(a,b)

    运行b-a次Random(0,1),累加和，最后再加a

5.1-3 等概率生成0和1

   Biased-Random 以概率p输出1，以概率1-p输出0，

  则1-Biased-Random 以概率p输出0，以概率1-p输出1

  则调用Biased-Random后接着调用1-Biased-Random，出现的概率为

   调用结果　　　　00　　　　　　01　　　　　 10　　　　11

   出现概率　   (1-p)*p　　  (1-p)*(1-p)　　   p*p　　  p*(1-p)

则1出现的期望E[1] = (1-p)*(1-p) + p*p + 2*p*(1-p) = 1;

  0出现的期望E[0] = 2(1-p)*p + (1-p)*(1-p) + p*p = 1;

故调用一次（Biased-Random） + （1-Biased-Random）就可以让0和1出现的概率相等。连续调用这个组合，统计0和1出现的个数，直到它们出现的个数不相等。此时输出出现次数多的那个。

网上还有另外一种解法：运行Biased-Random两次产生x和y，连续运行直到两个数不等，然后输出x

5.3-5 Random(1,n^3)所有元素都唯一的概率至少为1-1/n

参见http://photo.blog.sina.com.cn/list/blogpic.php?pid=932e6e55hc37388f5a11d&bid=932e6e5501015a80&uid=2469293653

5.1 概率计数

待补充

算法导论： 第5章,布布扣,bubuko.com

算法导论： 第5章

原文：http://www.cnblogs.com/rolling-stone/p/3634303.html