约瑟夫及相似问题的解法
约瑟夫及相似问题的解法
关乎约瑟夫问题的理解与解法
约瑟夫问题的变形以及相关问题
约瑟夫问题介绍
- 约瑟夫问题的产生是据说著名犹太历史学家josephus有过以下的故事：罗马人占领侨塔帕特后，39个 犹太人与josephus和他的朋友躲到一个洞中，39个犹太人决定先后自杀从而不用被敌人抓到，决定了一个自杀方法，所有人围成一个圈，由第一个人开始报数，每报数到第三个该人就必须自杀，随后从此人后面一位重新开始报数，josephus和他的朋友并不像遵从，于是josephus和他的朋友先假装遵从，随后站在了第16个和31的位置上，免去了性命之忧。这就是著名的约瑟夫问题。
-
现如今很多关于这种背景的思维题，比如报数出列，出列后从下一位继续报数，直到剩余两位成为诱饵，其他人为猎手等的军事游戏，还是猴子争王的背景题…在这些题目的背后都是这样一种运行规则：
约瑟夫问题的解决
- 首先这种问题的背景都是，由总数为N的单位围成一个圈，以q为一个小单位不断循环，第q个除去，随后继续循环，直到最后剩余（q-1）个单位停止。
- 首先以最原始的约瑟夫问题来看：（41个人轮番自杀）
-
首次41个人按0-40的编号排成一个圆圈，此时的话第41个加一应该注意跳转成0。如下图：
- 首先定义一个长度为41的数组，随后定义一个计数变量来统计剩余的人数，初始化为41个人，随后用step来表示报数，定义一个编号index。然后就可以用同种的循环语句来实现了。主要就是当”’ i++ = 40；”’就应该让其回到第一个位置0上去。从而达到转圈的目的。每次去除一个人之后计数变量自减1。循环结束后遍历数组找出存活的人的编号。
- 所以根据 这种方法，对于相关性的问题，index 为下标，q为循环单位的N个元素，count为剩余元素应该是”’index = （index+1）%count”’。
版权声明：本文为whl-lin原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。