约瑟夫环问题

#约瑟夫环问题

约瑟夫环对于学过算法的应该很熟悉了吧，其问题描述一般是如下情景：
* N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3，求最后剩下的人的编号

解决这个问题也很容易想到循环链表，我们只需要创建一个无头节点的循环链表，然后从第一个开始计数。每移动一个节点索引加一，直到索引等于M时移除该节点，然后将索引重置为1，循环至仅剩一个节点即可

代码实现：

typedef struct node {
    int data;
    node* next;
} node;
void create(node*& L, node*& r, int n) {
    L = new node; 
    L->data = 1; 
    r = L;
    for (int i = 1; i < n; i++) {
        node* s = new node; 
        s->data = i + 1; 
        r->next = s; 
        r = s; 
    }
    r->next = L; 
}
void out(node*& p, node*& pre, int k, int m) {
    while (--k) {
        p = p->next;
        pre = pre->next;
    }
    int i = 1;
    while (p->next != p) {
        if (i == m) { 
            i = 1; 
            cout << p->data << " ";
            pre->next = p->next; 
            delete p; 
            p = pre->next; 
        } else { 
            pre = pre->next;
            p = p->next;
            ++i;
        }
    }
cout << p->data << endl;
}

但这太复杂了不是吗
我们不仅要手搓一个循环链表，还容易访问超界（我第一次写就这样）

所以我们有一个更简单的方式解决这个问题：递归实现

先看数学公式：

f(N,M)=(f(N−1,M)+M)%n

为了理解这个公式，我们先假设有n个人，编号分别从0到n-1:

0, 1, 2, 3, 4, 5, 6 … (M-1)%n, M%n, (M+1)%n … n-2, n-1

显然，第(M-1)%n个是第一个嗝屁的
这时可能有人会想：我们为什么要用%n来表示编号呢？直接写M-1不是一样的吗？

很简单，我们去掉那个第一个嗝屁的倒霉蛋之后，从他的下一个开始数，就可以得到一个新的序列：

M%n, (M+1)%n, (M+2)%n … n-1, 0, 1, 2, 3 … (M-2)%n

那么对他们重新编号后就可以得：

0, 1, 2 ………….. n-2

相互对比后，我们可以很容易根据%n判断出上面的序列是在n个人时排的，下面编号n_2与上面编号n_1的对应关系便是：

n_1 = (n_2 + M)%n

这就是上面的序号为什么要加一个%n

代码实现：

int cir(int n,int M)
{
    int p=0;
    for(int i=2;i<=n;i++)
    {
	    p=(p+M)%i;
    }
    return p+1;
}

这样就解决了