Repository navigation
第 29 期(算法-数学)：抽奖概率算法 #32
Description
题目：
以下面的数据为参考，编写一个抽奖算法，其中 chance 字段为当前奖品的获奖概率（0.01-1）
const awards = [
{name: '智能平衡车', chance: 0.12},
{name: '华为 P30 Pro手机', chance: 0.06},
{name: '蓝牙手环', chance: 0.3},
{name: '100元购物卡', chance: 0.5},
{name: 'Mac Book Pro', chance: 0.02}
];参考答案：
初步思路：将所有奖品的概率转换为百分数（即 chance * 100），然后按照各自的占比生成一个100长度的数组：
- 1-12 项是智能平衡车区间
- 13-18 项是华为 P30 Pro手机区间
- 19-48 项是蓝牙手环区间
- 49-98 项是100元购物卡区间
- 99-100 项是Mac Book Pro区间
然后从1-100生成一个随机数，看落在哪个区间即可确定抽奖结果。
进阶：上面的思路空间复杂度较高，通过观察可以发现，生成的5个概率区间有5个临界参考点，即 12, 18, 48, 98, 100，换句话说，我们只需将获取的随机数按这些参考点依次进行比较，找到第一个比随机数大的参考点即可确定结果，而无需划分100长度的数组。
let arr = awards.map(it => ({ name: it.name, chance: it.chance * 100}))
.map((it, idx, array) => {
if (idx > 0) {
it.chance = it.chance + array[idx - 1].chance; // 累加上一个临界参考点
}
return it;
});
// 生成 1-99 随机数
let rdmNum = Math.floor(Math.random() * 99) + 1;
for (let award of arr) {
if (award.chance > rdmNum) {
console.log(`你抽中了 ${award.name}`);
break;
}
} 参考资料：Alias Method离散分布随机取样
Activity