Java實現(xiàn)游戲抽獎的算法

Java開發(fā)游戲抽獎算法主要有隨機數(shù)一一對應、離散法Alias算法等。

一、隨機數(shù)一一對應

1、隨機數(shù)算法原理：

將n個獎品編號0~n-1，其中各類獎品的概率通過其數(shù)量體現(xiàn)，最后程序產(chǎn)生0~n-1之間的隨機數(shù)便是抽中的獎品編號。

例如：蘋果手機概率1%，網(wǎng)站會員20%，折扣券20%，很遺憾59%。編號0是蘋果手機，1~20是會員，21~40是折扣券，41~100是很遺憾。產(chǎn)生的隨機數(shù)落在哪個區(qū)間就代表那個獎品被抽中。

2、隨機數(shù)存在問題

a總數(shù)N快速膨脹

概率通過數(shù)量來體現(xiàn)在各個獎品概率較大的情況下，總數(shù)n可以較小。但如果在精度很高的情況下，總數(shù)必須按比例成倍擴大。

b平衡性影響

在Java中，Math.random()方法本身基本可以保證大量測試的情況下避免高重復，且概率分布比較平均。但是需要注意的是，該方法默認返回0-1之間的數(shù)據(jù)。在當前算法中，必須擴大指定倍數(shù)并且強制使用int進行類型轉(zhuǎn)換。在這樣的擴大和轉(zhuǎn)換過程中，必然會對數(shù)據(jù)精度進行修改，轉(zhuǎn)換后的數(shù)據(jù)也不能保證概率分布平均。該算法實際可能達不到預期的概率要求。

c算法復雜度

數(shù)據(jù)準備階段，為每個獎品確定編號與獎品信息的關系集合需要O(n);產(chǎn)生隨機數(shù)階段并轉(zhuǎn)換，O(1);從集合中查找，不同的數(shù)據(jù)結構實現(xiàn)不同，最差需要O(n);

二、離散法

1、離散法算法原理高數(shù)幾何概形的思想

將獎品集合的概率劃分區(qū)段放入數(shù)組中。概率區(qū)段通過該概率累計相加確定。利用隨機數(shù)產(chǎn)生隨機概率，加入數(shù)組并排序，該數(shù)據(jù)的下標，就是對應獎品集合中獎品的索引。例如，獎品的集合有X1,X2,X3,X4，對應概率為P1=0.2,P2=0.2,P3=0.3,P4=0.3。

那么，產(chǎn)生的概率區(qū)段數(shù)組為[0.2，0.4，0.7，1.0]。

0.2以下代表X1，0.2~0.4代表X2，0.4~0.7代表X3，0.7~1代表X4。

這樣，如果產(chǎn)生一個隨機概率為0.5，加入數(shù)組排序后，0.4~0.7之間，是X3相加所在的概率區(qū)間，返回index=2。

由于區(qū)間分布的確定是按照X集合順序的，所以該索引也正是X3在原集合中的索引。

2、離散法特點

利用幾何概形，概率數(shù)組分布在0到1之間，不再需要擴大倍數(shù)和取整操作，基本可以保證概率平均分布，避免大量重復的情況概率分配的排序過程，可以使用java默認的排序工具類，也可以自己實現(xiàn)。保證時間復雜度最小。

3、離散法復雜度

準備階段，O(m)。m遠小于n，因為概率只有幾個，不會大量膨脹。

產(chǎn)生隨機數(shù)，O(1)

排序取下標，根據(jù)排序算法，O(logn)即可實現(xiàn)

取值，根據(jù)下標，O(1)；

三、Alias算法

Alias算法解決隨機類型概率問題，對于開發(fā)抽獎活動的任務來說，獎品一般放置在數(shù)據(jù)庫中，而概率分為一下兩種：

1、所有獎項的概率和為1，也就是說本次活動所有參與人員都會中獎，中獎的等級隨獎品的概率而定；

2、所有的獎項的概率和小于1，也就是說存在未中獎的情況，其實這種情況也可以歸結為第一種，將剩余的概率歸到未中獎事件上，然后再將未中獎看做一個獎項，這種情況就和第一種相似。

以上就是關于Java開發(fā)游戲抽獎算法隨機數(shù)、離散法、Alias算法的介紹，希望對您有所幫助。