最近在看王曉東的《計算機算法設計與分析(第3版) 》，感覺講的挺不錯的。這里先推薦下。
接下來的幾章(包括本章)，我準備以連載的方式講出來，主要用到的資料是上面推薦的那本書以及《算法導論》和網上的資源，內容是概率分析與隨機算法。文章內大部分內容出自書中，我僅以匯總形式以及個人理解加以補充。如有紕漏，歡迎指出。
概率算法的一個基本特征是對所求解問題的同一實例用同一概率算法求解兩次可能得到完全不同的效果。這兩次求解問題所需的時間甚至所得到的結果可能會有相當大的差別。一般情況下，可將概率算法大致分為四類:數值概率算法，蒙特卡羅（Monte Carlo）算法，拉斯維加斯（Las Vegas）算法和舍伍德（Sherwood）算法。
隨機數在概率算法設計中扮演著十分重要的角色。在現實計算機上無法產生真正的隨機數，因此在概率算法中使用的隨機數都是一定程度上隨機的，即偽隨機數。
產生隨機數最常用的方法是線性同余法。由線性同余法產生的隨機序列a1,a2,…,an滿足
1.a0=d
2.an=(b*an-1+c)mod m （n=1,2…….）
其中,b>0, c>=0, d>=m。d稱為該隨機序列的種子。
一般情況下，取gcd(m, b)=1，因此可取b為一素數。
這是一個隨機數類：
const unsigned long maxshort = 65535L;
const unsigned long multiplier = 1194211693L;
const unsigned long adder = 12345L;
class RandomNumber{
private:
// 當前種子
unsigned long randSeed;
public:
// 構造函數,默認值0表示由系統自動產生種子
RandomNumber(unsigned long s = 0);
// 產生0 ~ n-1之間的隨機整數
unsigned short Random(unsigned long n);
// 產生[0, 1) 之間的隨機實數
double fRandom();
};
// 產生種子
RandomNumber::RandomNumber(unsigned long s)
{
if(s == 0)
randSeed = time(0); //用系統時間產生種子
else
randSeed = s;
}
// 產生0 ~ n-1 之間的隨機整數
unsigned short RandomNumber::Random(unsigned long n)
{
randSeed = multiplier * randSeed + adder;
return (unsigned short)((randSeed >> 16) % n);
}
// 產生[0, 1)之間的隨機實數
double RandomNumber::fRandom()
{
return Random(maxshort) / double(maxshort);
}
利用這個隨機數類，寫一個程序，模擬拋硬幣的實驗。
拋10次硬幣構成一個事件，每次事件記錄得到正面的個數。反復模擬這個事件50,000次，然后對這50,000L次進行輸出頻率圖，比較每次事件得到正面次數的比例。
以下是總的代碼：
頭文件 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:
// 當前種子
unsigned long randSeed;
public:
// 構造函數,默認值0表示由系統自動產生種子
RandomNumber(unsigned long s = 0);
// 產生0 ~ n-1之間的隨機整數
unsigned short Random(unsigned long n);
// 產生[0, 1) 之間的隨機實數
double fRandom();
};
#endif
類實現文件RandomNumber.cpp :
// RandomNumber.cpp
#include "RandomNumber.h"
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
// 產生種子
RandomNumber::RandomNumber(unsigned long s)
{
if(s == 0)
randSeed = time(0); //用系統時間產生種子
else
randSeed = s;
}
// 產生0 ~ n-1 之間的隨機整數
unsigned short RandomNumber::Random(unsigned long n)
{
randSeed = multiplier * randSeed + adder;
return (unsigned short)((randSeed >> 16) % n);
}
// 產生[0, 1)之間的隨機實數
double RandomNumber::fRandom()
{
return Random(maxshort) / double(maxshort);
}
主文件Main :
// 主文件main
/*
* Author: Tanky woo
* Blog: www.WuTianQi.com
* Date: 2010.12.7
* 代碼來至王曉東《計算機算法設計與分析》
*/
#include "RandomNumber.h"
#include <iostream>
#include <iomanip>
#include <time.h>
using namespace std;
int TossCoins(int numberCoins)
{
// 隨機拋硬幣
static RandomNumber coinToss;
int i, tosses = 0;
for(i = 0; i < numberCoins; ++i)
tosses += coinToss.Random(2);
return tosses;
}
int main()
{
// 模擬隨機拋硬幣事件
const int NCOINS = 10;
const long NTOSSES = 50000L;
// heads[i]得到的i次正面的次數
long i, heads[NCOINS+1];
int j, position;
// 初始化數組heads
for(j = 0; j < NCOINS+1; ++j)
heads[j] = 0;
// 重復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;
}
輸出頻率圖：
具體可以看看王曉東的《計算機算法設計與分析》第七章。
下一篇我會寫《隨機化算法(2) — 數值概率算法》。
Tanky Woo原創，歡迎轉載，轉載請附上鏈接，請不要私自刪除文章內任何關于本博客的鏈接。
posted on 2010-12-10 08:01
Tanky Woo 閱讀(9505)
評論(2) 編輯 收藏 引用