数学问题：如何计算出为什么41个人中第16个和第31个幸存下来？

来源：百度知道 编辑：UC知道 时间：2024/05/26 17:09:45
数学问题：我在报纸上看到一个有关宗教的故事，说是某犹太人村庄被敌人屠杀，一个领袖带领一队人马出逃，逃到一个山洞，发现走投无路，被敌人包围。这时首领提议集体自杀但是采用如下方法：大家站成一个圈，定好位次，一二三报数，第二个数到三的人将前面数到三的人杀死，而最终剩下的那一个报三的人因为自己的刀沾满了前面所有犹太人的血，所以需要自杀。这队人马一共41人，首领把他自己还有他最亲信的朋友安排在16和31的位次。结果他们两个留到最后，走出山洞，投降敌人。请问，如何通过数学计算得出最后幸存的会是16和31两个位次？请给出详细计算方法及过程。谢谢。
谢谢d33的实列，我也是通过这样一轮轮一个个地剔除之后，验证出最后两名的确剩下第16和第31位。但是我想那位领袖一定有什么迅速计算的方法，才能在短时间内给自己和亲信安排了那两个位次。我希望能有聪明人用数学计算的方式给出答案。多谢了。

著名的Josephus问题，目前好像还没有通项公式解，实际的解法都是模拟或用递推公式做的。在数值较大时，模拟的速度过慢，还是用递推公式较好。

下面的网页给出了用模拟方法的C语言程序解：
http://zhidao.baidu.com/question/5112282.html
下面的页面则给出了递推公式及相应的C程序：
http://www.programfan.com/blog/article.asp?id=17704

下面页面则综合了上面两种解法：
http://www.vshj.com/Article/2005/200512/Article_20266.shtml

附：递推公式
f(1) = 0;
f(i) = (f(i - 1) + m) mod i; (i > 1)

第一轮之后剩下:1,2,4,5,7,8,10,11,13,14,16,17,19,20,22,23,25,26,28,29,31,32,34,35,37,38,40,41
第二轮之后剩下:2,4,7,8,11,13,16,17,20,22,25,26,29,31,34,35,38,40,41
第三轮之后剩下:2,4,8,11,16,17,22,25,29,31,35,38,40
第四轮之后剩下:2,4,11,16,22,25,31,35,38
第五轮之后剩下:2,4,16,22