约瑟夫环问题（链表 + 公式）

约瑟夫环

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

解决约瑟夫环问题方法

一、单向循环链表

我们很容易想到的是用数据结构中的单向循环链表，构成逻辑上第一个环，假设有n个人，那么就需要定义n个结点。定义一个指针指向头结点，然后指针向后移动，当移动m次后，删除该指针所在的结点，并让该指针指向被删结点的下一个结点，重新开始计数，再次移动m次时删除当前所在的结点，以此类推，当该结点只剩下一个节点时，说明该结点就是活下来的人。

代码

#include<stdio.h>
#include<stdlib.h>

typedef int LDataType;

typedef struct listNode
{
    LDataType data;
    struct listNode* next;
}listNode;

typedef struct list
{
    struct listNode* head;
}list;

void listInit(struct list* lst)
{
    if (lst == NULL)
        return;
	lst->head = NULL;
}

struct listNode* creatListNode(LDataType val)
{
	struct listNode* node = (struct listNode*)malloc(sizeof(listNode));
	if (node == NULL)
		exit(0);
	node->data = val;
	node->next = NULL;
	return node;
}

void listPushBack(struct list* lst, LDataType val)
{
	if (lst == NULL)
		return;

	if (lst->head == NULL)
	{
		lst->head = creatListNode(val);
		lst->head->next = lst->head;
	}
	else
	{
		struct listNode* tail;
		struct listNode* cur = lst->head->next;
		while (cur->next != lst->head)
		{
			cur = cur->next;
		}
		cur->next = creatListNode(val);
		tail = cur->next;
		tail->next = lst->head;
	}
}

void creatList(struct list* lst, int n)
{
	
	for (int i = 0; i < n; ++i)
	{
		listPushBack(lst, i);
	}
}

void josephCycle(int n, int m)
{
	list lst;
	listInit(&lst);
	creatList(&lst, n);
	struct listNode* cur = (&lst)->head;
	struct listNode* prev = (&lst)->head;
	struct listNode* tail = NULL;

	while (prev->next != (&lst)->head)
	{
		prev = prev->next;
	}

	while (cur->next != cur)
	{
		for (int i = 1; i < m ; ++i)
		{
			prev = cur;
			cur = cur->next;
		}
		tail = cur->next;
		prev->next = tail;
		free(cur);
		cur = tail;
	}

	printf("%d\n", cur->data);
}

int main()
{
	josephCycle(5, 3 );
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

缺点

要模拟整个游戏过程，时间复杂度高达O(nm)，当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。

二、约瑟夫环公式法

约瑟夫环是一个经典的数学问题，我们不难发现这样的依次报数，似乎有规律可循。为了方便导出递推式，我们重新定义一下题目。
问题： N个人编号为1，2，……，N，依次报数，每报到M时，杀掉那个人，求最后胜利者的编号。

公式：f(N,M)=(f(N−1,M)+M)%N
f(N,M)表示，N个人报数，每报到M时杀掉那个人，最终胜利者的编号
f ( N − 1 , M ) f(N-1,M)f(N−1,M)表示，N-1个人报数，每报到M时杀掉那个人，最终胜利者的编号

现在我们来推导这个公式是怎么来的
既然约塞夫问题就是用人来举例的，那我们也给每个人一个编号（索引值），每个人用字母代替
下面这个例子是N=8 m=3的例子
我们定义F(n,m)表示最后剩下那个人的索引号，因此我们只关系最后剩下来这个人的索引号的变化情况即可

从8个人开始，每次杀掉一个人，去掉被杀的人，然后把杀掉那个人之后的第一个人作为开头重新编号

第一次C被杀掉，人数变成7，D作为开头，（最终活下来的G的编号从6变成3）
第二次F被杀掉，人数变成6，G作为开头，（最终活下来的G的编号从3变成0）
第三次A被杀掉，人数变成5，B作为开头，（最终活下来的G的编号从0变成3）
以此类推，当只剩一个人时，他的编号必定为0！（重点！）

现在我们知道了G的索引号的变化过程，那么我们反推一下
从N = 7 到N = 8 的过程
如何才能将N = 7 的排列变回到N = 8 呢？
我们先把被杀掉的C补充回来，然后右移m个人发现溢出了，再把溢出的补充在最前面，神奇了经过这个操作就恢复了N = 8 的排列了！

问题1：假设我们已经知道8个人时，胜利者的下标位置为6。那下一轮7个人时，胜利者的下标位置为多少？
**答：**其实吧，第一轮删掉编号为3的人后，之后的人都往前面移动了3位，胜利这也往前移动了3位，所以他的下标位置由6变成3。

问题2：假设我们已经知道7个人时，胜利者的下标位置为3。那下一轮8个人时，胜利者的下标位置为多少？
**答：**这可以看错是上一个问题的逆过程，大家都往后移动3位，所以f ( 8 , 3 ) = f ( 7 , 3 ) + 3 。不过有可能数组会越界，所以最后模上当前人数的个数，f ( 8 , 3 ) = （ f ( 7, 3 ) + 3 ） % 8
问题3：现在改为人数改为N，报到M时，把那个人杀掉，那么数组是怎么移动的？
**答：**每杀掉一个人，下一个人成为头，相当于把数组向前移动M位。若已知N-1个人时，胜利者的下标位置位f ( N − 1 , M ) f(N-1,M)f(N−1,M)，则N个人的时候，就是往后移动M为，(因为有可能数组越界，超过的部分会被接到头上，所以还要模N)，既f ( N , M ) = ( f ( N − 1 , M ) + M ) % n f(N,M)=(f(N-1,M)+M)%nf(N,M)=(f(N−1,M)+M)%n

注：理解这个递推式的核心在于关注胜利者的下标位置是怎么变的。每杀掉一个人，其实就是把这个数组向前移动了M位。然后逆过来，就可以得到这个递推式。

代码：

int lastRemaining(int n, int m)
{
    if (n == 1) 
    {
        return 0;
    }
    int res = 0;

    for (int i = 2; i <= n; ++i)
    {
        res = (res + m) % i;
    }

    return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

附上力扣的oj题

圆圈中最后剩下的数字.

参考资料
1、https://blog.csdn.net/u011500062/article/details/72855826