2017年計(jì)算機(jī)二級(jí)C++輔導(dǎo)實(shí)例編程（2）

隨機(jī)化算法——隨機(jī)數(shù)
    概率算法的一個(gè)基本特征是對(duì)所求解問(wèn)題的同一實(shí)例用同一概率算法求解兩次可能得到完全不同的效果。這兩次求解問(wèn)題所需的時(shí)間甚至所得到的結(jié)果可能會(huì)有相當(dāng)大的差別。一般情況下，可將概率算法大致分為四類:數(shù)值概率算法，蒙特卡羅(Monte Carlo)算法，拉斯維加斯(Las Vegas)算法和舍伍德(Sherwood)算法。
    隨機(jī)數(shù)在概率算法設(shè)計(jì)中扮演著十分重要的角色。在現(xiàn)實(shí)計(jì)算機(jī)上無(wú)法產(chǎn)生真正的隨機(jī)數(shù)，因此在概率算法中使用的隨機(jī)數(shù)都是一定程度上隨機(jī)的，即偽隨機(jī)數(shù)。
    產(chǎn)生隨機(jī)數(shù)最常用的方法是線性同余法。由線性同余法產(chǎn)生的隨機(jī)序列a1,a2,…,an滿足
    1.a0=d
    2.an=(b*an-1+c)mod m (n=1,2…….)
    其中,b>0, c>=0, d>=m。d稱為該隨機(jī)序列的種子。
    一般情況下，取gcd(m, b)=1，因此可取b為一素?cái)?shù)。
    這是一個(gè)隨機(jī)數(shù)類：
    代碼
    const unsigned long maxshort = 65535L;
    const unsigned long multiplier = 1194211693L;
    const unsigned long adder = 12345L;
    class RandomNumber{
    private:
    // 當(dāng)前種子
    unsigned long randSeed;
    public:
    // 構(gòu)造函數(shù),默認(rèn)值0表示由系統(tǒng)自動(dòng)產(chǎn)生種子
    RandomNumber(unsigned long s = 0);
    // 產(chǎn)生0 ~ n-1之間的隨機(jī)整數(shù)
    unsigned short Random(unsigned long n);
    // 產(chǎn)生[0, 1) 之間的隨機(jī)實(shí)數(shù)
    double fRandom();
    };
    // 產(chǎn)生種子
    RandomNumber::RandomNumber(unsigned long s)
    {
    if(s == 0)
    randSeed = time(0); //用系統(tǒng)時(shí)間產(chǎn)生種子
    else
    randSeed = s;
    }
    // 產(chǎn)生0 ~ n-1 之間的隨機(jī)整數(shù)
    unsigned short RandomNumber::Random(unsigned long n)
    {
    randSeed = multiplier * randSeed + adder;
    return (unsigned short)((randSeed >> 16) % n);
    }
    // 產(chǎn)生[0, 1)之間的隨機(jī)實(shí)數(shù)
    double RandomNumber::fRandom()
    {
    return Random(maxshort) / double(maxshort);
    }
    利用這個(gè)隨機(jī)數(shù)類，寫一個(gè)程序，模擬拋硬幣的實(shí)驗(yàn)。
    拋10次硬幣構(gòu)成一個(gè)事件，每次事件記錄得到正面的個(gè)數(shù)。反復(fù)模擬這個(gè)事件50,000次，然后對(duì)這50,000L次進(jìn)行輸出頻率圖，比較每次事件得到正面次數(shù)的比例。
    以下是總的代碼：
    頭文件 RandomNumber.h：
    代碼
    // 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:
    // 當(dāng)前種子
    unsigned long randSeed;
    public:
    // 構(gòu)造函數(shù),默認(rèn)值0表示由系統(tǒng)自動(dòng)產(chǎn)生種子
    RandomNumber(unsigned long s = 0);
    // 產(chǎn)生0 ~ n-1之間的隨機(jī)整數(shù)
    unsigned short Random(unsigned long n);
    // 產(chǎn)生[0, 1) 之間的隨機(jī)實(shí)數(shù)
    double fRandom();
    };
    #endif
    類實(shí)現(xiàn)文件RandomNumber.cpp :
    代碼
    // RandomNumber.cpp
    #include "RandomNumber.h"
    #include
    #include
    #include
    using namespace std;
    // 產(chǎn)生種子
    RandomNumber::RandomNumber(unsigned long s)
    {
    if(s == 0)
    randSeed = time(0); //用系統(tǒng)時(shí)間產(chǎn)生種子
    else
    randSeed = s;
    }
    // 產(chǎn)生0 ~ n-1 之間的隨機(jī)整數(shù)
    unsigned short RandomNumber::Random(unsigned long n)
    {
    randSeed = multiplier * randSeed + adder;
    return (unsigned short)((randSeed >> 16) % n);
    }
    // 產(chǎn)生[0, 1)之間的隨機(jī)實(shí)數(shù)
    double RandomNumber::fRandom()
    {
    return Random(maxshort) / double(maxshort);
    }
    主文件Main :
    代碼
    // 主文件main
    /*
    * Author: Tanky woo
    * Blog: www.WuTianQi.com
    * Date: 2010.12.7
    * 代碼來(lái)至王曉東《計(jì)算機(jī)算法設(shè)計(jì)與分析》
    */
    #include "RandomNumber.h"
    #include
    #include
    #include
    using namespace std;
    int TossCoins(int numberCoins)
    {
    // 隨機(jī)拋硬幣
    static RandomNumber coinToss;
    int i, tosses = 0;
    for(i = 0; i < numberCoins; ++i)
    tosses += coinToss.Random(2);
    return tosses;
    }
    int main()
    {
    // 模擬隨機(jī)拋硬幣事件
    const int NCOINS = 10;
    const long NTOSSES = 50000L;
    // heads[i]得到的i次正面的次數(shù)
    long i, heads[NCOINS+1];
    int j, position;
    // 初始化數(shù)組heads
    for(j = 0; j < NCOINS+1; ++j)
    heads[j] = 0;
    // 重復(fù)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
    cout << " ";
    cout << "*" << endl;
    }
    return 0;
    }
    輸出頻率圖：