Josephus环问题两种求解算法（C语言实现）
一、算法一
构造双向循环链表。
首先创建结构体数组，每个结构体包括元素的编号、前驱元的索引(previous)及后继元的索引(next)。每次循环删除一个元素，使该元素的前驱元的next指向后继元的previous，后继元的previous指向前驱元的next，并将此元素标号置为-1。
从被删除元素的下一个元素开始继续循环，直到数组中只剩下一个元素（此元素的previous与next相等）
显然该算法时间复杂度为O(m*n)
#include<stdio.h>
#include<stdlib.h>
struct node
{
int number; //序号
int previous; //前驱元标号
int next; //后继元标号
};
struct node* InitArray(int n)//初始化游标形式的双向循环链表
{
struct node* people = (struct node*)malloc(sizeof(struct node) * n);
for (int i = 0; i < n; i++)
{
people[i].number = i + 1;
people[i].next = (i + 1) % n;
people[i].previous = (i + n - 1) % n;
}
return people;
}
int Josephus(int n, int m)
{
struct node* people = InitArray(n);
int current = m;
while ((current != people[current].next))//只剩下一个元素时，结束循环
{
printf("%d->", people[current].number);
people[current].number = -1;
people[people[current].previous].next = people[current].next;//删去结点，修改指针指向
people[people[current].next].previous = people[current].previous;
for (int i = 0; i <= m; i++)
{
if (people[people[current].next].number > 0)
{
current = people[current].next;
}
}
}
return people[current].number;
}
int main()
{
int x; //初始总人数
int y; //相邻两个倒霉的人之间相隔的人数
printf("初始总人数为：");
scanf_s("%d", &x);
printf("相邻两个倒霉的人之间间隔的人数为：");
scanf_s("%d", &y);
printf("\n最后幸存的人标号为：%d", Josephus(x, y));
return 0;
}
二、算法二
首先删除标记为k - 1的人，把最初标记为k的人标 记为0，并从0开始，重新标记其余的标签;
则有关系式Josephus(n, k) = (Josephus(n - 1, k) + k)) % n;
另有Josephus(1, k) = 0;
据此即可在O(n)时间内完成迭代计算
(代码略）