跳转至

杂七杂八的灵活算法⚓︎

约 2137 个字 20 行代码 预计阅读时间 7 分钟 总阅读量 次

最大公因数算法⚓︎

辗转相除法：大数 a 小数 b，如果 b 已经是0，则为a，否则，返回 (b , a % b) 的结果。

def gcd(a, b):
    if b == 0: return a 
    else: return gcd(b, a % b)

复杂度 \(O(\log(\max(a,b)))\)

蓄水池采样⚓︎

对于很大的一个数据流，采样K个元素，需要保证每个元素被选中的概率都是一样的。

  1. 对于前 K 个元素，直接放入蓄水池；
  2. 对于后续的所有元素，假设其下标为 i，则以概率 k / i 判断是否选中。
import random

def reservoir_sampling(stream, k):
    # 初始化一个大小为k的数组reservoir
    reservoir = [0]*k

    # 前k个元素直接放入reservoir
    for i in range(k):
        reservoir[i] = stream[i]

    # 对于第i个元素 (i >= k)，以概率k/i选择它
    for i in range(k, len(stream)):
        j = random.randint(0, i)
        if j < k:
            # 如果被选中，则替换掉原先蓄水池对应下标的元素即可
            reservoir[j] = stream[i]
    return reservoir

为什么这种算法是合理的？

现在我们让每个元素最终被保持在 reservoir 的概率是多少。我们以某个特定的元素，例如第\(i\)个元素（\(i > k\)）为例，它最后被保留在reservoir中的概率可以分为两部分：

第 \(i\) 个元素被选择到reservoir中的概率：这是很直观的，就是\(k/i\)。 在选择了第 \(i\) 个元素之后，所有后续的元素没有替换掉第 \(i\) 个元素的概率：对于任何后续的元素 \(j （j > i）\)，它首先以 \(k/j\) 的概率被选中，然后以1/k的概率替换掉reservoir中的第 \(i\) 个元素（假设reservoir中元素的位置是等概率的）。所以，第 \(j\) 个元素替换掉第 \(i\) 个元素的概率是 \((k/j)(1/k)= 1/j\)。相反，没替换掉的概率就是 \(1-1/j = (j-1)/j\)。 由于所有的 \(j\) 都必须没替换掉第 \(i\) 个元素，所以这些概率需要连乘起来，从 \(i+1\) 一直乘到\(n\)。那么第\(i\)个元素被保留在reservoir的总概率就是：

\(P(i \in \text{reservoir}) = (k/i) * [(i+1)/i+1] * [(i+2)/(i+1)] * ... * [n/n+1] = k/n\)

因此，无论 \(n\) 的大小如何（即数据流的长度是多少），所有元素最后被保留在reservoir中的概率都是 \(k/n\)，确保了每个元素被选中的公平性。

这里的"公平"是指对于数据流中的任何一个元素，其最终被留在蓄水池中的概率都是相等的。

扔鸡蛋⚓︎

N 层楼，2个相同鸡蛋，某层 T 以下都不碎，以上必碎，要在最坏情况下把测试次数减到最少。问最优策略和最少次数。

假设 N = 100，假设 t 层碎了，那么线性检查 t - 1, t - 2, ... 1 层，也就是 \(t * (t + 1) / 2 \geq 100\) ， \(t = 14\)。也就是先从 14 层往下扔。

解释：因为总共只有2个鸡蛋，因此必须充分利用第一个蛋碎的信息。

如果一个蛋在 \(t\) 层碎了，那么你必须检查 \([1, t - 1]\) 的所有情况（最坏），算上最开的一次，也就是必须投掷 \(t\) 次实验。

如果一个蛋在 \(t\) 层没有碎，那么这个值 T 肯定比 t 大，但是我们下一次选的位置，只有 t - 1 次实验机会了，也就是说，你无论怎么选，下一个值必须在 \(t - 1\) 层内，再倒推，如果下一次实验依然没碎，那么我们只剩下 \(t - 2\) 次机会了... 总之，为了防止 极大楼层数，我们必须有序增加楼层高度。比如 t 层没碎，那么 下次投 t + t - 1 层，这样就算碎了，我们也只要检验 \([t + 1, t + t - 1]\) 中间的层即可。

所以我们选择的 t 就是 \((t * (t + 1)) / 2 \geq N\) 的那个最小的 t。

追问：如果固定 100 层，但是 N 个鸡蛋，不同鸡蛋数量的次数有什么区别？

  1. 如果1个鸡蛋，毫无疑问最坏要100次；
  2. 2个鸡蛋，最坏要14次；
  3. 如果鸡蛋数很多可以二分搜索；最坏需要 \(\lceil \log_2(100) \rceil\) ，也就是 7 个鸡蛋。
  4. 在中间的那些情况：

非常好的问题！从2个鸡蛋推广到n个鸡蛋，会让这个问题从一个巧妙的逻辑题，升级为一个经典的动态规划问题。

我们依然沿用之前的思路，但需要把它变得更加通用。

思想：动态规划⚓︎

我们定义一个函数 F(n, k)，它表示用 n 个鸡蛋，进行 k 次测试，最多可以确定多少层楼的临界点。

我们的目标是找到一个最小的 k，使得 F(n, k) >= 100。

现在，我们来推导 F(n, k) 的表达式。假设我们拿着一个鸡蛋，在某一层楼 x 扔下。这是我们的第1次测试（总共允许 k 次）。

  1. 如果鸡蛋碎了：

    • 我们还剩下 n-1 个鸡蛋。
    • 我们还剩下 k-1 次测试机会。
    • 我们知道临界楼层在 x 层以下（即 1 到 x-1 层）。
    • 利用剩下的资源，我们能测试的楼层数是 F(n-1, k-1)。

  2. 如果鸡蛋没碎：

    • 我们还剩下 n 个鸡蛋。
    • 我们还剩下 k-1 次测试机会。
    • 我们知道临界楼层在 x 层以上。
    • 利用剩下的资源，我们在当前 x 层之上能继续向上测试的楼层数是 F(n, k-1)。

把这两种情况结合起来，我们在第 x 层扔一次，总共能覆盖的楼层数是： * x层以下的 F(n-1, k-1) 层 * x层本身（1层） * x层以上的 F(n, k-1) 层

为了最大化 F(n, k)，我们应该选择一个最优的 x。这个最优的 x 就是 F(n-1, k-1) + 1。这样，无论鸡蛋碎不碎，我们都能继续测试。

所以，我们得到了状态转移方程： $$ F(n, k) = F(n-1, k-1) + F(n, k-1) + 1 $$

这个方程表示：用 n 个鸡蛋、k 次机会能测试的最大楼层数，等于（蛋碎了能测试的楼层数）+（蛋没碎能继续向上测试的楼层数）+（当前测试的这一层）。

边界条件： * F(1, k) = k （如果只有1个蛋，只能线性从第1层测到第k层） * F(n, 1) = 1 （如果只有1次机会，只能测1层楼）

从动态规划到组合数学⚓︎

这个递推式看起来很眼熟。它和组合数（二项式系数）的递推式 C(k, n) = C(k-1, n-1) + C(k-1, n) 非常相似。经过数学推导，可以得出 F(n, k) 的一个更简洁的表达式：

\[F(n, k) = \sum_{i=1}^{n} C(k, i) = C(k, 1) + C(k, 2) + \dots + C(k, n)\]

其中 C(k, i) 是组合数，表示从 k 个元素中选 i 个。

这个公式的直观理解是：k 次测试中，如果鸡蛋在第 i 次（i <= n）测试时碎了，那么总共能覆盖的楼层数。把所有可能碎裂的情况（最多碎 n 个蛋）加起来，就是总共能测试的楼层数。

现在，我们的问题变成了：对于给定的鸡蛋数 n，找到最小的 k，使得：

\[\sum_{i=1}^{n} C(k, i) \ge 100\]

我们来计算不同 n 值对应的 k：

  • n = 1 (1个鸡蛋)

    • F(1, k) = C(k, 1) = k
    • k >= 100 => k = 100
    • 结果：100次 (线性扫描)

  • n = 2 (2个鸡蛋)

    • F(2, k) = C(k, 1) + C(k, 2) = k + k(k-1)/2 = k(k+1)/2
    • k(k+1)/2 >= 100 => k = 14
    • 结果：14次 (这和你原始问题一致)

  • n = 3 (3个鸡蛋)

    • F(3, k) = C(k, 1) + C(k, 2) + C(k, 3) >= 100
    • 我们来试一下 k 的值：
      • k=8: F(3, 8) = 8 + 28 + 56 = 92 (不够)
      • k=9: F(3, 9) = 9 + 36 + 84 = 129 (够了)
    • 结果：9次

  • n = 4 (4个鸡蛋)

    • F(4, k) = C(k, 1) + C(k, 2) + C(k, 3) + C(k, 4) >= 100
    • 我们来试一下 k 的值：
      • k=7: F(4, 7) = 7 + 21 + 35 + 35 = 98 (不够)
      • k=8: F(4, 8) = 8 + 28 + 56 + 70 = 162 (够了)
    • 结果：8次

  • n >= 7 (鸡蛋足够多)

    • 当鸡蛋数量足够多时，我们就不怕鸡蛋碎了，最优策略就变成了二分查找。
    • 对于100层楼，二分查找需要 ceil(log₂(100)) 次。
    • 2^6 = 64, 2^7 = 128。所以 log₂(100) 约等于6.64。
    • ceil(log₂(100)) = 7。
    • 在最坏情况下，二分查找可能每次都会扔碎一个鸡蛋(例如，你在50层扔，碎了；去25层扔，碎了...)，所以需要准备7个鸡蛋。
    • 当 n >= 7 时，k 不再减少。
    • 结果：7次

总结⚓︎

对于100层楼：

鸡蛋数 (n) 最少测试次数 (k) 求解表达式
1 100 k >= 100
2 14 C(k,1) + C(k,2) >= 100
3 9 C(k,1) + C(k,2) + C(k,3) >= 100
4 8 C(k,1) + C(k,2) + C(k,3) + C(k,4) >= 100
5 7 C(k,1) + ... + C(k,5) >= 100 (试k=6不够，k=7足够)
6 7 C(k,1) + ... + C(k,6) >= 100 (试k=6不够，k=7足够)
≥ 7 7 鸡蛋足够多，退化为二分查找: k >= ceil(log₂(100))

所以，对于n个鸡蛋、100层楼的问题，并没有一个简单的形如 f(n)=k 的解析表达式，而是一个需要求解不等式 ∑ C(k, i) >= 100 的计算过程。

无刻度水桶取X升水⚓︎

两个桶，\(m\) 和 \(n\) 的容量，无刻度，能否通过互相灌水来算出 \(X\) 升水呢？

回答：

当且仅当 \(X \leq \max(m, n)\) 且 \(gcd(m, n)\) 可以被X整除才可以。