C++ 约瑟夫环问题

假设有n个人的一个小组，按顺时针围坐一圈，一开始任选一个正整数作为报数的上限m，从第一个人开始按顺时针方向自1开始报数，报到m的人出圈，然后从他下一个开始从1重新开始报数，报到m的人出圈。如此下去，知道所有人都出圈为止。
（1） 出圈游戏一：使用动态数组来接收输入，参加的人数和报数上限可变
（2） 出圈游戏二：使用循环链表来接受输入，参加的人数和报数上限可变
（3） 参加游戏者的编号和姓名存入文件play.txt中，按出圈顺序将出圈者的编号和姓名存入文件result.txt中。
（4） 利用菜单提供用户界面，菜单格式如下：
1. 出圈游戏一
2. 出圈游戏二
3. 输出出圈游戏一结果
4. 输出出圈游戏二结果
5. 退出
选择1，2时分别进行出圈游戏，且将结果保存在文件中，选择3，4时，在屏幕上输出相应结果

# include
# include
struct stu
{
int num;
struct stu *next;
};
int m,n;struct stu *p,*q,*s;
struct stu *create()
{
struct stu *head,*s1,*r;
int i;

head=NULL;
for(i=1;i<=n;i++)
{
s1=(struct stu *)malloc(sizeof(struct stu));
s1->num =i;
if(head==NULL)head=s1;
else r->next =s1;
r=s1;
}
if(r) r->next =head;
return head;
}
struct stu * get_index(struct stu *head,int k)
{
int j=1;
if (k<1)
{
printf ("输入错误\n");
return NULL;
}
s=head;
while (s && j {
s=s->next ;j++;
}
return s;
}
void f1 (struct stu *head,struct stu *h)
{
int x,i;
x=m/2;
p=h;
i=1;printf ("依次出列的人的编号为:");
while (p->next!=p)
{
q=p->next;
for (i=1;i {p=q->next;q=p->next;}
p->next =q->next ;
printf ("%d ",q->num);
free(q);
p=p->next ;
}
printf ("最后剩下的人的编号为%d\n",p->num );
}
void f2 (struct stu *head,struct stu *h)
{
int i,x;
x=m/2;
i=1;
p=h;
printf ("依次出列的人的编号为:");
do
{
for (i=1;i<=x;i++)
{q=p->next ;p=q->next ;}
q->next =p->next ;
printf ("%d ",p->num);
free(p);
p=q->next ;
}
while (q->next!=q);
printf ("\n最后剩下的人的编号为%d\n",q->num);
}
void main ()
{
int k;
struct stu *head,*h;
printf ("请输入总人数：");
scanf ("%d",&n);
printf ("请输入退出圈子的人的编号：");
scanf("%d",&m);
printf ("请输入开始报数的人的编号:");
scanf ("%d",&k);
head=create ();
h=get_index(head,k);
if (m%2==0) f1(head,h);
else f2(head,h);
}

绝对可以运行！

前面几位貌似用C语言编写的，我这有个C++的，见笑了

#include
#include

//=============================================================
class Josephuscircle;
//=============================================================
class Josephusnode
{
int number;
Josephusnode * next;
public:
friend class Josephuscircle;

};
//============================================================
class Josephuscircle
{
private:
Josephusnode *head, *current;
int total,count,start; //定义三个参数分别作为总人数、
//报数长度、起始位置
public:
Josephuscircle (); //构造函数
~Josephuscircle (){delete [] head;} //析构函数
void counting(); //报数函数
};
//===========================================================
Josephuscircle::Josephuscircle()
{
int n,k,m;
cout<<">>>输入圈中的人数,报数长度,起始位置：";
loop:
cin>>n>>k>>m;
cout< if(n<=0||k<=0||m<=0||m>n)
{
cout<<">>>初始化参数不合法！"< cout<<">>>请重新输入参数！\n"< goto loop;
}

total=n; //====
count=k; //初始化参数
start=m; //====

head=current=new Josephusnode; //====
head->number=0; //创建表头
head->next=NULL; //====

for(int i=1;i<=total;++i)
{
current=current->next=new Josephusnode; //创建并初始化链表
if(current==NULL)
{
cerr<<"Memory Allocation Failed!"< return;
}
current->number=i;
}

current->next=head->next; //首尾连接形成循环链表
current=head; //当前指针指向表头

}
//===========================================================
void Josephuscircle::counting()
{
for(int i=1;i {
current=current->next; //将当前指针指向报数的起始位置
head->next=current;
}

Josephusnode *temp; //中转节点
int k=total;

while(k>1)
{
for(int j=1;j current=current->next; //报数

temp=current->next; //跳过将要被删除的节点
current->next=temp->next;

cout<<">>第"<number<<"号出局。\n";

delete temp; //删除节点
k--; //删除一个结点后表的长度减一
}

cout<<">>剩下的人是第："<next->number<<"号。"< delete [] current->next;

}

//===========================================================
int main()
{
char c;
loop1:
Josephuscircle Josephus; //定义一个对象并初始化
Josephus.counting(); //从链表中删除相关节点
cout<
/*以下语句用于循环执行*/
loop2:
cout<<">>>是否重新开始?(Y/N)"< cin>>c;
if(c=='y'||c=='Y')
goto loop1;
else
if(c=='N'||c=='n')
return 0;
else
{
cout<<">>>输入字符不正确!"< cout<<">>>请重新选择操作!"< goto loop2;
}
}

#include

using namespace std;

int main() {
int m, n;
while (cin >> n >> m) {
int* a = new int[n];
for (int i = 0; i < n; i++) a[i] = i + 1;
int j = 1; //用于报数
int k = 0; //遍历数组
int l = n; //跟踪剩余人数
while (l > 1) {
if (a[k]) {
if (j++ == m) { //报到m出局
j = 1;
a[k] = 0;
l--;
}
}
if (++k == n) k = 0; //循环数组
}
while (a[--i] == 0);
cout << a[i] << endl;
delete[] a;
}
return 0;
}

和找猴王的问题是一样的..代码如下:
#include
#include

/********************** Type Define *******************************/
typedef struct node
{
int location;
struct node *next;
}King;
/***************************************************************************/

/***************************************************************************/
/* Function: create(int n) */
/* Parament: */
/* n presents the number of monkeys */
/* Return : */
/* h presents the hear of the monkey queue */
/***************************************************************************/
King * create(int n)
{
King *p,*h,*s;
int i;
if((h=(King*)malloc(sizeof(King)))==NULL)
{
printf("分配内存空间失败....\n");
return NULL;
}
h->location=1;
h->next=h;
p=h;
for(i=1;i {
if((s= (King *) malloc(sizeof(King)))==NULL)
{
printf("分配临时内存空间失败....\n");
return NULL;
}
s->next=p->next;
p->next=s;
s->location=i+1;

p=s;
}
return(h);
}

void main()
{
int number;
King *head,*current;
int outnumber=13;
int count=1;
char ch;

printf("|---------------------------------------------------------------------|\n");
printf("|\t\t\t 猴王问题(循环链表实现) \t\t |\n");
printf("|---------------------------------------------------------------------|\n");

while(1)
{
printf("请输入猴子的个数(大于13):");
scanf("%d",&number);
if(number>=13)
break;
}

head=create(number);
if(head==NULL)
printf("创建失败...");
else
{
printf("----------------------------------------------------------------\n");
current = head;
do{
count+=1;
if(count==outnumber)
{
King *del;
del=current->next;
printf("\t%2d号猴子退出..退出条件:%2d..",del->location,outnumber);
head=del->next;
current->next=head;
current=head;
outnumber-=1;
number-=1;
printf("还有%2d个猴..\n",number);
count=1;
free(del);
if(outnumber==1&&number!=1)
outnumber=13;
}
else
current=current->next;

if(head->next==head)
{
printf("----------------------------------------------------------------\n");
printf("\t\t\t猴王是%d号\n",head->location);
break;
}
}while(head->next!=head);

}
ch=getchar();
}

O(∩_∩)O哈哈~，我书上一模一样的答案

要打，麻烦

#include
using namespace std;
struct child
{
int num ;
child *link ;
} ;
void init(int n) ; //初始化函数
void gameStart(int n,int m) ; //模拟游戏函数
child *head ; //链表头
child *present ; //当前结点
child *end ; //链表尾
int main( )
{
int n , m ;
cout << "请输入孩子个数:" ;
cin >> n ;
cout << "请输入正整数 m:" ;
cin >> m ;
init ( n ) ;
gameStart(n , m);
cout << "第" << present->num << "个孩子将获得胜利!" << endl ;
delete present ;
return 0 ;
}

void init (int n)
{
head = new child ;
head -> num = 1 ;
present = head ;

for(int i = 1 ; i < n ; i++)
{
present -> link = new child;
present -> link -> num = i + 1;
present = present -> link ;
}

present -> link = head ;
end = present ;
present = head ;
}

void gameStart(int n,int m)
{
child *pGuard=end; //指向待删除结点的前驱结点，起初应指向表尾
while(n != 1)
{
for(int j = 1 ; j < m ; j++)
{
pGuard = present ;
present = present ->link ;
}

pGuard ->link = present->link ;
delete present ;
present = pGuard ->link ;
n-- ;
}

}
我运行过了，OK！