2011年计算机二级C++辅导实例编程（2）

会计考友 · 发表于 2012-7-31 21:56:58

　　随机化算法——随机数
　　概率算法的一个基本特征是对所求解问题的同一实例用同一概率算法求解两次可能得到完全不同的效果。这两次求解问题所需的时间甚至所得到的结果可能会有相当大的差别。一般情况下，可将概率算法大致分为四类:数值概率算法，蒙特卡罗(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();
　　};
　　随机化算法——随机数
　　概率算法的一个基本特征是对所求解问题的同一实例用同一概率算法求解两次可能得到完全不同的效果。这两次求解问题所需的时间甚至所得到的结果可能会有相当大的差别。一般情况下，可将概率算法大致分为四类:数值概率算法，蒙特卡罗(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();
　　};
　　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
　　#include
　　#include
　　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
　　#include
　　#include
　　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;

会计考友 · 发表于 2012-7-31 21:56:59

</p>　　// heads得到的i次正面的次数
# p( f& m* L8 v* e8 U　　long i, heads[NCOINS+1];
* k; I- s; b/ J0 i　　int j, position;; t8 E' D! Z, T
　　// 初始化数组heads
2 u- P5 l% z9 W6 [9 Z6 |% Z* P　　for(j = 0; j < NCOINS+1; ++j)4 _) l% o. f X4 m
　　heads[j] = 0;
! L) N7 [- j& S9 h1 z* W) b) b+ P　　// 重复50,000次模拟事件1 y" ?0 x" H/ Q- c( ?, g
　　for(i = 0; i < NTOSSES; ++i)
0 S" s3 u3 C) n/ j! P5 r4 G5 E; Q　　heads[TossCoins(NCOINS)] ++;# B: f# d: s( b; L& h) Z
　　// 输出频率图* y! g0 J5 [6 O7 v6 k! g
7 D0 s, T- ]% p; Y1 |8 X5 T
　　for(i = 0; i

		自动登录	找回密码
密码			立即注册

[C++] 2011年计算机二级C++辅导实例编程（2）

2011年计算机二级C++辅导实例编程（2）

浏览过的版块