Question

模拟约瑟夫环（josephus）问题

1、编写程序，模拟约瑟夫环（josephus）问题： n个人（编号为1，2，3，……，n (n>0) ）按顺时针方向围坐一圈，每人持有一个正整数密码。开始时任意给出两个值：一个为首先报数的人的编号i (0<i<=n)，另一个为起始报数上限值m。接着从编号为i的人开始按顺时针方向自1起顺序报数，报到m时停止报数，且报到m的人出列，并将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新自1报数，……，如此下去，直到所有人全部出列为止。要求设计一个程序模拟此过程，给出出列人的编号序列。

基本要求:

（1） 人数n、每人的正整数密码、首次报数人编号i、初始报数上限值m均由键盘输入。

（2） 参照线性表的抽象数据类型定义，设计本实验的抽象数据类型。

（3） 根据你设计的抽象数据类型，分别用顺序存储结构和链式存储结构实现约瑟夫环问题。并请分别将顺序存储结构的程序存放在文件test6_Seq.h（基本操作函数）、test6_Seq.cpp（主函数）中，链式存储结构的程序存放在文件test6_Link.h（基本操作函数）、test6_Link.cpp（主函数）中。

（4） 设计测试数据，并调试程序，直到正确运行。

Answer 1

#include <stdio.h>
#include <stdlib.h>
typedef struct Lnode{
int data;
struct Lnode *next;} Lnode;

Lnode* create(int n)
{//建立共有n个结点的单循环链表h
int i;
Lnode *h,*p;//p为当前新生成结点的指针
Lnode *r=(Lnode *)malloc(sizeof(Lnode));//r为尾指针
r->data=n;h=r;//h为头指针
for(i=n-1;i>0;i--)//头插法建立链表
{p=(Lnode *)malloc(sizeof(Lnode));
p->data=i;
p->next=h;
h=p;
}
r->next=h ; //形成环
return h;
}

void jeseph(Lnode *p,int m)
{//从约瑟夫环中输出出列人的编号
Lnode *q;
int j=0;
printf("出队序列为:\n");
do{
j++;
if (j==m-1)
{
q=p->next;
p->next=q->next;
printf("%d ",q->data);
j=0;free(q);
}
p=p->next;
}while(p->next!=p);
printf("%d\n",p->data);
free(p);
}

void main()
{
Lnode *h;
int m,n;
printf("\n请输入n和m的值：");
scanf("%d,%d",&n,&m);
h=create(n) ;
jeseph(h,m);
}
执行程序结果为：
请输入n和m的值：12 , 4
出队序列为:4，8，12，5，10，3，11，7，6，9，2，1
执行程序结果为：
请输入n和m的值：7，20

Answer 2

program haonan;
var
a: array [1..200] of integer;
i,n,j,renshu,m,qishiweizhi,tuichu,biaohao:integer;
begin
read(m,n);
renshu := m;
qishiweizhi := 1;
biaohao := 0;
for i := 1 to m do
a[i] := i;
for i := 1 to m do
begin
tuichu := (n+qishiweizhi-1) mod renshu;
if tuichu = 0 then
tuichu := renshu;
write(a[tuichu],' ');
biaohao := biaohao + 1;
for j := tuichu to (renshu - 1) do
a[j]:=a[j+1];
qishiweizhi := tuichu;
renshu := renshu - 1;

if biaohao mod 10 = 0
then
writeln;
end;
readln;
readln;
readln;
readln;
readln;
end.

Answer 3

#include<stdio.h>
#include<malloc.h>
typedef struct Node
{
int num;
int cipher;
struct Node *next;
}Node;

void Joesphproblem(struct Node *L,int n,int m)
{struct Node *s,*p;
int countperson=1,count=0;
s=L;
p=L->next;
while(countperson<=n)
{if(p==NULL) /使得p,s指针在循环过程中跳过头结点和尾结点/
p=p->next;
if(p==L)
p=p->next;
if(s==NULL)
s=s->next;
if(s==L&&countperson!=1&&m!=1) /其中当钥密为1时，就不能使s指向头结点的下一位/
s=s->next;
count++;
if(count==m)
{printf("the %d person num and cipher:",countperson);
printf("(%d,%d)",p->num,p->cipher);
m=p->cipher;
s->next=p->next; /修改出列指针/
free(p); /删除出列结点/
p=s->next; /指向出列结点的指针后移/
count=0; /计数器清零/
countperson++; /出列人数计数器加1/
printf("\n");
}
else /不是所报数时，指针自动后移/
{s=s->next;
p=p->next;
}
}
}
struct Node *create_sl(int n,int m)
{struct Node *head,*pt,*p;
int i=0,j;
p=(struct Node*)malloc(sizeof(struct Node)); /开辟一个储存单元/
head=pt=p; /令head，pt,p指针指向头结点/
for(j=0;j<=n;j++)
{pt->next=p;
pt=p;
i=i+1;
p=(struct Node*)malloc(sizeof(struct Node));
p->num=i;
p->cipher=m;
}
p->next=NULL;
pt->next=head;
return(head);
}
void print(struct Node *L)
{
struct Node *p,*head;
head=L;
p=L->next;
while(p!=NULL&&p!=head)
{
printf("（%d %d）",p->num,p->cipher);
p=p->next;
}
printf("\n");
}
void main()
{int n,m;
struct Node *L;
printf("please input n:");
scanf("%d",&n);
printf("please input m:");
scanf("%d",&m);
L=create_sl(n,m);
printf("the L is:\n");
print(L);
Joesphproblem(L,n,m);
}
输入：m值为5 n 值1时和m值为5 n值为3查看就知道了