随机与概率简要说明
目录
随机的类型
- 真随机
电脑会检测电脑外部发生的某种物理现象(气象变化，股市变化等)。比如说，电脑可以测量某个原子的放射性衰变。根据量子理论，原子衰变是随机而不可测的， 所以这就是宇宙中的“纯粹”随机性。攻击者永远无法预测原子衰变的发生时间，也就不可能猜出随机值。举个更实际的例子， 电脑会根据环境中的噪音或者采取你敲击键盘的精确时间作为随机数据生成依据。举个例子， 你的电脑监测到你某天下午2点以后敲击键盘的精确时间是0.23423523秒，有足够的这些特定长数字你也就可以生成“真”随机数。 由于人不是机器，所以攻击者无法掌握你的敲击时间。
- 伪随机
伪随机数这个概念是相对于“真”随机数而言。电脑通过发送种子数值，运用算法产生某个看起来像随机数的数字。 但是实际上这个数字是可以预测的。因为电脑没有从环境中收集到任何随机信息。 虽然是伪随机数，但是并不是所有领域都不需要伪随机数。比如，如果你在玩电子游戏， 那么游戏过程中是靠伪随机数还是真随机数并不重要。另一方面，如果你的应用正在加密，情况就不同了，因为你不希望攻击者能够猜到你的随机数。 举个例子，如果攻击者掌握了某随机数生成器使用的种子数值和加密算法， 如果随机数生成器完全依靠种子数值和加密算法生成密文，这个过程中不添加任何额外随机性， 如果攻击者掌握的情报足够多，他们可以逆推来确定加密算法一定会用到的伪随机数，也就能破译密文。
随机数网站(www.random.org)
随机数研究网站，这个网址用来提供真正的随机数据（依赖大气相关的物理运动）并给出了部分的请求接口及相关的算法，值得参考！
PHP语言中随机相关的函数
- int rand ( void );int rand ( int $min , int $max ) 直接用来产生一个随机数
- int mt_rand ( void );int mt_rand ( int $min , int $max ) 加强版的随机数产生，根据手册说明，效率会更好
- void mt_srand ([ int $seed ] ) 种子数产生器
- void srand ([ int $seed ] ) 种子数产生器
伪随机数如何产生
PHP及C语言中的随机数都是通过“线性同余方法”进行产生的，即通过算法产生！ 具体参考纯线性同余随机数生成器 LCG 算法数学上基于公式：X(n+1) = (a * X(n) + c) % m 其中，各系数为： 模m, m > 0 系数a, 0 < a < m 增量c, 0 <= c < m 原始值(种子) 0 <= X(0) < m 其中参数c, m, a比较敏感，或者说直接影响了伪随机数产生的质量。 一般而言，高LCG的m是2的指数次幂(一般2^32或者2^64)，因为这样取模操作截断最右的32或64位就可以了。多数编译器的库中使用了该理论实现其伪随机数发生器rand()。
C语言中伪随机数生成算法实际上是采用了"线性同余法"。具体的计算如下： Xi = (Xi-1 * A + C ) mod M 其中A,C,M都是常数（一般会取质数）。当C=0时，叫做乘同余法。引出一个概念叫seed，它会被作为X0被代入上式中， 然后每次调用rand()函数都会用上一次产生的随机值来生成新的随机值。可以看出实际上用rand()函数生成的是一个递推的序列，一切值都来源于最初的seed。 所以当初始的seed取一样的时候，得到的序列都相同，这也就可以解释目前北京摇号系统的原理，在每次摇号前需要得到6个种子数，然后基于这确定的 6个种子数来产生的对应的随机序列！
PHP中随机代码实例
<source lang="PHP"> <?php srand(5); echo(rand(1, 10)); echo(rand(1, 10)); echo(rand(1, 10)); ?> 结果显示：2,6,9 ，种子数确定为5，那么每次运行的结果都是确定的，只不过在4.2以后的rand函数中每次调用都是使用新的随机数！ </source>
<source lang="PHP"> <?php srand(5); echo(rand(1, 10)); srand(5); echo(rand(1, 10)); srand(5); echo(rand(1, 10)); ?> 结果显示：2,2,2，种子数确定为5，每次执行之前都强制使用了种子数，导致执行的结果每次都一致 </source>
大转盘抽奖思路
简要说下大转盘抽奖思路，首先是每种奖品的几率配置：比如A,B,C,D四种奖品，几率分别设定为A(0.5),B(0.3),C(0.15),D(0.05) ，对应的就是50%,30%,15%,5% 其实不管几率是怎么设定加起来是否为1或其他别的，总体的算法就是每一种奖品的几率为： A(几率)/(A(几率)+B(几率)+C(几率)+D(几率)) 如果其中任何一种奖品已经被抽光，没有了的话，那么剩下的奖品会再次分配几率 如果B被抽光了，那么剩余的就是A，C，D直接按照上面的算法重新计算新的几率配比！ 在几率配比确定后，然后基于一个放大的基数（比如说是1000,10000），根据奖品的配比形成一个键值配对数组，例如从1-100为A，101-300为B，301-900为C，901-999为D 在此数组基础上，进行随机处理，打乱排列顺序，然后随机产生一个0-999之间的数值，查看该数值所对应的数组值对应的是那个奖品，类似于打地鼠的游戏
具体代码： <source lang="php">
<?php ///////////////////////////////////////////////////// // Copyright(c) 2015,父母邦，帮父母 // 日 期：2015-1-15 // 作 者：卢少锦 // E-mail :shaojin.lu@linktone.com // 文件名：lottery.php // 创建时间:下午12:03:22 // 编 码：UTF-8 // 摘 要:一个抽奖配置类，利用打地鼠游戏的思路，每次将1000个数字的数组，随机分配对应的 // 奖品对应，然后随机一个数字，对应的数组中获得了啥 /////////////////////////////////////////////////////
class CI_Lottery{ protected $baseFactor=1000;//数值扩大因子 protected $randArray=array();//随机数组 protected $awardArray=array();//奖项数组 protected $oddArray=array();//概率数组 protected $luckNum=0;//幸运数字
/** * 构造函数 */ public function __construct(){
}
/** * 设置方法因子 * @param number $factor */ public function setBaseFactor($factor=1000){ $this->baseFactor=$factor; }
/**
* 添加奖项配置
* @param string $awardName
* @param number $awardOdd
* @param string $desc
*/
public function addAward($awardName,$awardOdd,$desc){
//判断奖品设置是否重复
if(isset($this->awardArray[$awardName])){
$this->showTips("奖项设置[$awardName]重复");
}
$this->awardArray[$awardName]=array("odd"=>$awardOdd,"desc"=>$desc);
}
/** * 奖项初始化 */ public function initAward(){ $totalSum=0;//汇总的和 foreach ($this->awardArray as $awardName=>$awardInfo){ $totalSum+=$awardInfo['odd']*$this->baseFactor;//扩大一个系数 } //再计算每种奖品所占用的概率空间 foreach ($this->awardArray as $awardName=>$awardInfo){ $this->oddArray[$awardName]=round(($awardInfo['odd']*$this->baseFactor)/$totalSum,3); } //开始针对每种奖品的几率进行数组的填充 $startSpace=0; foreach($this->oddArray as $awardName=>$odd){ //计算结束的空间 $endSpace=$startSpace+$odd*$this->baseFactor; //需要在这个地方进行修正下，这样会影响到最后一个配置奖品的几率，但是不会影响太大，可以忽略 if($endSpace>$this->baseFactor){ $endSpace=$this->baseFactor; } //开始填充空间 for ($index=$startSpace;$index<$endSpace;$index++){ $this->randArray[$index]=$awardName;//配置这个位置的奖品 } //更改起始位置 $startSpace=$endSpace; } }
/** * 运行抽奖程序 */ public function runLottery(){ //开始进行随机,这样更加干扰,随机性更大 shuffle($this->randArray); //开始选择一个幸运数字 $luckyNum=mt_rand(0, ($this->baseFactor-1)); $this->luckNum=$luckyNum; return $this->randArray[$luckyNum]; }
/** * 获取幸运数字 * @return number */ public function getLuckNum(){ return $this->luckNum; }
/** * 测试程序 */ public function debug(){ echo "奖项配置:\n"; print_r($this->awardArray); echo "奖项概率:\n"; print_r($this->oddArray); echo "概率分布:\n"; print_r($this->randArray); }
/** * 提示信息 * @param string $msg */ public function showTips($msg){ echo $msg."\n";exit; }
/**
* 基准测试
*/
public function benchmark(){
$this->setBaseFactor(1000);
$this->addAward("test1","0.1","奖品1");
$this->addAward("test2","0.3","奖品2");
$this->addAward("test3","0.4","奖品3");
$this->addAward("test4","0.2","奖品4");
$this->initAward();
$testResult=array();
$num=1000;
for($i=0;$i<$num;$i++){
$result=$this->runLottery();
echo $result."\n";
$testResult[]=$result;
}
print_r(array_count_values($testResult));
}
}
?>
</source>
思考问题：如何快速高效洗牌
问题的说明：假设有一个数组，包含n个元素。现在要重新排列这些元素，要求每个元素被放到任何一个位置的概率都相等（即1/n），并且直接在数组上重排（in place）， 不要生成新的数 组。用O(n) 时间、O(1)辅助空间。 引申一下：针对一个排序好的数组，在不利用系统提供的现成函数基础上进行随机排列处理？ 这些都是很有意思的问题，通过参考资料，有人针对上述的问题提供了一种高效的算法：高效洗牌算法
伪代码：
To shuffle an array a of n elements (indices 0..n-1):
for i from n − 1 downto 1 do
j ← random integer with 0 ≤ j ≤ i
exchange a[j] and a[i]
思路说明： 从一个数组data的最末端开始设为j，然后在0-j之间产生一个随机数i,然后将data[j]与data[i]进行位置的交换，如此循环结束 具体的PHP代码实现： <source lang="PHP">
//随机算法 public function shuffle_array_fisher_yates(){ //初始化数据 $testdata=array('A',"B","C","D","E","F","G","H","I","J"); $length=count($testdata); if ( $length == 0 ) return; $index=$length; //从最后一个元素开始，每次都与随机到的一个元素进行互换 while ( --$index ) { $randnum = rand() % ($index+1); echo "randnum:$randnum\n"; $temp = $testdata[$index]; $testdata[$index] = $testdata[$randnum]; $testdata[$randnum] = $temp; } print_r($testdata); }
</source>
