最近的一個業(yè)務需求是開發(fā)一個抽獎管理功能阳似，要求在一個獎池中放一堆獎品闷堡，分別給它們設置不同的數(shù)量和概率隘膘，在獎品沒有發(fā)完的情況下，概率高的被抽中的幾率就大缚窿，反之則低棘幸。另外，概率為0的不能被抽中倦零，概率為100則一定要被抽中误续。
這里只討論下其中的核心算法的設計及一個示例函數(shù)吨悍，算法之外的系統(tǒng)控制暫不提及。
實現(xiàn)抽獎的方法應該有很多蹋嵌，沒有仔細去考察和搜索那些非常復雜的算法育瓜，這里僅做了一個簡單的假設，并在此基礎上推出后面所有的控制邏輯栽烂。
- 基本假設
假設系統(tǒng)生成一個1到100之間的隨機整數(shù)R躏仇，C為1到100之間的一個任意整數(shù)，那么R小于C的概率為C/100腺办。
暫且不去從數(shù)學上論證這個假設是否真的成立焰手，我們僅從直觀上來看，R是隨機的怀喉，它的值不論是多少书妻，取到1-100之間任意一個整數(shù)的概率都是一樣的。
但C越小躬拢，R落入0-C之間的概率也會越小躲履，所以我們大致上可以用C來控制某個獎品的概率。Good!
- 實現(xiàn)邏輯
有了上面的假設聊闯，我們就可以考慮實現(xiàn)一個獎池內不同獎品配置情況下的控制邏輯工猜。
首先我們把獎池中的獎品做一個過濾，剔除掉那些不滿足條件的獎品菱蔬，比如概率為0的篷帅、已經發(fā)完的等等。剩下的獎品都是可以被抽中的拴泌，只是概率大小不同而已犹褒。
OK，下面我們來設置一些概念弛针，以方便后面的行文叠骑。
假設有N個獎品，它們都以100為滿概率削茁，那么它們總共的概率空間為O=N*100宙枷；
如果這N個獎品的概率分別為C1,C2,C3...Cn，那么他們總共的中獎概率空間就是H=C1+C2+C3+...+Cn茧跋，因為Cn總是小于等于100慰丛，所以
H總是小于等于O。
我們把以上這些參數(shù)在后臺配置好瘾杭，當抽獎行為發(fā)生時诅病，我們讓系統(tǒng)生成一個隨機數(shù)R，1<=R<=O，那么當R<=C時贤笆，我們就認為中獎了蝇棉，否則就不中獎。Good10!
在判斷出是否中獎后芥永，我們就可以進一步判斷中了什么獎篡殷。
首先把獎品以數(shù)組形式A按概率從小到大進行排序，然后求出每個獎品在總中獎概率空間H中的中獎區(qū)間埋涧，并且把各區(qū)間的最大值保存成一個數(shù)組D板辽。
例如有a和b兩個獎品，概率分別為20和30,那么a的概率空間為20棘催，中獎區(qū)間為1-20劲弦；而b的概率空間為30，但它的中獎區(qū)間是20-50醇坝，這樣D就是(1,20,50)瓶您。
然后我們再把D從小到大排序并循環(huán)，當R小于20時纲仍，我們認為a被抽中；R小于50時贸毕，認為b被抽中郑叠。Good11!
這里有個問題，就是為什么不直接把R跟a和b的概率比較明棍，而要比較它們各自中間區(qū)間的最大值乡革？
因為我們設想的情況是，不僅某種獎品概率調大時其抽中的幾率增大摊腋，而且所有獎品的概率都調大時沸版，它們被抽中的幾率都增大。
如果直接把R跟獎品各自的概率比較兴蒸，根據我們上面的邏輯视粮，它們總的中獎空間H=2×100=200，只要R的值小于200橙凳，我們就已經認為中獎了蕾殴；但是當a和b兩種獎品的概率為99時，只有當R小于100時它們才會被抽中岛啸，R落在100到200之間將不被認為中獎钓觉，這顯然是不對的。
搞清楚了上面的邏輯坚踩，剩下的就是處理一些特殊情況了荡灾。
比如，如果某些獎品的概率為100，這就是我們之前說的存在滿概率獎品批幌。按我們的設想础锐，當有百分百中獎的獎品時，我們一定要這種獎品被抽中逼裆。
處理這個問題郁稍，我的方法是把獎品按概率分成兩組，一組是滿概率獎品胜宇，一組是非滿概率獎品耀怜。當滿概率獎品組不為空時，從中隨機取出一個作為被抽中的獎品放出桐愉，直到這些獎品被抽完财破。
到此為止整個邏輯基本結束，可以著手寫代碼了从诲。Good101!
/**
* 抽獎核心算法
* @param prize array,所有概率不為0且剩余數(shù)大于0的獎品數(shù)組
* @return array 單個獎品
* version 2015.12.21
* author thinkmad@sina.com
*/
const FULL_CHANCE = 100;
function calcPrize($prize){
if(!$prize){
return false;
}
$arr_chance = array();//所有獎品概率
$arr_delimiter = array();//中獎區(qū)間分界數(shù)組
$full_chance_prize = $nofull_chance_prize = array();//劃分滿概率和非滿概率數(shù)組
$H = 0;//中獎概率空間
//劃分滿概率和非滿概率獎品
foreach($prize as $item){
if($item['prizeChance'] >= self::FULL_CHANCE) {
$full_chance_prize[] = $item;
}else{
$nofull_chance_prize[$item['prizeID']] = $item;
}
}
//存在滿概率獎品左痢，則隨機取出一個獎品并返回
$len = count($full_chance_prize);
if($len > 0){
$r = mt_rand(0,$len-1);
return $full_chance_prize[$r];
}
//計算總概率空間O
$O = count($prize) * self::FULL_CHANCE;
//計算總中獎空間H并生成概率數(shù)組
foreach($nofull_chance_prize as $k => $v){
$H += $v['prizeChance'];
$arr_chance[$k] = $v["prizeChance"];
}
$R = mt_rand(1,$O);
if($R > $H){ //R不在中獎空間
return false;
}else{//R落在中獎空間
asort($arr_chance);
for($i = 0; $i < count($arr_chance) ; $i++){
$arr_delimiter[key($arr_chance)] = array_isum($arr_chance,0,$i+1);
next($arr_chance);
}
foreach($arr_delimiter as $key => $val){
if($R <= $val) {
return $nofull_chance_prize[$key];
}
}
}
}
/**
* 輔助函數(shù)array_isum，計算數(shù)組中i起n個數(shù)的和
* @params $input array,要計算的數(shù)組
* @params $start,int,起始位置
* @params $num,int,個數(shù)
* @return int
*/
function array_isum($input,$start,$num){
$temp = array_slice($input, $start,$num);
return array_sum($temp);
}
上面是用PHP實現(xiàn)的一個核心算法系洛，其中定義了一個常量FULL_CHANCE為100俊性。還定義了一個輔助函數(shù)array_isum，用來計算一個數(shù)組中從下標i開始n個數(shù)的和描扯。
這里面其實還有一個小小的問題定页，就是當幾種獎品都是非滿概率獎品且它們的概率相同，我們需要隨機抽出一個作為獎品放出绽诚，如果不做這個處理典徊，則會按照默認順序先把前面的獎品發(fā)完再發(fā)后面的。
Enjoy It!
