随机化算法(1) — 随机数
最近在看王晓东的《计算机算法设计与分析(第3版) 》，感觉讲的挺不错的。这里先推荐下。
接下来的几章(包括本章)，我准备以连载的方式讲出来，主要用到的资料是上面推荐的那本书以及《算法导论》和网上的资源，内容是概率分析与随机算法。文章内大部分内容出自书中，我仅以汇总形式以及个人理解加以补充。如有纰漏，欢迎指出。
概率算法的一个基本特征是对所求解问题的同一实例用同一概率算法求解两次可能得到完全不同的效果。这两次求解问题所需的时间甚至所得到的结果可能会有相当大的差别。一般情况下，可将概率算法大致分为四类:数值概率算法，蒙特卡罗（Monte Carlo）算法，拉斯维加斯（Las Vegas）算法和舍伍德（Sherwood）算法。
随机数在概率算法设计中扮演着十分重要的角色。在现实计算机上无法产生真正的随机数，因此在概率算法中使用的随机数都是一定程度上随机的，即伪随机数。
产生随机数最常用的方法是线性同余法。由线性同余法产生的随机序列a1,a2,…,an满足
1.a0=d
2.an=(b*an-1+c)mod m （n=1,2…….）
其中,b>0, c>=0, d>=m。d称为该随机序列的种子。一般情况下，取gcd(m, b)=1，因此可取b为一素数。
这是一个随机数类：
const unsigned long maxshort = 65535L; const unsigned long multiplier = 1194211693L; const unsigned long adder = 12345L; class RandomNumber{ private: // 当前种子 unsigned long randSeed; public: // 构造函数,默认值0表示由系统自动产生种子 RandomNumber(unsigned long s = 0); // 产生0 ~ n-1之间的随机整数 unsigned short Random(unsigned long n); // 产生[0, 1) 之间的随机实数 double fRandom(); }; // 产生种子 RandomNumber::RandomNumber(unsigned long s) { if(s == 0) randSeed = time(0); //用系统时间产生种子 else randSeed = s; } // 产生0 ~ n-1 之间的随机整数 unsigned short RandomNumber::Random(unsigned long n) { randSeed = multiplier * randSeed + adder; return (unsigned short)((randSeed >> 16) % n); } // 产生[0, 1)之间的随机实数 double RandomNumber::fRandom() { return Random(maxshort) / double(maxshort); }利用这个随机数类，写一个程序，模拟抛硬币的实验。
抛10次硬币构成一个事件，每次事件记录得到正面的个数。反复模拟这个事件50,000次，然后对这50,000L次进行输出频率图，比较每次事件得到正面次数的比例。
以下是总的代码：
头文件 RandomNumber.h：
补充：综合编程 , 其他综合 ,CopyRight © 2012 站长网 编程知识问答 www.zzzyk.com All Rights Reserved
部份技术文章来自网络，
