最近面试被问到一个关于概率抽奖的问题，记录一下，题目是：实现一个抽奖系统，中头奖的概率是10%，中奖的概率是二等奖20%，三等奖概率30%，四等奖概率40%。写出来之后，让我写个测试代码，跑1000次，看看结果的概率是否接近。作为一个前端代码新手，遇到这种问题只能原地打，从来不写后台的逻辑~let_prize=['A','B','C','D']//Awardslet_prop=[1,2,3,4]//权重leta=0,b=0,c=0,d=0;//统计每次抽奖的次数letcount=0;//countNumberoftests//根据奖项和权重生成奖池（如果奖项少，概率简单，可以跳过这一步，直接写奖池）letgeneratePool=(prize,prop)=>{让池=[];for(leti=0;i{letrandom=Math.floor(Math.random()*poolLen)//奖池容量中的一个随机数Numberswitch(newPool[random]){case'A':a++breakcase'B':b++breakcase'C':c++中断案例'D':d++break}count++;//统计测试次数}//重复测试n次，计算概率letcomputeP=(func,times)=>{while(count{res[k]=(item/100/poolLen).toFixed(2)})returnres}//测试1000console.log(computeP(getPrize,1000))//以下是几次运行的结果，比较稳定//>["0.10","0.20","0.32","0.38"]//>["0.09","0.20","0.29","0.41"]//>["0.08","0.20","0.29","0.42"]//>["0.10","0.18","0.30","0.42"]写下来，发现自己写的还是太好了。我已经尽力抽象了，但是很多功能还是不能复用。每次都需要改一些数据，但是效果还是不错的10/17/2021更新根据别人的博客（忘了在哪里看的），找到了一个更高效的算法，用离散化和二分查找实现假设抽取ABCDE的概率分别为1%、3%、6%、30%、60%为了避免像之前那样生成一个大数组Pool，我们直接取边界值来讨论会更方便。从1-100的正整数中随机选择一个数字。如果得到1，则奖励A。2、3、4为奖励B，以此类推，我们只需要判断生成的随机数在哪个区间即可。这里我们可以从小到大的顺序搜索这个随机数到大型或二进制搜索。这里使用二进制积分可以将时间复杂度降低到logN，通过判断区间输出一个奖品，然后重复计算概率let_prize=['A','B','C','D','E']let_prop=[1,4,10,40,100]//累积分布函数leta=0,b=0,c=0,d=0,e=0;让计数=0；letgetPrize=()=>{letrandom=Math.ceil(Math.random()*100)//从1-100生成正整数//二进制搜索letlow=0lethigh=_prop.length-1count++;while(low_prop[mid]&&random<=_prop[mid+1]){return_prize[mid+1]}elseif(random>_prop[mid+1]){low=mid}else{high=mid}}return_prize[0]}letcomputeP=(func,times)=>{while(count{res[k]=(item/times).toFixed(3)})returnres}console.log(computeP(getPrize,1000))//>["0.012","0.033","0.056","0.300","0.599"]//>[“0.015”，“0.026”，“0.045”，“0.308”，“0.606”]
