首页 > 编程语言 >java实现按比重抽奖

java实现按比重抽奖

时间:2024-05-20 18:07:37浏览次数:65  
标签:奖品 抽奖 java Prize 权重 int weight 比重 prizes

java实现按比重抽奖

目录

方案

对于按比重抽奖的更优方案,可以考虑以下几种方法:

  1. 轮盘抽奖(Roulette Wheel Selection)
    • 原理:想象一个旋转的轮盘,每个奖品占据轮盘上与其权重成比例的区域。随机选择一个点并让其“落下”,落在哪个奖品区域就选中哪个奖品。
    • 实现:可以通过累加权重来模拟轮盘,然后生成一个随机数来决定指针落在哪个区间。
    • 优点:直观易懂,模拟了真实世界的轮盘抽奖。
    • 缺点:在奖品和权重非常多时,性能可能不是最优的。
  2. Alias Method(别名采样法)
    • 原理:通过预处理步骤,为每个奖品分配一个或多个“别名”,使得每个奖品或别名被选中的概率都是1/n(n是奖品的数量)。在抽奖时,随机选择一个奖品或别名即可。
    • 实现:较为复杂,需要进行预处理来构建别名表。但一旦构建完成,抽奖操作的时间复杂度就是O(1)。
    • 优点:抽奖操作非常快,适用于频繁抽奖的场景。
    • 缺点:构建别名表的过程可能比较耗时,且当奖品或权重发生变化时需要重新构建。
  3. Binary Search(二分查找)
    • 原理:将奖品按照权重排序(可以使用平衡二叉搜索树如红黑树或AVL树来维护排序),然后生成一个随机数,并使用二分查找来找到对应的奖品。
    • 实现:需要维护一个排序的奖品列表或树结构。抽奖时,通过二分查找找到随机数对应的奖品。
    • 优点:在奖品数量较多时,性能通常优于简单的累加权重方法。
    • 缺点:需要维护排序结构,当奖品或权重发生变化时需要重新排序。

轮盘抽奖

示例

import lombok.Data;
import org.apache.commons.collections4.CollectionUtils;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.stream.Collectors;

@Data
class Prize {
    String name;
    int weight; // 权重(比重)  

    public Prize(String name, int weight) {
        this.name = name;
        this.weight = weight;
    }

    // 可以添加getter和setter方法...  
}

public class LotterySystem {

    public static void main(String[] args) {
        List<Prize> prizes = new ArrayList<>();
//        prizes.add(new Prize("奖品A", 10)); // 假设奖品A的权重是10
//        prizes.add(new Prize("奖品B", 10)); // 假设奖品A的权重是10
//        prizes.add(new Prize("奖品C", 20)); // 假设奖品B的权重是20
//        prizes.add(new Prize("奖品D", 20)); // 假设奖品B的权重是20
//        prizes.add(new Prize("奖品E", 30)); // 假设奖品C的权重是30
//        prizes.add(new Prize("奖品F", 10)); // 假设奖品A的权重是10

        // 计算总权重  
        int totalWeight = 0;
        for (Prize prize : prizes) {
            totalWeight += prize.weight;
        }

        // 执行抽奖  
        List<Prize> resList = new ArrayList<>();
        for (int i = 0; i < 1000; i++) {
            Prize winningPrize = drawLottery(prizes, totalWeight);
            System.out.println("恭喜您获得:" + winningPrize.name);
            resList.add(winningPrize);
        }
        Map<String, List<Prize>> map = resList.stream().collect(Collectors.groupingBy(Prize::getName));
        for (Map.Entry<String, List<Prize>> entry : map.entrySet()) {
            System.out.println(entry.getKey() + "-" + entry.getValue().size());
        }
    }

    public static Prize drawLottery(List<Prize> prizes, int totalWeight) {
        if (CollectionUtils.isEmpty(prizes) || totalWeight < 1) {
            return null;
        }
        // 打乱奖品列表,确保权重计算不会受到原始顺序的影响  
        Collections.shuffle(prizes);

        // 随机选择一个数字  
        Random random = new Random();
        int randomNumber = random.nextInt(totalWeight) + 1; // 生成1到totalWeight之间的随机数  

        // 根据随机数选择奖品  
        int currentWeight = 0;
        for (Prize prize : prizes) {
            currentWeight += prize.weight;
            if (randomNumber <= currentWeight) {
                return prize;
            }
        }
        // 如果所有奖品都没有被选中(理论上不应该发生),则返回一个默认奖品或抛出异常  
        return null; // 或抛出异常  
    }
}

关键点

  • 随机数生成:生成的随机数是介于1和总权重之间的整数,它代表了“抽奖指针”的位置。

  • 权重累加:通过累加奖品的权重,我们可以确定每个奖品对应的权重范围。随机数落在哪个范围内,就说明抽中了哪个奖品。

Binary Search(二分查找)

import java.util.Random;
  
public class WeightedLottery {  
  
    // 奖品类,包含奖品名称和权重  
    static class Prize {  
        String name;  
        int weight;  
  
        Prize(String name, int weight) {  
            this.name = name;  
            this.weight = weight;  
        }  
  
        @Override  
        public String toString() {  
            return "Prize{" +  
                    "name='" + name + '\'' +  
                    ", weight=" + weight +  
                    '}';  
        }  
    }  
  
    // 根据奖品列表和权重计算累积权重数组  
    static int[] calculateCumulativeWeights(Prize[] prizes) {  
        int totalWeight = 0;  
        for (Prize prize : prizes) {  
            totalWeight += prize.weight;  
        }  
  
        int[] cumulativeWeights = new int[prizes.length];  
        cumulativeWeights[0] = prizes[0].weight;  
        for (int i = 1; i < prizes.length; i++) {  
            cumulativeWeights[i] = cumulativeWeights[i - 1] + prizes[i].weight;  
        }  
  
        // 归一化累积权重(可选),使最后一个累积权重为totalWeight  
        for (int i = 0; i < cumulativeWeights.length; i++) {  
            cumulativeWeights[i] = cumulativeWeights[i] * totalWeight / cumulativeWeights[cumulativeWeights.length - 1];  
        }  
  
        return cumulativeWeights;  
    }  
  
    // 二分查找确定中奖的奖品  
    static Prize binarySearchForPrize(Prize[] prizes, int[] cumulativeWeights, int randomNumber) {  
        int left = 0;  
        int right = prizes.length - 1;  
  
        while (left <= right) {  
            int mid = left + (right - left) / 2;  
            if (randomNumber < cumulativeWeights[mid]) {  
                right = mid - 1;  
            } else {  
                if (mid == prizes.length - 1 || randomNumber < cumulativeWeights[mid + 1]) {  
                    return prizes[mid];  
                }  
                left = mid + 1;  
            }  
        }  
  
        // 如果没有找到(理论上不会发生,除非randomNumber超出范围),则返回null或抛出异常  
        return null;  
    }  
  
    public static void main(String[] args) {  
        Prize[] prizes = {  
                new Prize("奖品A", 1),  
                new Prize("奖品B", 2),  
                new Prize("奖品C", 3)  
        };  
  
        int[] cumulativeWeights = calculateCumulativeWeights(prizes);  
  
        Random random = new Random();  
        int randomNumber = random.nextInt(cumulativeWeights[cumulativeWeights.length - 1]) + 1; // 生成一个1到总权重之间的随机数  
  
        Prize winningPrize = binarySearchForPrize(prizes, cumulativeWeights, randomNumber);  
        System.out.println("中奖奖品: " + winningPrize);  
    }  
}

标签:奖品,抽奖,java,Prize,权重,int,weight,比重,prizes
From: https://www.cnblogs.com/lyn8100/p/18202556

相关文章

  • java应用CPU占用率过高排查
    1.背景服务器CPU使用率告警,紧急排查。2.排查思路2.1top查看各进程的CPU占用率top查到进程的pid2.2查看该进程的所有线程top-Hp<pid>发现大量的GCtaskthread#的cpu使用超过90%,定位到时频繁GC导致,可能是内存不足引起#jstat监控GC情况,其中:<vmid> 是Java虚拟机......
  • what's the advantages of using Map over Object in JavaScript?
    what'stheadvantagesofusingMapoverObjectinJavaScript?在JavaScript中使用Map相对于Object有什么优势?prosconsdemoshttps://leetcode.com/studyplan/30-days-of-javascript/(......
  • 解决yarn打包时出现“FATAL ERROR: Reached heap limit Allocation failed - JavaScri
    1、......
  • CentOS7安装Java
    1.查看是否有安装Javarpm-qa|grepjavarpm-qa|grepjdkrpm-qa|grepgcj如果之前有安装就卸载安装rpm-qa|grepjava|xargsrpm-e--nodeps2.下载安装包https://www.oracle.com/java/technologies/downloads/#java83.上传CentOS7服务器这里我们使用的......
  • Java常用的JSON序列化与反序列化工具实践
    JSON简介:JSON(JavaScriptObjectNotation)是一种轻量级的数据交换格式,通常用于在不同系统之间传输数据。它基于JavaScript对象语法,但已成为一种独立于语言的格式。JSON数据以键值对的形式组织,易于阅读和编写。为什么要使用JSON?1.简单易用:JSON的语法简单,易于理解和编写,可以......
  • JavaScript------querySelector/querySelectorAll的使用
    1、基础语法querySelector()方法返回文档中匹配指定CSS选择器的一个元素。querySelector()方法仅仅返回匹配指定选择器的第一个元素。如果你需要返回所有的元素,请使用querySelectorAll()方法替代。属性:指定一个或多个匹配元素的CSS选择器。可以使用它们的id,类,类......
  • Java基础-转岗学习路线
    2023年初,因为公司项目的调整变化,原来的Unity项目取消了,没有其他适合的项目和岗位可以做了,公司也不进行裁员而是允许转岗,鉴于就业形势不佳以及我有机会来好好学习其他技术,于是我决定转岗Java后端开发,当然,总归还是迫于无奈,对我来说也是个不小的挑战,因为虽然做开发四年有余,有Java代码......
  • 【JAVA】BOSS系统发版艺术:构建高效、优雅的微服务部署策略
    在现代软件开发领域,微服务架构与容器化部署已迅速成为行业新趋势。微服务架构通过将应用拆分成多个小型、自治的服务单元,每个服务承担某项特定的业务功能。而容器化部署则以其轻量级和高度可移植的特性,为这些微服务的有效打包、分发和运行提供了强大支持。在这样的环境中,实现微服......
  • hdu1025java
    1:dp+二分 NlogN的复杂度2:注意road与roads区别3:注意输入不能用Scanner4:注意格式最后是要输出两个空行假设存在一个序列d[1..9]=215364897,可以看出来它的LIS长度为5。下面一步一步试着找出它。我们定义一个序列B,然后令i=1to9逐个考察这个序列。此外,我们用......
  • RabbitMQ在Java中的完美实现:从入门到精通
    哈喽,大家好,我是木头左!一、RabbitMQ简介RabbitMQ是一个开源的AMQP实现,服务器端用Erlang语言编写,支持多种客户端,如:Python、Ruby、.NET、Java、JMS、C、PHP、ActionScript、XMPP、STOMP等,支持AJAX。用于在分布式系统中存储转发消息,在易用性、扩展性、高可用性等方面表现不俗。本......