频道栏目
首页 > 程序开发 > 综合编程 > 其他综合 > 正文
随机化算法(2) — 数值概率算法
2011-04-16 13:09:07           
收藏   我要投稿

在这章开篇推荐下chinazhangjie总结的随机算法,因为咱两看的是同一本书,所以大家也可以去参考下他的,总结的很不错

/kf/201104/87905.html

这一章我就把书中的一个例子举出来了,感觉虽然很简单,但是很有意思。

用随机投点法计算Pi值

设有一半径为r的圆及其外切四边形。向该正方形随机地投掷n个点。设落入圆内的点数为k。由于所投入的点在正方形上均匀分布,因而所投入的点落入圆内的概率为(Pi*r*r)/(4*r*r)= Pi/4 。所以当n足够大时,k与n之比就逼近这一概率。从而,PI 约等于 (4*k)/n.

如下图:
\

因为代码里用到了上一章《概率算法(1) — 随机数》里的RandomNumber类,所以大家可以先把前一章看看。

我把这个伪随机类再贴一遍:

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);
}

主文件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
/*
* Author: Tanky woo
* Blog:   www.WuTianQi.com
* Date:   2010.12.8
* 用随机投点法计算Pi值
* 代码来至王晓东《计算机算法设计与分析》
*/
 
#include "RandomNumber.h"
#include <iostream>
#include <iomanip>
#include <time.h>
using namespace std;
 
double Darts(long n)
{
	// 用随机投点法计算Pi值
	static RandomNumber dart;
	
	
点击复制链接 与好友分享!回本站首页
相关TAG标签 算法 数值 概率
上一篇:概率算法
下一篇:随机化算法(3) — 舍伍德(Sherwood)算法
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站