Question

约瑟夫环的实现

编写程序，模拟约瑟夫环（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（主函数）中。
谁能接我具体的解释下啊,我学的不太好!
test6_Seq.cpp：

#include<iostream.h>
#include<stdlib.h>
typedef int ElemType;
struct list{
int maxsize;
ElemType *elem;
ElemType *mima;
};
#include "test6_Seq.h"
void main()
{
int i,x,n,t;
ElemType m;
list josephus;
cout<<"输入人数和初始密码：";
cin>>n>>m;
josephus.maxsize=n;
Intlist(josephus); //申请空间
for(i=1;i<=n;i++)
{
putlist(josephus.elem,i,i-1); //标记人的编号
cout<<"第"<<i<<"个人的密码:";
cin>>x;
putlist(josephus.mima,x,i-1); //插人密码
}
cout<<"淘汰的人的编号:"<<endl;
do{
m=delelist(josephus,m); //删除并返回值
}while((t=liseEmpy(josephus))!=0); //判断是否为空

}

Answer 1

首先你要明白该程序在主函数中调用的函数都在头文件“#include "test6_Seq.h" ”里。这些函数有（Intlist(josephus); ，putlist(josephus.elem,i,i-1); ，m=delelist(josephus,m); ，liseEmpy(josephus))!=）。如果你不知道该函数里的内容，此程序你很难明白。
我给你写了一个我自己写的程序。
#include<iostream.h>
typedef int ElemType;
struct LNode{ //定义一个LNode类型的结构
ElemType data;
LNode* next;
};
void Josephus(int n,int m,int s);//n为总人数，s为起始位置，m为间隔

void main( )
{
int i,j,k;
cout<<"请输入人数n:";
cin>>i;
cout<<"请输入起始位置:";
cin>>k;
cout<<"请输入间隔:";
cin>>j;
Josephus(i,j,k);
}
void Josephus(int n,int m,int s)
{
LNode* HL=NULL;
int i;
for(i=n;i>=1;i--){ //for循环形成一个环
LNode* newptr=new LNode;
newptr->data=i;
if(HL==NULL){newptr->next=newptr;HL=newptr;}
else {newptr->next=HL->next;HL->next=newptr;}
}
LNode *ap=HL,*cp=HL->next; //找到第一个位置
for(i=1;i<s;i++){
ap=cp;
cp=cp->next;
}
for(i=1;i<n;i++){ //找到一个删除一个
for(int j=1;j<m;j++){
ap=cp;
cp=cp->next;
}
cout<<cp->data<<' ';
ap->next=cp->next;
delete cp;
cp=ap->next;
}
cout<<cp->data<<endl;
delete cp;
}

Answer 2

我自己想的PASCAL约瑟夫程序 很简单的
program zhangyuxiang(input,output);
var
m,n,i,j,w,k,jiance,b,c:integer;
a:array [1..10] of integer;

procedure first;
begin
for i:=1 to m do
if a[i]<>0
then k:=a[i];
end;

procedure second;
begin
jiance:=0;
for b:=1 to m do
if a[b]<>0
then jiance:=a[b];
if jiance<>0 then
begin
j:=j+1;
if j>m then j:=1;
if a[j]<>0 then w:=w+1;
if w<>n then second;
end;
end;

procedure third;
begin
jiance:=0;
for c:=1 to m do
if a[c]<>0
then jiance:=a[c];
end;

begin
writeln('This program only made by zhangyuxiang');
writeln('please input n');
m:=10;
read(n);
for i:=1 to m do
a[i]:=i;
j:=0;

repeat
w:=0;
first;
second;
a[j]:=0;
third;
until jiance=0;
writeln(k)
end.