本文共 1146 字，大约阅读时间需要 3 分钟。

描述

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

输入

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

输出

7 (剩下的那个)

样例输入

8 1 3

样例输出

7

#include 
   
    using namespace std;struct Node{    int data;    struct Node *next;};class List{private:    Node *rear;public:    List(int n);    void solved(int m,int k);};List::List(int n){    Node *s=NULL;    rear=new Node;    rear->data=1;    rear->next=rear;//头尾结点等同于一个结点形成循环链表    for(int i=2; i<=n; i++)    {        s=new Node;        s->data=i;        s->next=rear->next;        rear->next=s;        rear=s; //方便后续的插入，移动rear结点也就是新加入的s变为rear结点    }    //rear=rear->next;//回到最初的第一个结点}void List::solved(int m,int k){    Node *pre=rear,*p=rear->next;//初始化两个工作指针    int cnt=1;    for(int i=1; i
    
     next;//工作指针同时后移，寻找开始的k    }    while(p->next!=p)    {        if(cnt
     
      next;//工作指针同时后移            cnt++;        }        else{            pre->next=p->next;//将结点p摘链            delete p;//移除节点            p=pre->next;//重新初始化结点p            cnt=1;        }    }    cout<
      
       data<
       
        >n>>k>>m;    List A(n);    A.solved(m,k);    return 0;}
       
      
     
    
   

转载地址：http://troo.baihongyu.com/