作者:mobiledu2502913165 | 来源:互联网 | 2023-08-29 19:44
最近一次面试被问到一个概率抽奖的问题,记录一下,题目是:实现一个抽奖零碎,抽到一等奖的概率为10%,二等奖的概率为20%,三等奖的概率为30%,四等奖的概率为40%。
最近一次面试被问到一个概率抽奖的问题,记录一下,题目是:实现一个抽奖零碎,抽到一等奖的概率为10%,二等奖的概率为20%,三等奖的概率为30%,四等奖的概率为40%。
写进去之后,又让我写一个测试代码,跑1000次,看后果概率是否靠近。
作为前端入门的代码萌新,遇到这种问题,只能临场发挥,素来没写过后盾的逻辑~
let _prize = ['A','B','C','D'] //奖项
let _prop = [1, 2, 3, 4] //权重
let a = 0, b = 0, c = 0, d = 0; //统计抽到每个奖的次数
let count = 0; //统计测试次数
//依据奖项和权重生成奖池(如果奖项少,概率简略,能够不必这一步,间接手写奖池)
let generatePool = (prize, prop) => {
let pool = [];
for (let i = 0; i {
let random = Math.floor(Math.random() * poolLen) //奖池容量里的一个随机数
switch (newPool[random]){
case 'A':
a++
break
case 'B':
b++
break
case 'C':
c++
break
case 'D':
d++
break
}
count++; //统计测试次数
}
//反复测试n次,并计算概率
let computeP = (func, times) => {
while (count {
res[k] = (item/100/poolLen).toFixed(2)
})
return res
}
//测试1000次
console.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] //累计散布函数
let a = 0, b = 0, c = 0, d = 0, e = 0;
let count = 0;
let getPrize = () => {
let random = Math.ceil(Math.random() * 100) //生成1-100的正整数
//二分查找
let low = 0
let high = _prop.length - 1
count++;
while (low _prop[mid] && random <= _prop[mid + 1]){
return _prize[mid + 1]
} else if (random > _prop[mid + 1]){
low = mid
} else {
high = mid
}
}
return _prize[0]
}
let computeP = (func, times) => {
while (count {
res[k] = (item/times).toFixed(3)
})
return res
}
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"]