专业网站建设出售,网页版微信登录入口官网,免费的ai作图软件,杭州网站备案要多久常用抽奖算法对比基础的游戏抽奖算法通常要求实现在指定奖品的集合中#xff0c;每个奖品根据对对应概率进行抽取。个人了解的主要有以下几中抽奖算法#xff1a;随机数一一对应算法思想这种算法思想最为简单。将n个奖品编号0 - N-1#xff0c;其中各类奖品的概率通过其数量…常用抽奖算法对比基础的游戏抽奖算法通常要求实现在指定奖品的集合中每个奖品根据对对应概率进行抽取。个人了解的主要有以下几中抽奖算法随机数一一对应算法思想这种算法思想最为简单。将n个奖品编号0 - N-1其中各类奖品的概率通过其数量体现最后程序产生0~n-1之间的随机数便是抽中的奖品编号。例如苹果手机概率1%网站会员20%折扣券20%很遗憾59%。这样编号0是苹果手机1-20是会员21-40是折扣券41~100是 很遗憾。产生的随机数落在那个区间就代表那个奖品被抽中。存在问题1、总数N快速膨胀概率通过数量来体现在各个奖品概率较大的情况下总数n可以较小。但如果在精度很高的情况下总数必须按比例成倍扩大。例如所有奖品概率都是10%那么n只需要取10就可以。但是如果某个奖品概率是0.01%按照这种算法总数要扩大到100*100。2、平衡性影响在Java中Math.random()方法本身基本可以保证大量测试的情况下避免高重复且概率分布比较平均。但是需要注意的是该方法默认返回0-1之间的数据。在当前算法中必须扩大指定倍数并且强制使用int进行类型转换。在这样的扩大和转换过程中必然会对数据精度进行修改转换后的数据也不能保证概率分布平均。因此该算法实际可能达不到预期的概率要求。3、算法复杂度数据准备阶段为每个奖品确定编号与奖品信息的关系集合需要O(n);产生随机数阶段并转换O(1);从集合中查找不同的数据结构实现不同最差需要O(n);离散法算法思想(高中数学里几何概形的思想)将奖品集合的概率划分区段放入数组中。概率区段通过该概率累计相加确定。利用随机数产生随机概率加入数组并排序该数据的下标就是对应奖品集合中奖品的索引。例如奖品的集合有X1,X2,X3,X4对应概率为P10.2,P20.2,P30.3,P40.3。那么产生的概率区段数组为[0.20.40.71.0]。0.2以下代表X10.2-0.4代表X20.4-0.7代表X30.7~1代表X4。这样如果产生一个随机概率为0.5加入数组排序后0.4~0.7之间是X3相加所在的概率区间返回index2。由于区间分布的确定是按照X集合顺序的所以该索引也正是X3在原集合中的索引。特点1、利用几何概形概率数组分布在0到1之间不再需要扩大倍数和取整操作基本可以保证概率平均分布避免大量重复的情况2、概率分配的排序过程可以使用java默认的排序工具类也可以自己实现。保证时间复杂度最小。3、复杂度准备阶段即对准备概率集合进行归一化等操作假设样本的概率个数为M个则复杂度为O(m)。m远小于方法一中的n因为概率只有几个不会大量膨胀。产生随机数O(1)排序取下标根据排序算法O(logM)即可实现取值根据下标O(1)Alias 算法这种算法对数学要求比较高没有仔细研究。感兴趣的小伙伴可以自己研究一下和我分享算法实现奖品实体类/*** 抽奖奖品实体类* author irving* since 2017年7月23日 下午9:41:33* version MARK 0.0.1*/public class Gift {private int id; //奖品Idprivate String name; //奖品名称private double prob; //获奖概率public int getId() {return id;}public void setId(int id) {this.id id;}public String getName() {return name;}public void setName(String name) {this.name name;}public double getProb() {return prob;}public void setProb(double prob) {this.prob prob;}Overridepublic String toString() {return ToStringBuilder.reflectionToString(this, ToStringStyle.JSON_STYLE);}}抽奖实现工具类/*** 抽奖工具类* 整体思想* 奖品集合 概率比例集合* 将奖品按集合中顺序概率计算成所占比例区间放入比例集合。并产生一个随机数加入其中排序。* 排序后随机数落在哪个区间就表示那个区间的奖品被抽中。* 返回的随机数在集合中的索引该索引就是奖品集合中的索引。* 比例区间的计算通过概率相加获得。* author irving* since 2017年7月23日 下午9:48:23* version MARK 0.0.1*/package com.xxx.xxx.xxx.service;import java.util.*;/*** 抽奖工具类* Author yuanyicheng* Date 7:14 上午 2020/9/9*/public class DrawUtil {public static Gift draw(List gifts) {if (null gifts || gifts.size() 0) {return null;}gifts.sort((o1, o2) - (o1.prob - o2.prob) 0 ? 1 : -1);List probLists new ArrayList(gifts.size());Double sumProb 0D;for (Gift gift : gifts) {sumProb gift.getProb();}if (sumProb 0) {return null;}// 归一化概率端点Double rate 0D;for (Gift gift : gifts) {rate gift.getProb();probLists.add(rate / sumProb);}double random Math.random();probLists.add(random);Collections.sort(probLists);int index probLists.indexOf(random);if (index 0) {return gifts.get(index);}return null;}public static void main(String[] args) {List gifts new ArrayList();Gift nothing new Gift(谢谢惠顾, 0.5D);Gift vip new Gift(XX会员1个月, 0.4D);Gift phone new Gift(手机, 0.1D);gifts.add(nothing);gifts.add(phone);gifts.add(vip);// 抽奖// Gift g draw(gifts);// 以下是测试统计Map countMap new HashMap();for (Gift gift: gifts) {countMap.put(gift.getName(), 0);}countMap.put(null, 0);for (int i0; i1000; i) {// 抽一个Gift gift draw(gifts);String name null;if (null ! gift) {name gift.getName();}int count countMap.get(name);countMap.put(name, count);}for (Map.Entry entry : countMap.entrySet()) {System.out.println(抽到entry.getKey(), entry.getValue()次);}}}/*** 奖品类*/class Gift {String name;Double prob;public Gift(String name, Double prob) {this.name name;this.prob prob;}public String getName() {return name;}public void setName(String name) {this.name name;}public Double getProb() {return prob;}public void setProb(Double prob) {this.prob prob;}}以上就是本文的全部内容希望对大家的学习有所帮助也希望大家多多支持脚本之家。
