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





















有帮助,赞一个