约瑟夫问题

有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);
}

控制台输出: