约瑟夫问题（出自计算机科学和数学中的问题）

问题来历

据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus和他的朋友并不想遵从。首先从一个人开始，越过

17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事：15个教徒和15个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。

问题分析与算法设计

约瑟夫问题并不难，但求解的方法很多；题目的变化形式也很多。这里给出一种实现方法。

题目中30个人围成一圈，因而启发我们用一个循环的链来表示，可以使用结构数组来构成一个循环链。结构中有两个成员，其一为指向下一个人的指针，以构成环形的链；其二为该人是否被扔下海的标记，为1表示还在船上。从第一个人开始对还未扔下海的人进行计数，每数到9时，将结构中的标记改为0，表示该人已被扔下海了。这样循环计数直到有15个人被扔下海为止。

一般形式

约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如

分析：

（1）由于对于每个人只有死和活两种状态，因此可以用布朗型数组标记每个人的状态，可用true表示死，false表示活。

（2）开始时每个人都是活的，所以数组初值全部赋为false。

（3）模拟杀人过程，直到所有人都被杀死为止。

pascal代码1

C++代码

无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达

为了讨论方便，先把问题稍微改变一下，并不影响原意：

问题描述：n个人（编号

我们知道第一个人（编号一定是

并且从k开始报0。

我们把他们的编号做一下转换：

...

...

变换后就完完全全成为了

如何知道

令f表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]

递推公式

有了这个公式，我们要做的就是从

由于是逐级递推，不需要保存每个f，程序也是异常简单：

pascal

代码2

pascal代码3

pascal代码4

c++

pascal代码5

这个算法的时间复杂度为

python代码

该程序基于python3.x实现

10e100版

描述Description

n个人排成一圈。从某个人开始，按顺时针方向依次编号。从编号为1的人开始顺时针“一二一”报数，报到2的人退出圈子。这样不断循环下去，圈子里的人将不断减少。由于人的个数是有限的，因此最终会剩下一个人。试问最后剩下的人最开始的编号。

输入格式InputFormat

一个正整数n，表示人的个数。输入数据保证数字n不超过100位。

输出格式OutputFormat

一个正整数。它表示经过“一二一”报数后最后剩下的人的编号。

样例输入SampleInput

9

样例输出SampleOutput

3

时间限制TimeLimitation

各个测试点1s

注释Hint

样例说明

当

24681597

最后剩下的人编号为3

初见这道题，可能会想到模拟。可是数据实在太大啦！！

我们先拿手来算，可知n分别为1，2，3，4，5，6，7，8...时的结果是1，1，3，1，3，5，7，1...

有如下规律：从1到下一个1为一组，每一组中都是从1开始递增的奇数，且每组元素的个数分别为1，2，4...

这样就好弄了！！

大体思路如下：

①

②

③

⑥

⑦

⑧

⑨

有了思路，再加上高精度就可以了。我写的代码比较猥琐，因为是先把上面的思路敲进去，再写过程，又把一些简单的过程合到主程序中了，所以有点乱，也有点猥琐。起提供思路的作用还是完全可以的吧~~~

猴子选王

一．问题描述：

一堆猴子都有编号，编号是

约瑟夫

"密码问题"

问题描述：编号为

编号为1的人开始，按顺时针方向自1开始顺序报数，报到指定数M时停止报数，报M的人出列，并将

他的密码作为新的M值，从他在顺时针方向的下一个人开始，重新从1报数，依此类推，直至所有的

人全部出列为止。请设计一个程序求出出列的顺序，其中

二．基本要求：

（1）输入数据：输入m,nm,n为整数，

（2）中文提示按照m个猴子，数n个数的方法，输出为大王的猴子是几号，建立一个函数来实现此功能

• 1、C程序

• C语言程序2

• C语言程序3:用数组模拟链表

• pascal程序：

• 

• 约瑟夫数学算法

• 约瑟夫递推算法

• 2、PHP模拟算法

php有非常完善的数据结构模拟方案，可以非常简洁的解决这样的问题!

3、Python遍历数组

笔算解决约瑟夫问题

在M比较小的时候，可以用笔算的方法求解，

即N个人围成一圈，1，2，1，2的报数，报到2就去死，直到只剩下一个人为止。

当

对于任意的自然数N都可以表示为

于是当有t个人去死的时候，就只剩下

于是就求出了当

求出不大于N的最大的2的整数次幂，记为

即N个人围成一圈，1，2，3，1，2，3的报数，报到3就去死，直到只剩下一个人为止。

此时要比

我们以

假设这种情况下还剩下n个人，则下一轮将杀死

设这n个人为

从

于是可得：

1、这一轮中最后一个死的是

2、若

若

若

3、新一轮第k个人对应原来的第

综合1，2，3可得：

当

于是：

第一圈，将杀死669个人，这一圈最后一个被杀死的人是2007，还剩下1340个人，

第二圈，杀死446人，还剩下894人

第三圈，杀死298人，还剩下596人

第四圈，杀死198人，还剩下398人

第五圈，杀死132人，还剩下266人

第六圈，杀死88人，还剩下178人

第七圈，杀死59人，还剩下119人

第八圈，杀死39人，还剩下80人

第九圈，杀死26人，还剩下54人

第十圈，杀死18人，还剩36人

十一圈，杀死12人，还剩24人

十二圈，杀死8人，还剩16人

十三圈，杀死5人，还剩11人

十四圈，杀死3人，还剩8人

十五圈，杀死2人，还剩6人

然后逆推回去

视频中给出了经典的约瑟父问题的数学解法，当猴子选王问题的

对于经典约瑟父问题，视频中的解法是：

1）找出令等式

2）求解出

3）所以，最后留下来的人的序号为

视频中给出的解释是：

推广到猴子选王问题，从以上解法不难看出，解法就是把2换成N，即：

1）找出令等式

2）求解出

3）所以，最后留下来的猴子的序号为