约瑟夫问题
有N个人围成一个圈，从第1个人开始计数，如果数到m，则这个人从圈中退出，下一个人从1开始重新计数，重复此过程，直到所有人退出圈。
问:最后一个退出的人的编号是多少？
此问题如果我们使用单循环链表，模拟真实情况，则代码如下:
1.创建循环链表
typedef struct Node{
int data;
struct Node *next;
}Node;
typedef struct Node LinkList;
#define LINK_H
#include "Josephus.h"
LinkList *createLinkList(int n) {
int tmp = 1;
// 创建头结点
Node *head = (Node*)malloc(sizeof(Node));
head->data = 0;
head->next = head;
// 当前节点。现在指向头结点
Node *currentNode = head;
while (tmp <= n) {
// 创建子节点
Node *p = (Node*)malloc(sizeof(Node));
// 节点数据从1开始到n
p->data = tmp;
// 设置子节点的下一个节点
currentNode->next = p;
// 将子节点设置为当前节点
currentNode = p;
++tmp;
}
// 最后的子节点的下一个节点为头结点
currentNode->next = head;
return head;
}
2.计算最后一个退出的人
void find(LinkList *list, int m) {
Node *head = list;
Node *currentNode = head;
// 头结点永不删除，因此如果头结点的子节点还是自身，那么就是空链表了
while (head->next!=head) {
// 循环2次，找到要删除的子节点的上一个节点
for (int i = 1; i<m; ++i) {
currentNode = currentNode->next;
// 如果当前结点是头结点
if (currentNode == head) {
// 那么将头结点的下一个结点赋值给当前结点
currentNode = currentNode->next;
}
}
// 如果要删除的节点是头结点，那么将当前节点设置为头结点（也就是往后移动了一个节点）
if (currentNode->next == head) {
currentNode = currentNode->next;
}
// 打印删除节点的数据
printf("->%d",currentNode->next->data);
// 删除要删除的节点
free(currentNode->next);
currentNode->next = currentNode->next->next;
}
}
得到的结果
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
我们可以看到每次删除一个人，需要进行一次while循环。假设删除完所有的人，则外层时间复杂度为O(n)
每一次循环内部需要执行m-1次，则内层时间复杂度为O(m)。（这里忽略了-1）
则总的时间复杂度为O(n*m)。
该方法的好处是可以查看到退出的顺序。但假如只是求最后一个人的编号，那么该方法就复杂化了。
利用数学解法
在优化前，我们先来查找其中有没有什么数学规律：
假设总共5个人，每次数到3则移除。
每次移除一个人，将下一个人的编号映射为0，后面的人依次递增(注意因为是循环，所以之前在前面的人在经过删除后放在后面)。
条件:N = 5 ,m = 3
第一次排序(原始排序):0 1 2 3 4
移除第3个人后的排序结果:3 4 0 1
重新排序后的结果:0 1 2 3
此时，重新排序和原始排序的关系
（new + m）% N，其中new代码新编号，m表示第几个人被删除，N是总人数，现在是5
再移除第3个人后的排序结果:3 0 1
重新排序后的结果:0 1 2
此时，重新排序和原始排序的关系
（new + m）% (N-1)
再移除第3个人后的排序结果:0 1
重新排序后的结果:0 1
此时，重新排序和原始排序的关系
（new + m）%(N-2)
再移除第3个人后的排序结果:1
重新排序后的结果:0
此时，重新排序和原始排序的关系
（new + m）%(N-3)
最后一个人被移除，此时他的编号为0
这个0，是经过了多次重新排列后的编号，因为只有一个人了，所以它总是0，但并不是最原始的编号。我们需要从这个0推导回原始的编号。
结论: 按照删除逻辑，5个人，最后应该剩余编号为3的人。那么我们需要从0推导回3。
这个0是经过多次变更的，和原始的编号有什么关系呢？还能找回去吗？中间删除的元素，重新排列的编号等等会产生影响吗？
我们应该这样思考:
- 对于中途被移除的编号，我们不考虑它，因为不管它们怎么变，都是提早被移除的。而我们需要的是最后一个移除的编号。
- 对于最后一个编号(或者这个人)，可以看到他始终在我们的转化体系内，无非就是 原始编号->算法1->编号1->算法2->编号2->算法3->编号3....
而在上面的过程中，我们知道这些算法是可逆的。因此把整个过程倒过来计算即可。
从最后1个人推导出剩余2个人的时候的编号:
最后1个人在剩余2个人的时候的编号fn2 = (new + m) % 2 = (0 + 3) % 2 = 1
最后1个人在剩余3个人的时候的编号fn3 = (new + m) % 3 = (fn2 + 3) % 3 = (1 + 3) % 3 = 1
最后1个人在剩余4个人的时候的编号fn4 = (new + m) % 4 = (fn3 + 3) % 4 = (1 + 3) % 4 = 0
最后1个人在剩余5个人的时候(也就是最开始的时候)的编号fn5 = (new + m) % 5 = (fn4 + 3) % 5 = (0 + 3) % 5 = 3
结果就为3
注意:我们总是从计算fn2往回推到，此时的人数是2。这是因为最后一个人的经过多次调整的编号总是0，不用计算。
因此，我们可以使用循环来完成这个过程,时间复杂度为O(n)。
// 该算法第一个人的编号为0。如果要为1，则将结果加1即可
void find() {
int fn = 0;
for (int i=2; i<=5; i++) {
fn = (fn + 3) % i;
}
printf("origin fn = %d\n",fn);
}
控制台输出:
origin fn = 3
现在，只需要将算法中的5和3替换为相应的N和m即可。
