约瑟夫及相似问题的解法

发布日期:2019-10-10

关乎约瑟夫问题的理解与解法

约瑟夫问题的变形以及相关问题

约瑟夫问题介绍

    约瑟夫问题的产生是据说著名犹太历史学家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"""。