约瑟夫环问题

描述：

约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

输入8 1 3 (n=8 k=1 m=3 )

输出7 (剩下的那个)

样例输入

8 1 3

样例输出

7

#include<cstdio>
using namespace std;
struct Node
{
    int date;
    Node*next;
};
int main()
{

    int n,star,out;
    scanf("%d%d%d",&n,&star,&out);
    Node *head,*s,*p,*q;
    s=new Node;
    s->date=1;
    head=s;
    q=s;///保存下来头结点的位置
    for(int i=2;i<=n;i++)
    {
        p=s;
        s=new Node;
        s->date=i;
        p->next=s;
    }
    s->next=head;///成环
    for(int i=1;i<star;i++)
    {
        q=q->next;
    }
    while(q->next!=q)
    {
        for(int i=1;i<out-1;i++)
        {
            q=q->next;
        }
        p=q->next;
        q->next=p->next;
        delete(p);
        q=q->next;///注意这个地方，上面out-1找出的是将要删去的前一个，删除后，从第一个元素开始，第一个元素应为q->next
    }
    printf("%d
",q->date);
    return 0;
}