百层高楼玻璃碎

这其实是求最坏情况下的最优解

一些分析可以看：https://www.zhihu.com/question/31855632
这幅图其实已经讲明了：

三人三鬼把河过

链接

链接

概率为峰-1

原文链接：https://blog.csdn.net/weixin_41888257/article/details/107589772

int random_0_1()
{
    int i = RANDOM();
    int j = RANDOM();
    int result;
    while (true)
    {
        if (i == 0 && j == 1)
        {
            result = 0;
            break;
        }
        else if (i == 1 && j == 0)
        {
            result = 1;
            break;
        }
        else
            continue;
    }
    return result;
}

概率为峰-2

import random
class Solution:
    def random_index(self):
        # """随机变量的概率函数"""
        # 参数rate为list<int>
        # 返回概率事件的下标索引
        # 这是一个10%概率产生0，90%概率产生1的生成器
        rate = [1, 9]
        start = 0
        index = 0
        randnum = random.randint(1, sum(rate))
        for index, scope in enumerate(rate):
            start += scope
            if randnum <= start:
                break
        return index
    def Rand1(self):
        # 1. 等概率生成 0，1
        i1 = self.random_index()
        i2 = self.random_index()
        if i1 == 0 and i2 == 1:
            return 1
        elif i1 == 1 and i2 == 0:
            return 0
        else:
            return self.Rand1()
        return -1
    def Rand2(self, n: int):
        # 2. 以 1/N 的概率返回 1~N 之间的数
        # int(res, 2) 表示把 str 类型的二进制转成十进制 int('101',2) == 5
        k = len(bin(n)[2:])  # k = 1 + np.log2(n)
        print("k:", k)       # 10
        res = ''
        for i in range(k):
            res += str(self.Rand1())
        if int(res, 2) > n:
            return self.Rand2(n)
        else:
            return int(res, 2)
    def Rand3(self, n: int):
        # 3. 以 1/N 的概率返回 1~N 之间的数
        # (1<<i) 表示 1 * 2^i
        import numpy as np
        result = 0
        k = 1 + np.log2(n)
        print("k:", int(k))   # 10
        for i in range(0, int(k)):
            if self.Rand1() == 1:
                result |= (1<<i)
        if result > n:
            return self.Rand3(n)
        return result
if __name__ == '__main__':
    solution = Solution()
    rand1 = []
    for i in range(20):
        rand1.append(solution.Rand1())
    print(rand1)
    rand2 = []
    for i in range(10):
        rand2.append(solution.Rand2(999))
    print(rand2)
    rand3 = []
    for i in range(10):
        rand3.append(solution.Rand3(999))
    print(rand3)

概率为峰-3

int rand7()
{
    int x = 0;
    do
    {
        x = 5 * (rand5() - 1) + rand5();
    }while(x > 21);
    return 1 + x % 7;
}

LeetCode-rand7生成rand10

public int rand10() {
    // 首先得到一个数
    int num = (rand7() - 1) * 7 + rand7();
    // 只要它还大于40，那你就给我不断生成吧
    while (num > 40)
        num = (rand7() - 1) * 7 + rand7();
    // 返回结果，+1是为了解决 40%10为0的情况
    return 1 + num % 10;
}

/**
 * The rand7() API is already defined in the parent class SolBase.
 * public int rand7();
 * @return a random integer in the range 1 to 7
 */
class Solution extends SolBase {
    public int rand10() {
        while (true){
            int num = (rand7() - 1) * 7 + rand7();
            // 如果在40以内，那就直接返回
            if(num <= 40) return 1 + num % 10;
            // 说明刚才生成的在41-49之间，利用随机数再操作一遍
            num = (num - 40 - 1) * 7 + rand7();
            if(num <= 60) return 1 + num % 10;
            // 说明刚才生成的在61-63之间，利用随机数再操作一遍
            num = (num - 60 - 1) * 7 + rand7();
            if(num <= 20) return 1 + num % 10;
        }
    }
}