Question

c++约瑟夫环问题

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

Answer 1

#include <iostream>
using namespace std;

struct node
{
int num;
int key;
node *next;
};

node* creatlist(const int &n);
node* play(node *head,int m);

int main()
{
int m,n;
cout<<"请输入小朋友人数和起始上线："<<endl;
cin>>n>>m;
node *head=creatlist(n);
play(head,m);
return 0;
}

node* creatlist(const int &n)
{
node *head=0,*temp=0,*tem=0;
int i=0;
for(i=1;i<=n;++i)
{
temp=new node;
temp->num=i;
if(!head)
{
head=temp;
}
else
{
tem->next=temp;
}
cout<<"请输入"<<i<<"号小朋友的密码："<<endl;
cin>>temp->key;
tem=temp;
}
temp->next=head;
return head;
}

node* play(node *head,int m)
{
node *temp=head,*tem;
for(tem=temp;tem->next!=temp;tem=tem->next);
for(int i=0;temp!=temp->next;temp=temp->next)
{
++i;
if(i==m)
{
tem->next=temp->next;
m=temp->key;
cout<<"第"<<temp->num<<"号小孩出列"<<endl;
delete temp;
temp=tem;
i=0;
}
else
{
tem=tem->next;
}
}
cout<<"第"<<temp->num<<"号小孩出列"<<endl;
cout<<"第"<<temp->num<<"号小孩获胜"<<endl;
return temp;
}

#include <iostream>
using namespace std;
#define N 10
#define count 3

struct node//结构体结点，用来存放小孩的编号和下一个小孩的位置
{
int n;//编号
node *next;//下一个小孩的地址
};

int main()
{
int i;//计数变量
node *head,*p,*l;//辅助指针

head=l=new node;//做出圈子,做出一个单循环链表存放小孩的编号
l->n=N;//确定最后一名小孩的编号
for(i=N-1;i>0;)//确定其他小孩的编号
{
p=new node;
p->n=i--;
p->next=head;
head=p;
}
l->next=head;//让最后一个结点指向第一个结点，将链表接成循环的

for(i=1;p!=p->next;)//游戏
{
i++;//计数
l=p;
p=p->next;
if(!(i%count))//判断该小孩是否要离开
{
cout<<"第"<<p->n<<"号小孩离开"<<endl;
l->next=p->next;
delete p;//清楚该小孩所在结点，并让上一个结点指向下一个结点
p=l;
}
}
cout<<"第"<<p->n<<"号小孩获胜！"<<endl;

return 0;
}
很果断的拿出了作业