频道栏目
首页 > 程序开发 > 综合编程 > 其他综合 > 正文
概率算法
2011-04-16 13:09:46           
收藏   我要投稿

一、随机数 

  随机数在概率算法设计中扮演着十分重要的角色。在现实计算机上无法产生真正的随机数,因此在概率算法中使用的随机数都是一定程度上随机的,即伪随机数

线性同余法是产生伪随机数的最常用的方法。由线性同余法产生的随机序列a0,a1,…,an满足

\

  其中b >= 0,c >= 0,d <= m。d称为该随机序列的种子。如何选取该方法中的常数b、c和m直接关系到所产生的随机序列的随机性能。这是随机性理论研究的内容,已超出本书讨论的范围。从直观上看,m应取得充分大,因此可取m为机器大数,另外应取gcd(m, b) = 1,因此可取b为一素数

二、数值概率算法

1、用随机投点法计算pi

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

\

实现:

/* 主题:随机投点法计算PI值
* 作者:chinazhangjie
* 邮箱:chinajiezhang@gmail.com
* 开发语言:C++
* 开发环境:Code::Blocks 10.05
* 时间: 2010.11.11
*/
#include
<iostream>
#include
<cstdlib>
#include
<limits>
using namespace std;

// 获得0-1之间的随机数
double get_random_num ()
{
   
return (double)rand () / RAND_MAX ;
}
// 用随机投点法计算 PI
double darts (int n)
{
   
int k = 0 ;
   
for (int i = 0; i < n; ++ i) {
       
double x = get_random_num() ;
       
double y = get_random_num() ;
       
if ((x * x + y * y) <= 1.0) {
           
++ k ;
        }
    }
   
return (4 * k) / (double)n ;
}
int main()
{
    cout
<< darts (200000000) << endl ;
}

 

 

2.计算定积分

设f(x)是[0,1]上的连续函数,且0 <= f(x) <= 1。

需要计算的积分为\,积分I等于图中的面积G。

\

在图所示单位正方形内均匀地作投点试验,则随机点落在曲线下面的概率为

\

假设向单位正方形内随机地投入n个点(xi,yi)。如果有m个点落入

G内,则随机点落入G内的概率\

假定 f(x) = x * x (0 <= x <= 1)计算定积分

实现:

/* 主题:随机投点法计算定积分
* 作者:chinazhangjie
* 邮箱:chinajiezhang@gmail.com
* 开发语言:C++
* 开发环境:Code::Blocks 10.05
* 时间: 2010.11.11
*/
#include
<iostream>
#include
<cstdlib>
using

点击复制链接 与好友分享!回本站首页
相关TAG标签 概率 算法
上一篇:随机化算法(1) — 随机数
下一篇:随机化算法(2) — 数值概率算法
相关文章
图文推荐
文章
推荐
点击排行

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

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