关于javascript:Javascript实现概率抽奖算法及改进方案

最近一次面试被问到一个概率抽奖的问题，记录一下，题目是： 实现一个抽奖零碎，抽到一等奖的概率为 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"]