问题来源
- 据说著名犹太历史学家Josephus有过以下的故事：
在罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲到一个山洞，39个犹太人决定宁死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀生忙为止。
然而Josephus和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置。于是逃过了这场死忙游戏。
理论付诸实践
约瑟夫问题里边41个人是围城一个圆圈，我们的循环链表也是一个圆圈，所以可以模仿并让计算机运行告诉我们的结果。
问题： 用循环链表模拟约瑟夫问题，把41个人自杀的循序编号输出。
代码如下：
#include<stdafx.h>
#include<stdio.h>
#include<stdlib.h>
//n个人围圈报数，报m出列，最后剩下的是几号？
typedef struct node {
int data;
struct node *next;
}node;
node *create(int n) {
node *p = NULL, *head;
head = (node *)malloc(sizeof(node));
p = head;
node *s = NULL;
int i = 1;
if (0 != n)
{
while (i <= n)
{
s = (node *)malloc(sizeof(node));
s->data = i++;
p->next = s;
p = s;
}
s->next = head->next;
}
free(head);
return s->next;
}
int main() {
int n = 41;
int m = 3;
int i;
node *p = create(n);
node *temp;
m %= n;
printf("%d\n\n", m);
//判断链表是否为空
while (p != p->next)
{
for (i = 1; i < m - 1; i++)
{
p = p->next;
}
printf("%d->", p->next->data);
temp = p->next;
p->next = temp->next;
free(temp);
p = p->next;
}
printf("%d", p->data);
getchar();
return 0;
}
约瑟夫问题的扩展
提高挑战难度：编号为1~N的N个人按顺时针方向围坐一圈，每人持有一个密码（正整数，可以自由输入）。开始人选一个正整数作为报数上限值M,从第一个人按顺时针方向自1开始顺时针报数，报道M时停止报数。报道M的人出列，将他的密码作为新的M值，从他顺时针方向上的下一个人开始从1报数，如此下去，直至所有人全部出列为止。
