最近一次面试被问到一个概率抽奖的问题，记录一下，题目是：实现一个抽奖零碎，抽到一等奖的概率为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 < prop.length; i++) { for (let j = 0; j < prop[i]; j++){ pool.push(prize[i]) } } return pool} let newPool = generatePool(_prize, _prop) //生成此次奖池let poolLen = newPool.length //奖池容量 //抽奖let getPrize = () => { 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 < times){ func() } let res = [a, b, c, d] res.forEach((item, k) => { 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 < high){ let mid = Math.floor((low + high) / 2) if (random > _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 < times){ let cur_prize = func() switch (cur_prize){ case 'A': a++ break case 'B': b++ break case 'C': c++ break case 'D': d++ break case 'E': e++ break } } let res = [a, b, c, d, e] res.forEach((item, k) => { 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"]