约瑟夫环（链表法，公式法）

约瑟夫环作为一个数学问题，它的代码实现方式有很多，比如循环链表，公式解决或者动态规划，之前参考资料也有用递归解决的。Anyway，这些都是解决约瑟夫环问题很有效的方法。这里总结两种方法，循环链表法和公式法。
首先是循环链表法，它的原理很简单，也很容易理解。求解过程和人思考解决的过程很接近。设总人数为N，报数为M的人淘汰。第一步就是建立一个循环链表，这样就把从1到N的数据头尾连接起来了，第二部就是去循环报数，报数为M的进行链表的删除操作。循环条件是总人数N！=1，即只要剩下的总人数不为1，就一定没有循环结束。最后输出指针指向那个节点的数就OK了。
要注意的问题：
1：设置一个judge来专门进行报数以及判断是否要删除当前节点。因为每删除一个数后，就要重新从1开始报数，即judge的值重置为1。也可以在判断时对judge取余看结果是否为0来确定是否需要删除，这种方法则不需要重置Judge.
2：如果有头结点，设置初始指针时应指向head->next而不是指向head，因为此时head并没有实际意义，数据是从head->next开始储存的，包括再建立循环链表时，最后的指针也要指向head->next。
3：由于建立的是单向链表，所以只能检索当前节点的下一个而不能回溯。因此在删除操作时应提前一步进行删除。举个例子，假如报数为3的淘汰，当前节点如果已经检索到3这个位置，应把2号为与4号相连来删除3号，但当前为3号为且不能回溯，因此这样就GG了。解决方法就是我们提前判断，在当前节点时就判断3要被淘汰，直接把当前节点与44号连接，即当前的next->next。
以下是代码实现。

#include<bits/stdc++.h>
using namespace std;
struct ListNode
{
    int date;
    ListNode *next;
};
class List
{
    ListNode *head;
public:
    List(){head=new ListNode;head->next=NULL;}
    void Josephus();
    void DisPlay();
};
void List::Josephus()
{
    int Count,m;
    cout<<"请输入总人数以及淘汰的号码数"<<endl;
    cin>>Count>>m;
    ListNode *s,*r;
    r=head;
    for(int i=1;i<=Count;i++)
    {
        s=new ListNode;
        s->date=i;
        r->next=s;
        r=s;
    }
    r->next=head->next;
    ListNode *p1=head->next;
    int judge=1;
    while(Count!=1)
    {
        if(judge+1==m)
        {
            ListNode *p2=p1->next->next;
            p1->next=p2;
            p1->next->date=p2->date;
            p1=p1->next;
            judge=0;
            Count--;
        }
        else p1=p1->next;
        judge++;
    }
    cout<<"幸存者是"<<p1->date<<"号"<<endl;
}
int main()
{
    List A;
    A.Josephus();
    return 0;
}

至于公式法就so easy了。按照公式f(n,m)=(f(n-1,m)+m)%n进行就OK。n为总人数，m为要被淘汰的数。具体函数实现有两种：递归和循环。至于公式为什么成立，怎么得到的。好多博主写的相当好，这里就不在赘述了。
以下是代码实现。

#include<bits/stdc++.h>         //公式法解决约瑟夫环
using namespace std;
int cir(int n,int m)                 //循环实现
{
    int p=0;
    for(int i=2;i<=n;i++)
    {
        p=(p+m)%i;
    }
    return p+1;
}
int cir(int n,int m)                 //递归实现
{
    cout<<"ls"<<endl;
    int p=0;
    if(n==1) return p;
    else return p=(cir(n-1,m)+m)%n;
}
int main()
{
    int n,m;
    cin>>n>>m;
    cout<<cir(n,m)<<endl;
    return 0;
}

以上。