随机化算法(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为一素数。

这是一个随机数类

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 unsigned long multiplier = 1194211693L;
const unsigned long adder = 12345L;
 
#ifndef RANDOMNUMBER_H
#define RANDOMNUMBER_H
 
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();
};
 
#endif

类实现文件RandomNumber.cpp :

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
// RandomNumber.cpp
#include "RandomNumber.h"
#include <iostream>
#include <stdlib.h>
#include <time.h>
 
using namespace std;
 
// 产生种子
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);
}

主文件Main :

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
39
40
41
42
43
44
45
46
47
48
// 主文件main
/*
* Author: Tanky woo
* Blog:   www.WuTianQi.com
* Date:   2010.12.7
* 代码来至王晓东《计算机算法设计与分析》
*/
#include "RandomNumber.h"
#include <iostream>
#include <iomanip>
#include <time.h>
using namespace std;
 
int TossCoins(int numberCoins)
{
	// 随机抛硬币
	static RandomNumber coinToss;
	int i, tosses = 0;
	for(i = 0; i < numberCoins; ++i)
		tosses += coinToss.Random(2);
	return tosses;
}
 
int main()
{
	// 模拟随机抛硬币事件
	const int NCOINS = 10;
	const long NTOSSES = 50000L;
	// heads[i]得到的i次正面的次数
	long i, heads[NCOINS+1];
	int j, position;
	// 初始化数组heads
	for(j = 0; j < NCOINS+1; ++j)
		heads[j] = 0;
	// 重复50,000次模拟事件
	for(i = 0; i < NTOSSES; ++i)
		heads[TossCoins(NCOINS)] ++;
	// 输出频率图
	for(i = 0; i <= NCOINS; ++i)
	{
		position = int (float(heads[i]) / NTOSSES*72);
		cout << setw(6) << i << " ";
		for(j = 0; j<position-1; ++j)
			cout << " ";
		cout << "*" << endl;
	}
	return 0;
}

输出频率图:

具体可以看看王晓东的《计算机算法设计与分析》第七章。

下一篇我会写《随机化算法(2) — 数值概率算法》。

www.WuTianQi.com Tanky Woo原创,欢迎转载,转载请附上链接,请不要私自删除文章内任何关于本博客的链接。

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《随机化算法(1) — 随机数》有44个想法

  1. const unsigned long maxshort = 65535L;
    const unsigned long multiplier = 1194211693L;
    const unsigned long adder = 12345L;

    博主,这些值的选取有什么特定含义吗?

    1. 额。不知道下面你说的random函数有没有收到我的回复邮件,再发一下吧:
      unsigned short RandomNumber::Random(unsigned long n)
      {
      randSeed = multiplier * randSeed + adder;
      return (unsigned short)((randSeed >> 16) % n);
      }

      我用的是自己实现的Randon类函数。C/C++库确实是没有random函数。

  2. 確實現在計算機上的隨機都是偽隨機,不過kita想到現實中應該也是偽隨機。比如擲色子,它的結果是色子質量、拋出力度、角度、空氣、降落點、降落面材質等許許多多的因素所共同產生的 [s:10]

      1. unsigned short RandomNumber::Random(unsigned long n)
        {
        randSeed = multiplier * randSeed + adder;
        return (unsigned short)((randSeed >> 16) % n);
        }

        。。。我用的是自己实现的Randon类函数。。。

  3. @韩国

    彩票的概率其实可以计算出来的,我以前玩十一运夺金就玩过一段时间,看起来出奖率很大,但是相对钱的数目很小,最后算一下概率,发现怎么玩都亏,除非运气好,一次中了大奖。

发表评论

电子邮件地址不会被公开。 必填项已用*标注