一道+ / edao.plus

二进制法

对于循环淘汰问题（如丢一张、移一张），找出不超过 n 的最大 2 的幂 2^m，答案 = 2 × (n - 2^m)。

直观场景

当卡片数是 2 的幂时，最后剩下的就是最后一张；多出来的部分经过一轮操作后会变成 2 倍，所以答案就是 2 × (n - 2^m)。

推导思路

  1. 找出不超过 n 的最大 2 的幂 2^m。
  2. 计算 k = n - 2^m。
  3. 答案 = 2 × k。

公式 / 要点

  • 当 n 是 2 的幂时，答案就是 n 本身。
  • 这个方法适用于“丢一张、移一张”这种循环淘汰模式。

典型例题

1卡片淘汰
100 张卡片编号 1~100，每次丢掉最上面一张，把下一张移到最下面，直到剩一张。最后是几号？
  1. 不超过 100 的最大 2 的幂是 64。
  2. k = 100 - 64 = 36。
  3. 答案 = 2 × 36 = 72。

小结：记住公式：答案 = 2 × (n - 2^m)，其中 2^m 是不超过 n 的最大 2 的幂。

常见误区

  • 不要混淆不同的淘汰模式，这个公式只适用于“丢一张、移一张”的情况。

用到「二进制法」的题目

#10194 卡片淘汰
数论五年级