作者:水墨寒
掘金ID:https://juejin.cn/user/3051900006317549
在解决算法问题中我们会经常遇到要求均等概率的问题, 以leetcode 470....⚠️ 不讨论最优解,只讨论算法思路 看到均等概率的问题, 我们最先要想到转成2进制来处理,思路是让均等概率转换成均等概率出现0和1, 再由 0 和 1 ,增加位数来处理均等概率的其他数。...第一步转化二进制函数
Rand7() 的结果是均等概率 出现 1,2,3,4,5,6 拆解下就是 均等概率出现 1,2,3 和 4,5,6 当出现 1,2,3 的时候返回 0 ,当出现 4,5,6...1 : 0
}
现在我们有了过渡函数 Rand2 , 那么我们使用随机生成4位二进制数那么我就会得到 一个 均等生成 0 ~ 15 的函数
function Rand15(): number {...给一个随意函数f,以P概率返回 0 , 以 1-P 的概率返回1 这是你唯一可以使用的随机机制,如何实现等概率返回 0 和 1
思路还是用二进制升位的方式, 0 的概率是 P 1 的概率是 1- P
可以得出