题目：n个数字（0,1,…,n-1）形成一个圆圈，从数字0开始，

每次从这个圆圈中删除第m个数字（第一个为当前数字本身，第二个为当前数字的下一个数字）。

当一个数字删除后，从被删除数字的下一个继续删除第m个数字。

求出在这个圆圈中剩下的最后一个数字。

这个问题数学上已经得出了递推公式

 递推公式: 　　f[1]=0; 　　f[i]=(f[i-1]+m)%i; (i>1)

当然我们就不推了，这里给出一个中规中矩的用环的方法来解决此问题

1 Node* Josephus(Node* Head,int m){ 2       Node* p=Head; 3       while(true){ 4             for(int i=0;i
     
      next; 6             if(p->next!=p){
   //还没到最后一个节点 7                    Node* temp=p->next; 8                    int tempdata=p->data; 9                    p->data=temp->data;10                    temp->data=tempdata;11                    p->next=temp->next;12                    free(temp);13             }else//就剩下一个节点了14                    break;15       }16       return p;17 }
     

 

 给出一个完成的程序

/*约瑟夫环，输入m,n,输出其序列，例如输入 5,3，输出：3 1 5 2 4*/#include 
     
      using namespace std;typedef struct Node {    int element;    Node *pNext;}Node,*LinkList;void InitList(LinkList& head){    head=(LinkList)malloc(sizeof(Node));    head->pNext=NULL;}int ListLength(LinkList head){    int length=-1;    LinkList p=head;    while (p!=NULL)    {        length++;        p=p->pNext;    }    return length;    }void main(){    cout<<"输入M："<
      
       >M;    cout<<"输入N："<
       
        >N;    LinkList head,rear;    InitList(head);    rear=head;    for (int i=1;i<=M;i++)    {        LinkList temp=(LinkList)malloc(sizeof(Node));        temp->element=i;        temp->pNext=NULL;        rear->pNext=temp;        rear=temp;    }    rear->pNext=head->pNext;    free(head);    head=rear->pNext;    i=1;    while (head->pNext!=head)    {        if (i%N!=0)        {            rear=head;            head=head->pNext;            i++;        }        else        {            rear->pNext=head->pNext;            cout<
        
         element<
         
          pNext;            i++;        }    }    cout<
          
           element<