Pilot's Blog
0%

第七章_随机化算法

发表于 分类于 ， Valine：
本文字数： 920 阅读时长 ≈ 1 分钟

随机数

随机算法

数值随机

计算π

设有一半径为r的圆及其外切四边形，向正方形随机投掷n个点。设落入圆内的点数为k。若所投入的点在正方形上均匀分布， 则所投入的点落入圆内的概率为：

1
2
3
4
5
6
7
8
9
10
11
12
double Darts(int n)
{ // 用随机投点法计算值
    static RandomNumber dart;
    int k=0;
    for (int i=1;i <=n;i++) 
    {   double x=dart.fRandom();
         double y=dart.fRandom();
         if ((x*x+y*y)<=1) k++;
     }
    return 4 * k / double(n);
}

计算定积分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
double Darts(int n) { 
    // 用随机投点法计算定积分 
    static RandomNumber dart; 
    int k = 0; 
    for (int i = 1; i <= n; i++) {
        double x = dart.fRandom(); 
        double y = dart.fRandom(); 
        if (y < f(x)) {
            k++; 
        }
    } 
    return k / double(n); 
}

注：上面两题本质上都是投点，限制点在目标区域，计算目标区域中点在整个区域中个数

舍伍德（Sher wood)

随机洗牌

算法思想

从位置1取到位置n，每个对应位置随机选一个位置，将两个位置的牌对调

1
2
3
4
5
6
7
8
9
template<class Type>
void Shuffle(Type a[], int n) // 随机洗牌算法
{  
    static RandomNumber rnd;
    for (int i=1;i<n;i++) 
    {    int j=rnd.Random(n-i)+i; // 产生[i, n-1]随机数
         Swap(a[i-1], a[j]);
     }
}

拉斯维加斯（Las Vegas)

标记重复元素

设有n个元素保存在一维数组a中，其中有n/2个元素各不相同，而另外n/2个元素有相同值。也就是说，总共有(n/2)+1种不同的元素值。现要求找出其中那个重复元素。

蒙特卡洛（Monte Carlo)