概率算法

一、随机数

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

线性同余法是产生伪随机数的最常用的方法。由线性同余法产生的随机序列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

补充：综合编程 , 其他综合 ,