约瑟夫斯问题（Josephus Problem）
约瑟夫斯问题（有时也称为约瑟夫斯置换），是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为“约瑟夫环”，也有的地方叫做“丢手绢”。
问题是这样的：
有编号从
1
到
n
的
n
个人围坐成一圈。从编号为
1
的人开始报数，报到
m
的人出局，下一位再从
1
开始报数，报到
m
的人出局，……如此持续，直到剩下一人为止，假设此人的原始编号是
x
。给定
n
和
m
，求出
x
。
为了说明问题，我们举个例子。这个例子中
n=4, m=2
. 最终结果
x=1
.
以下是示意图（横着看）
思路一：编程模拟
若编程解决此问题，很容易想到用数组或者循环链表模拟整个过程，直到剩下一个人。
用数组模拟
C语言代码如下。
#include <stdio.h>
#include <stdlib.h>
void josephus(int n,int m) //一共n个人，报m的人被淘汰
{
if((n<=) || (m<=)) //n和m最小是2
return;
//数组的下标作为每个人的编号。a[0]不使用
int *a = (int *)malloc(sizeof(int)*(n+));
if(a==NULL)
{
printf("内存分配失败\n");
return;
}
int i;
for(i=;i<n+;++i)
a[i]=; // 初始化，1表示人存在
int count = ; //用来模拟报数，取值从0到m
int left = n; // 用来记录剩下的人数
while()
{
for(i=;i<=n;++i)
{
if(a[i]) //如果人存在
{
++count; //模拟报数，这里取值从1到m
if(count == m)
{
a[i]=; //此人被淘汰
printf("%d ",i); //打印被淘汰的人的编号
count=; //重置为0，准备下一轮报数
--left;
if(left == ) //说明只剩一个人,这时候跳出死循环
goto out;
}
}
}
}
out:
for(i=;i<=n;++i)
{
if(a[i]) //找到最后的那个人，打印其编号
{
printf("%d ",i);
break;
}
}
printf("\n");
free(a);
}
int main(void) //测试代码
{
josephus(,);
return ;
}
运行结果如下：
3 6 9 12 15 18 21 24 27 30 33 36 39 1 5 10 14 19 23 28 32 37 41 7 13 20 26 34 40 8 17 29 38 11 25 2 22 4 35 16 31
为了验证结果的正确，除了人工计算外，我从网上找了一张图片来对比：
用循环链表模拟
【错误的代码】本来想删除这部分内容，算了，留个纪念吧。
#include <stdio.h>
#include <stdlib.h>
void josephus(int n,int m);
int main(void)
{
josephus(,);
return ;
}
struct node
{
int data;
struct node *next;
};
typedef struct node node_t;
void josephus(int n,int m)
{
// 创建头结点
node_t *head = (node_t *)malloc(sizeof(node_t));
if(head==NULL)
{
printf("内存分配失败\n");
return;
}
node_t *pre = head;
node_t *cur;
for(int i=;i<=n;++i)
{
cur = (node_t *)malloc(sizeof(node_t));
if(cur==NULL)
{
printf("内存分配失败\n");
return;
}
cur->data = i; //用data字段存储编号
pre->next = cur;
pre = cur;
} //以上带头结点的单向链表创建完毕，此时cur指向最后一个结点
cur->next = head->next; //最后一个结点的next域指向第一个结点，构成循环链表
cur = head->next; // 让cur指向第一个人
free(head); //头结点不再使用，释放头结点
int skip;
while(n--) //每次循环淘汰一人（包括胜利者），循环n次
{
skip = m-; //从1报数到m,即跳过（m-1）个人
while(skip--)
{
pre = cur;
cur = cur->next; //cur指向下一个人
}
pre->next = cur->next; //淘汰一人
printf("%d ",cur->data); //打印被淘汰者的编号
free(cur); //释放结点
cur = pre->next; //从1开始报数，cur指向报1的人
}
printf("\n");
}
测试上面的代码，虽然结果正确，但是我发现了一个BUG，请注意64~65这两行
free(cur); //释放结点
cur = pre->next; //从开始报数，cur指向报的人
当执行最后一次循环体的时候，此时只剩一个人，
cur
和
pre
指向的是同一个地址，执行完
free(cur);
与此地址关联的内存已经被释放，
cur
和
pre
都不能被引用了（除非它们又指向了其他有效的内存区域）。但是，
cur = pre->next
这条语句又引用了
pre
。所以，这是一个BUG！
所以，我修改了while循环（见下面33~46行）。
【正确的代码】
void josephus(int n,int m)
{
// 创建头结点
node_t *head = (node_t *)malloc(sizeof(node_t));
if(head==NULL)
{
printf("内存分配失败\n");
return;
}
node_t *pre = head;
node_t *cur;
for(int i=;i<=n;++i)
{
cur = (node_t *)malloc(sizeof(node_t));
if(cur==NULL)
{
printf("内存分配失败\n");
return;
}
cur->data = i; //用data字段存储编号
pre->next = cur;
pre = cur;
} //以上带头结点的单向链表创建完毕
cur->next = head->next; //最后一个结点的next指向第一个结点，构成循环链表
cur = head->next; // cur指向第一个人
free(head); //头结点不再使用，释放头结点
int skip;
while(cur->next != cur) //不断淘汰，直到剩下一个人
{
skip = m-; //从1报数到m,即跳过（m-1）个人
while(skip--)
{
pre = cur;
cur = cur->next; //cur指向下一个人
}
pre->next = cur->next; //淘汰
printf("%d ",cur->data); //打印被淘汰者的编号
free(cur); //释放结点
cur = pre->next; //从1开始报数，cur指向报1的人
}
printf("%d\n",cur->data); //打印最后一个人的编号
free(cur);
}
思路二：数学公式法
无论是用数组还是用循环链表求解，都有一个共同点——要模拟整个过程，时间复杂度高达
O(n*m)
，当
n*m
非常大（例如上百万、上千万）的时候，是非常耗时间的。
注意到原问题仅仅要求算出最后胜利者的编号，而不是要求模拟整个过程。因此要追求效率，就要打破常规，比如利用数学方法。
为了讨论方便，先把问题稍微改变一下，并不影响原意。
有编号从
到
n-1
的
n
个人围坐成一圈。从编号为
的人开始报数，报到
m-1
的人出局，下一位再从
开始报数，报到
m-1
的人出局，……如此持续，直到剩下一人为止，假设此人的原始编号是
x
。给定
n
和
m
，求出
x
。
还是以
n=4, m=2
为例，每淘汰一个人后（绿色表示），我们给余下的人重新编号（从0开始编），示意图（竖着看）如下。
令
f(i)
表示
i
个人玩此游戏最后胜利者的编号，那么本问题就是求
f(n)
.
不管多少人玩这个游戏，最后胜出者的新编号都是0，所以我们规定
f(1)=0;
由上图第一行可以得出：
f(2)=0, f(3)=2, f(4)=0;
其中的规律是：
f[i]=(f[i-1]+m)%i; (i>1)
也就是说递推公式如下：
f[i]=0; (i=1)
f[i]=(f[i-1]+m)%i; (i>1)
公式的证明可以参考维基百科，这里略去。
根据公式我们就可以写出代码，C语言代码如下。
void josephus(int n,int m)
{
int s = ;
for(int i=; i<=n; ++i)
{
s = (s+m)%i;
}
printf("the winner = %d\n",s);
}
测试代码是
int main(void)
{
josephus(,);
return ;
}
运行结果是
the winner = 30
如果编号从1开始，那么获胜者的编号是31，这和前两种方法得出的结果是一致的。
【参考资料】
[1] 维基百科https://zh.wikipedia.org/wiki/%E7%BA%A6%E7%91%9F%E5%A4%AB%E6%96%AF%E9%97%AE%E9%A2%98
[2] http://mathworld.wolfram.com/JosephusProblem.html
[3] http://blog.163.com/[email protected]/blog/static/157591739201321341221179/