当前位置：编程学习 > 网站相关 >>

随机化算法(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称为该随机序列的种子。


一般情况下，取易做图(m, b)=1，因此可取b为一素数。




这是一个随机数类：









1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38



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：









1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23



// RandomNumber.h
 
const unsigned long maxshort = 65535L;
const
补充：综合编程 , 其他综合 ,
上一个：概率算法
下一个：《算法导论》学习总结 — 2.第一章 && 第二章 && 第三章
更多图片编程知识:

  
更多网站相关疑问解答：
点com的文化和设计
网站项目管理规范手册
设计师不可不看----《李永诠设计录》
网站开发规范
设计之心理学研究
网页艺术设计初探
网页设计的八种陋习
平面构成入门（一）平面构成的基本要素
Web 上图形设计的最佳实践
平面构成入门（三）平面构成的形式
平面构成入门（二）单形的构成
网站风格之魂
网站生存的关键---创意
平面构成入门-平面构成的基本要素
从美的原则谈 WWW 网页上的艺术表现 一：美的原则







  





CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络，