分苹果问题

有1000个苹果，分别装在10个箱子里。任意给出1到1000之间的一个整数，都可以用某几个箱子中的苹果数量相加获得此数。

解析：

这道题的本质其实是考察你对位和二进制的理解。想象一下，为什么一个 32bit 的二进制数（无符号）可以表示 0 ～ 2^32 - 1 中的任意整数？

假设有一个 10bit 的二进制数 X，其范围为 0000000000 ~ 1111111111 之间，可以表示 0 ～ 1023 之内的所有整数。

根据二进制转十进制的规则，对于 X 而言，其值是由其每一位上的值乘以2的n-1次方的和，其中 n 是这一位在第几位（从后往前）。

所以我们应该需要有 0b1, 0b10, 0b100, 0b1000, 0b10000, 0b100000, 0b1000000, 0b10000000, 0b100000000, 0b1000000000 这几个数字就可以表示 0 ～ 1023 的任意数字了。但是对于本题来说，我们只需要表示 1 ～ 1000，而我们的苹果总数也只有 1000 个，所以最后一个数字就不需要 0b1000000000 这么多，而是将剩余的苹果都放入最后的箱子即可

所以本题的答案就是 1, 2, 4, 8, 16, 32, 64, 128, 256, 489

随机数问题

有一个随机数生成器A，其返回的结果为 0 的概率是X，为 1 的概率是 1-X，请实现一个随机数生成器B，其返回的结尾为0的概率和为1的概率均为 0.5

解析：

这道题是一道简单的概率数学题，对于随机数生成器A，其调用一次的结果为 0 的概率是 X，为 1 的概率是 1-X。那么如果连续调用两次随机数生成器A呢？其返回值有以下四种情况：

P(两次都返回0) = X * X
P(两次都返回1)= (1-X) * (1-X)
P(第一次返回0，第二次返回1) = X * (1-X)
P(第一次返回1，第二次返回0) = (1-X) * X

很容易发现，对于后两种情况，其概率是相同的，那么我们就可以对这两种情况作为区分，比如如果第一次返回0，第二次返回1，则返回0；如果第一次返回1，第二次返回0，则返回1；对于其他情况就需要重新获取。

对应的伪代码如下：

1
func RandBNext() int {
2
    n1, n2 := RandANext(), RandANext()
3

4
    if n1 == 0 && n2 == 1 {
5
        return 0
6
    } else if n1 == 1 && n2 == 0 {
7
        return 1
8
    }
9

10
    return RandBNext()
11
}

给定方法 rand7 可生成 [1,7] 范围内的均匀随机整数，试写一个方法 rand10 生成 [1,10] 范围内的均匀随机整数。

本题来自于 Leetcode 470. 用 Rand7() 实现 Rand10()

对于本题来说，由于其希望用一个小的范围的随机数生成一个大范围的随机数，我们可以考虑使用多次随机的方法。

现在我们假设有一个 7 进制数字 X，其只有两位，X ₇ = AB，将 7 进制数转换成 10 进制数就可以得到 X 的范围为 0 ～ 48，并且 X = 7 * A + B，对于 A 和 B 可以由 rand7() - 1 来生成，那么我们就可以用两次生成的 rand7() - 1 来组合表示 0 ~ 48 内的任意整数，且概率均匀，而我们题目中需要的是 [1, 10]，所以可以采用拒绝采样的方式，如果 X 在 0 ～ 39 的范围，则保留，如果在 40 以上则重新生成。这样我们就可以对 X 进行 mod 10 操作，最终生成的就是 0 ～ 9 的均匀的随机整数，所以最后还需要 + 1

所以这道题的代码如下：

1
func rand10() int {
2
    A := rand7() - 1
3
    B := rand7() - 1
4
    X := A * 7 + B
5

6
    if X >= 40 {
7
        return rand10()
8
    }
9
    return X % 10 + 1
10
}

目录

分苹果问题

随机数问题