首页技术正文

[py]约瑟夫问题-循环队列

开发者玉涵技术 2022年11月16日

0 收藏 471 点赞 3,195 浏览 807 个字

约瑟夫问题(历史战争问题)

直观理解

老外视频讲解
 模拟器演示

约瑟夫问题数学姥公众号讲的最清楚背景及,推倒过程讲解得很清晰,旨在提高人们对数据的兴趣

简单说下: 几个人围成一圈(循环队列), 第一个人开始报数 1 2 1 2, 依次进行,喊2的被杀掉. 如果人数是n,则最后剩下几号?

约瑟夫斯问题是个蛮好玩的问题。这个问题来源于一个犹太叛徒，约瑟夫斯是犹太人，参与了对罗马的起义，并被任命为起义部队的军事长官。不过在后来罗马军团的进攻下，犹太人的起义很快失败了，约瑟夫斯带领这39名犹太士兵躲到了一个山洞中，山洞则被罗马人包围。士兵们坚贞不屈，宁可死也不肯投降，然而约瑟夫斯不想死，又不敢说出来。于是约瑟夫斯利用了犹太教中关于自杀耻辱的教义，说咱们不能自杀，咱们可以互相杀，怎么互相杀，谁来杀呢？这样

40人围成一圈，然后连续1,2,1,2……报数，所有报2的被同伴杀死，直到最后一个，最后一个自杀者承担教义中自杀的耻辱。约瑟夫斯是个数学家，他当然很快就知道自己应该站在哪个位置而不会被杀死。当所有人都被杀死后，他走出山洞，投降了罗马人。

那么，现在的问题是，就按照1212报数，报2被杀死的规则，当人数n不止40时，站在哪个位置能最后活下来？

最终推倒出的解决公式:

如果n个人,则最终f(n)号活下来.栗子1: f(100)=f(64+36)=2*36+1=73，100这里为何64+36呢? 2^6=64, 2^7=128>100, 所以只能36了.依据公式,可以推倒出 n = 100, f(100)=73栗子2: n = 6,最终存活下第5个Susan["Bill", "David", "Kent", "Jane", "Susan", "Brad"]

搞清楚了这个问题是啥,和解题思路.后用程序来实现它.