马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
本帖最后由 三体人的智子 于 2024-8-16 19:36 编辑
约瑟夫问题（简单版）
还记得2024的春晚魔术吗？ 里面的步骤：
1.准备阶段：
准备四张扑克牌，分别命名为1、2、3、4。将这四张牌撕开后，产生两套（半张）扑克牌，每套包含1、2、3、4各一张。
2放置阶段：
将牌堆顶数量为名字字数的牌移至牌堆底。无论移多少张牌，得到的扑克牌堆编号（从上至下）都只会有以下几种结果：
前四张牌和后四张牌的顺序完全一样。
前四张牌和后四张牌分别是1234的一个轮换。
3插入阶段：
将前三张放在牌堆中间，并取出牌堆顶的牌置于一旁。
南方人取一张，北方人取两张，若不确定是南方人还是北方人的取三张。无论本轮中选择牌堆顶多少张牌插入牌堆中，都不会影响目标牌的位置，仍然处于牌堆底部。
4丢弃阶段：
男生扔掉牌堆顶一张，女生扔掉牌堆顶两张。
5见证奇迹的时刻：
从牌堆顶开始，每次先将牌堆顶的一张牌放在牌堆底，再扔掉牌堆顶的一张牌。重复以上操作直到只剩一张牌。
检查此牌和步骤三中放置在一旁的牌是否吻合，若吻合则魔术成功。
没错，此魔术的原理就是约瑟夫问题
一个小故事 ：
一群犹太人被罗马人包围，为了不当罗马人的俘虏，他们选择集体自杀。
自杀的方式是第一个士兵会杀掉他左边的第二个士兵，同样的第三个会杀掉第四个士兵……直到最后只剩下一个人，他再自杀。
士兵中有个人叫约瑟夫，他其实想投降保命，但不敢明说，那么约瑟夫应该站在那个位置才能成为最后剩下的人，这样就不用自杀了。
举几个例子：1.当士兵只有5个人时，站在第三个位置可以保命。
2.当士兵只有8个人时，站在第一个位置可以保命。
3.当士兵只有10个人时，站在第五个位置可以保命。
详细一些：当士兵有8个人。
第一回合：1->2,3->4,5->6,7->8。
第二回合：1->3,5->7。
第三回合：1->5
最终活下来的是1
从活着的人中我们可以看到一些规律：1.不论总人数多少，最终活下来的人的位置都是奇数。
2.多举几个例子会发现士兵一活下来的机率最高。（2，1）（4，1）（8，1），且一对应的位置都是2的n次方。
也就是说，如果士兵总人数是2的n次方($2^n$)，最后活着的一定是士兵1。（关键）
那么如果士兵人数不是2的n次方，我们可以将其转化为2的n次方+a。
例如19=$2^4$+3，刚才所说，在2的3次方上，存活的一定是士兵一，也就是最先动手的人，所以我们只需要看前面的三个，可以理解为先排除多余的这三个人，1->2,3->4,5->6,把2，4，6这三个人排除掉，然后再重新标识位置，这时候总人数变成16人，也就是2的4次方，按规律，活下来的是标识后的士兵一，所以看士兵一其实就是原来的士兵7，所以我们说在总人数19人时，活下来的是士兵7，按照这个计算方式，如果总人数为33人，38=2的5次方+6，然后去数等六个人被杀后该第几个人动手，这个人就是活下来的，接下来将这个规律整理成数学公式。
也就是约瑟夫公式：如果总人数是x,可以拆解为：x=a+$2^n$，最终存活的位置是y=2*a+1.
废话不多说，上代码（python）def josephus(n,m)
if n==1:
return 1
else:
return(josephus(n-1,m)+m-1)%n+1
代码演示：
| 
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2024-2-20 20:20:13
置顶卡
千斤顶
显身卡
楼主
发表于 2024-2-20 20:42:40
发表于 2024-2-21 18:19:34
