最近在看王曉東的《計(jì)算機(jī)算法設(shè)計(jì)與分析(第3版) 》，感覺講的挺不錯(cuò)的。這里先推薦下。
接下來的幾章(包括本章)，我準(zhǔn)備以連載的方式講出來，主要用到的資料是上面推薦的那本書以及《算法導(dǎo)論》和網(wǎng)上的資源，內(nèi)容是概率分析與隨機(jī)算法。文章內(nèi)大部分內(nèi)容出自書中，我僅以匯總形式以及個(gè)人理解加以補(bǔ)充。如有紕漏，歡迎指出。
概率算法的一個(gè)基本特征是對(duì)所求解問題的同一實(shí)例用同一概率算法求解兩次可能得到完全不同的效果。這兩次求解問題所需的時(shí)間甚至所得到的結(jié)果可能會(huì)有相當(dāng)大的差別。一般情況下，可將概率算法大致分為四類:數(shù)值概率算法，蒙特卡羅（Monte Carlo）算法，拉斯維加斯（Las Vegas）算法和舍伍德（Sherwood）算法。
隨機(jī)數(shù)在概率算法設(shè)計(jì)中扮演著十分重要的角色。在現(xiàn)實(shí)計(jì)算機(jī)上無法產(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 <iostream>
#include <stdlib.h>
#include <time.h>
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
* 代碼來至王曉東《計(jì)算機(jī)算法設(shè)計(jì)與分析》
*/
#include "RandomNumber.h"
#include <iostream>
#include <iomanip>
#include <time.h>
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<position-1; ++j)
cout << " ";
cout << "*" << endl;
}
return 0;
}
輸出頻率圖：
具體可以看看王曉東的《計(jì)算機(jī)算法設(shè)計(jì)與分析》第七章。
下一篇我會(huì)寫《隨機(jī)化算法(2) — 數(shù)值概率算法》。
Tanky Woo原創(chuàng)，歡迎轉(zhuǎn)載，轉(zhuǎn)載請(qǐng)附上鏈接，請(qǐng)不要私自刪除文章內(nèi)任何關(guān)于本博客的鏈接。
posted on 2010-12-10 08:01
Tanky Woo 閱讀(9474)
評(píng)論(2) 編輯 收藏 引用