这是经典的约瑟夫环问题(Josephus Problem)。
你的描述:100个士兵围成一圈,从1开始报数,报到2的人被杀(淘汰),然后继续从1报数,循环直到剩下最后一个人。
核心问题:最后活下来的是第几号士兵?
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
通用解法
对于“报数到 m 就淘汰”的约瑟夫问题,当人数为 n、报数到 2 淘汰时,最后幸存者的编号可以用公式递推:
设 f(n)f(n)f(n) 为 n 个人时幸存者的位置(0-indexed):
f(1)=0f(1) = 0f(1)=0
f(n)=(f(n−1)+2) mod nf(n) = (f(n-1) + 2) \bmod nf(n)=(f(n−1)+2)modn
算到 n=100:
* 也可以直接用公式:当 n=2k+ln = 2^k + ln=2k+l(其中 0≤l<2k0 \le l < 2^k0≤l<2k)时,幸存者位置为 2l2l2l(1-indexed 则为 2l+12l+12l+1)。
100 = 64 + 36,所以 l=36l = 36l=36,幸存者编号 = 2×36+1=732 \times 36 + 1 = 732×36+1=73。
答案:第73号士兵活下来。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
这类题常见变体
1. 报数到 3 淘汰(杀3数)——公式不同,需递推。
2. 从某人开始报数,或每隔几个淘汰。
3. 求被杀顺序,而不只是最后幸存者。
4. 猴子选大王、丢手绢等应用题。
如果你是想问“这是什么类型的题”,答案就是:约瑟夫环(约瑟夫问题),属于算法/数据结构中的经典模拟与递推题。