第 29 期(算法-数学)：抽奖概率算法

[wingmeng]

题目：

以下面的数据为参考，编写一个抽奖算法，其中 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离散分布随机取样