抽獎活動演算法

A. 怎樣根據物品價值制定抽獎概率

抽獎概率-三種演算法一、逢「幾」中獎逢「幾」中獎，即通過預估抽獎人數和獎品數來判斷，「幾」=(抽獎人數/獎品數)*N。這是一種最簡單抽獎演算法，適合抽獎人數眾多，而且互相無聯系的情況。如今大為流行的微博轉發得獎就常常使用這種演算法，即根據轉發次數來決定獎品歸屬，透明而且具有激勵性。當然這個「幾」也不單只次數，還可能是時間，逢某個時間點就可以抽中，不過這種方案可能產生無人中獎和很多人中獎的情況，時間點的安排很關鍵！這個時間點一旦公布出去，那就是秒殺，霍霍。。逢「幾」中獎有很多弊端，但是非常簡單，很容易實現，被很多抽獎活動所採用，有些會公布抽獎規則，激勵抽獎，有些則不會公布，其實後台運行的可能也是這個演算法，簡單高效又不失公平。在信息不透明的情況下，鬼知道你是第幾個抽獎的，哈哈。。二、概率抽獎所謂概率抽獎是最容易想到的抽獎演算法了，這個概率可以是一成不變的，也可以是一直在變化調整的，最難的是採用多大的概率，何種情況下採用何種概率。這個也沒有什麼通用的方案，不同的應用場景，所用的概率演算法不同。下面介紹一種演算法，根據獎品的過期日期來計算它當前時間的中獎率，當時間逐漸接近獎品過期時間時，中獎概率會逐漸發生變化，如果設為1表示線性衰減，2為平方衰減，以此類推。

B. 有哪些經典的抽獎演算法

常見的有兩種

第一類是常見的有等級的抽獎活動，如一等、二等、三等獎等等

java">//分別為一、二、三、四等將的獎品數量，最後一個為未中獎的數量。
privatestaticfinalInteger[]lotteryList={5,10,20,40,100};

privateintgetSum(){
intsum=0;
for(intv:lotteryList){
sum+=v;
}
returnsum;
}

privateintgetLotteryLevel(){
Randomrandom=newRandom(System.nanoTime());
intsum=getSum();
for(inti=0;i<lotteryList.length;++i){
intrandNum=Math.abs(random.nextInt())%sum;
if(randNum<=lotteryList[i]){
returni;
}else{
sum-=lotteryList[i];
}
}
return-1;
}

第二類是不分等級的抽獎活動，僅需要參與人數與獎品總數，各獎品中獎概率相等。

//另一種抽獎演算法，用於公司抽獎，即總參與人數與獎品數固定。
=75;
privatestaticfinalinttotal=175;
privatestaticSet<Integer>lotterySet=newHashSet<Integer>();
static{
for(inti=1;i<=lotteryNum;++i){
lotterySet.add(total*i/lotteryNum);
}
}
privateintgetLotteryNum2(){
Randomrand=newRandom(System.nanoTime());
intrandNum=Math.abs(rand.nextInt())%total;
if(lotterySet.contains(randNum)){
returnrandNum*lotteryNum/total;
}
return-1;
}

C. 抽獎活動的中獎幾率是怎麼算的

中獎的概率就是用獎品的數量除以參與抽獎的總人數，得到的結果就是抽到該獎品的中獎概率。如果參與抽獎人數有800個人，獎品有5件，那麼中獎的概率就是：5/800=0.625%。

在國內彩市中頭獎概率最低的是大樂透玩法，概率僅為2142萬分之一。其次是雙色球的頭獎中出概率，為1772萬分之一。

而美國最熱門的兩大彩種之一，兆彩（超級百萬）的中頭獎概率為1.75億分之一，堪稱史上難度最大的彩票玩法，也就是說，美國兆彩中頭獎的概率僅為雙色球的1/9.86。

概率，亦稱「或然率」，它是反映隨機事件出現的可能性大小。隨機事件是指在相同條件下，可能出現也可能不出現的事件。

例如，從一批有正品和次品的商品中，隨意抽取一件，「抽得的是正品」就是一個隨機事件。設對某一隨機現象進行了n次試驗與觀察，其中A事件出現了m次，即其出現的頻率為m/n。

經過大量反復試驗，常有m/n越來越接近於某個確定的常數（此論斷證明詳見伯努利大數定律）。該常數即為事件A出現的概率，常用P
(A) 表示。

D. 概率演算法

最近做了一個活動抽獎需求，項目需要控制預算，概率需要分布均勻，這樣才能獲得所需要的概率結果。
例如抽獎得到紅包獎金，而每個獎金的分布都有一定概率：

現在的問題就是如何根據概率分配給用戶一定數量的紅包。

演算法思路 ：生成一個列表，分成幾個區間，例如列表長度100，1-40是0.01-1元的區間，41-65是1-2元的區間等，然後隨機從100取出一個數，看落在哪個區間，獲得紅包區間，最後用隨機函數在這個紅包區間內獲得對應紅包數。

時間復雜度 ：預處理O(MN)，隨機數生成O(1)，空間復雜度O(MN)，其中N代表紅包種類，M則由最低概率決定。

優缺點 ：該方法優點是實現簡單，構造完成之後生成隨機類型的時間復雜度就是O(1)，缺點是精度不夠高，佔用空間大，尤其是在類型很多的時候。

演算法思路 ：離散演算法通過概率分布構造幾個點[40, 65, 85, 95,100]，構造的數組的值就是前面概率依次累加的概率之和。在生成1~100的隨機數，看它落在哪個區間，比如50在[40,65]之間，就是類型2。在查找時，可以採用線性查找，或效率更高的二分查找。

演算法復雜度 ：比一般演算法減少佔用空間，還可以採用二分法找出R，這樣，預處理O(N)，隨機數生成O(logN)，空間復雜度O(N)。

優缺點 ：比一般演算法佔用空間減少，空間復雜度O(N)。

演算法思路 ：Alias Method將每種概率當做一列，該演算法最終的結果是要構造拼裝出一個每一列合都為1的矩形，若每一列最後都要為1，那麼要將所有元素都乘以5（概率類型的數量）。

此時會有概率大於1的和小於1的，接下來就是構造出某種演算法用大於1的補足小於1的，使每種概率最後都為1，注意，這里要遵循一個限制：每列至多是兩種概率的組合。

最終，我們得到了兩個數組，一個是在下面原始的prob數組[0.75,0.25,0.5,0.25,1]，另外就是在上面補充的Alias數組，其值代表填充的那一列的序號索引，（如果這一列上不需填充，那麼就是NULL），[4,4,0,1,NULL]。當然，最終的結果可能不止一種，你也可能得到其他結果。

舉例驗證下，比如取第二列，讓prob[1]的值與一個隨機小數f比較，如果f小於prob[1]，那麼結果就是2-3元，否則就是Alias[1]，即4。

我們可以來簡單驗證一下，比如隨機到第二列的概率是0.2，得到第三列下半部分的概率為0.2 * 0.25，記得在第四列還有它的一部分，那裡的概率為0.2 * (1-0.25)，兩者相加最終的結果還是0.2 * 0.25 + 0.2 * (1-0.25) = 0.2，符合原來第二列的概率per[1]。

演算法復雜度 ：預處理O(NlogN)，隨機數生成O(1)，空間復雜度O(2N)。

優缺點 ：這種演算法初始化較復雜，但生成隨機結果的時間復雜度為O(1)，是一種性能非常好的演算法。