高校问答许君聪笑傲江湖红色:约瑟夫问题
来源：百度文库 编辑：高校问答 时间：2024/04/19 12:15:47
用数据结构（单向环形链表）及C++的知识写一段程序：
N个人围成圆圈，从1开始报数，到第M个人令其出列，然后下一个人继续从1开始报数，到第M个人令其出列，如此下去，直到只剩一个人为止。显示最后一个人为剩者。
N个人围成圆圈，从1开始报数，到第M个人令其出列，然后下一个人继续从1开始报数，到第M个人令其出列，如此下去，直到只剩一个人为止。显示最后一个人为剩者。
没写注释，请耐心点阅读。
#include<iostream.h>
class Node
{
public:
int flag;
int data;
Node * next;
};
void main()
{
int n,m,i,count=0;
Node * p,* pp,* Head,*pre;
cout<<"请输入n:"<<endl;
cin>>n;
cout<<"请输入m:"<<endl;
cin>>m;
Head =new Node;
Head->next=NULL;
Head->flag=1;
Head->data=1;
p=Head;
for(i=0;i<n-1;i++)
{
pp=new Node;
p->next=pp;
p=p->next;
p->flag=1;
p->data=i+2;
}
p->next = Head;
pre=p=Head;
i=1;
for(;;)
{
if(p->flag==1)
{
if(i==m)
{
p->flag=0;
i=0;
count++;
if(count==n-1)
break;
}
i++;
}
pre=p;
p=p->next;
}
for(i=0;i<n;i++)
{
cout<<Head->flag;
if(Head->flag==1)m=Head->data;
Head=Head->next;
}
cout<<endl<<"最后剩下的是第"<<m<<"位."<<endl;
}
就是定义一个节点指针。当指到第M个节点时就删去M，如此循环下去。直到只有一个节点。