Question

约瑟夫环问题 设计一个带头结点的循环单链表类，实现约瑟夫环问题； 问题描述：设编号为1,2,…，n(n>0)个

约瑟夫环问题
设计一个带头结点的循环单链表类，实现约瑟夫环问题；
问题描述：设编号为1,2,…，n(n>0)个人按顺时针方向围坐-圈，每人持有一个正整数密码。开始时任意给出一个报数上限值m从第一个人开始顺时针方向自1起顺序报数。报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新自1起顺序报数.如此下去，直到所有人全部出列为止。要求设计一个程序模拟此过程，并给出出列人的编号序列。
测试数据：
n=7,7个人的密码依次为3,1,7,2,4,8,4
初始报数上限值m=20
用C++

Answer 1

# include <stdio.h>

# define SIZE 20

int joseph(int a[],int m,int n)

{

int b[SIZE];

int i;

int flag=0;

int code;

int sum=n;

int point=0;

int num=m;

for(i=0;i<n;i++)

{ b[i]=i+1; }

while(sum!=0)

{

for(i=1;i<=num;i++)

{ if(point>=sum) point=1;

else point++;

}

num=a[point-1];

code=b[point-1];

for(i=point;i<=sum;i++)

{ a[i-1]=a[i];

b[i-1]=b[i];

}

sum--;

flag++;

point--;

printf("已退出%d人,退出的人的编号为%d.\n",flag,code);

}

return 0;

}

main()

{

int m,n,i;

int array[SIZE];

printf("约瑟夫环求解,当前设置最大人数为%d.\n",SIZE);

printf("报数上限:\n");

scanf("%d",&m);

printf("总人数为:\n");

scanf("%d",&n);

for(i=0;i<n;i++)

{

printf("第%d人的密码为:",i+1);

scanf("%d",&array[i]);

}

joseph(array, m, n) ;

return 0;

}

我用的是C语言，已经运行过没有问题。望采纳

Answer 2

用指针实现的循环单链表。
#include <iostream>
using namespace std;

struct Node
{
int m,num;//m是密码，num是他的编号
Node *next;
};

Node *head;
int M,N;

void Build()
{
cin>>N>>M;
Node *p=head;
for(int i=1;i<=N;i++)
{
Node *tmp=new Node;
cin>>tmp->m;
tmp->num=i;
if(i==1)head=p=tmp;
else p->next=tmp;
p=tmp;
}
p->next=head;
}

Node* Move(int step,Node* from)
{
Node *p=from;
for(int i=0;i<step;i++)
p=p->next;
return p;
}

void GO()
{
Node *p=head;
int step=M-1;
for(int i=1;i<N;i++)
{
p=Move(step-1,p);
step=p->next->m;
cout<<p->next->num<<endl;
p->next=p->next->next;
}
cout<<p->num<<endl;
}

int main()
{
Build();
GO();
return 0;
}