采用链表解决约瑟夫问题：有n个人围坐在一起形成头尾相接的一个环,从第m个人开始报数,每次有人数到r时,这个人就离开.请输出所有人的离队顺序.
来源：学生作业帮助网 编辑：六六作业网 时间：2024/11/17 03:54:26
采用链表解决约瑟夫问题：有n个人围坐在一起形成头尾相接的一个环,从第m个人开始报数,每次有人数到r时,这个人就离开.请输出所有人的离队顺序.
采用链表解决约瑟夫问题：有n个人围坐在一起形成头尾相接的一个环,从第m个人开始报数,每次有人数到r时,
这个人就离开.请输出所有人的离队顺序.
采用链表解决约瑟夫问题：有n个人围坐在一起形成头尾相接的一个环,从第m个人开始报数,每次有人数到r时,这个人就离开.请输出所有人的离队顺序.
/*
有n个人围坐在一起形成头尾相接的一个环,从第m个人开始报数,每次有人数到r时,zhe
*/
#include
using namespace std;
// 表示一个犯人的结构体
struct Prisoner
{
// 编号
int id;
// 密码
int pass;
// 用于链表的指针
struct Prisoner * pre;
struct Prisoner * next;
};
class JosephCircle
{
public:
// 基本的约瑟夫构造函数
JosephCircle(int N,int M,int R);
// 输出约瑟夫环
void print();
// 开始处决犯人
void start();
private:
int N,M,R;
// 约瑟夫环的头指针
struct Prisoner * head;
// 第一个被处决的犯人的节点指针
struct Prisoner * firstPunishedPrision;
};
JosephCircle::JosephCircle(int N,int M,int R)
{
this->N = N;
this->M = M;
this->R = R;
struct Prisoner * p , *pr;
// 约瑟夫环的头指针初始化为空
this->head = NULL;
// 构造一个由 N 个犯人组成的约瑟夫环
for(int i=1;ihead == NULL)
{
// 新增一个犯人
p = new struct Prisoner();
// 犯人编号
p -> id = i;
// 犯人密码
p -> pass = R;
// 紧挨着的下一个犯人（因为是环状的,每个人都会有紧挨着的其他犯人）
p -> pre = p;
p -> next = p;
// 约瑟夫环的头指针
this->head = pr = p;
}
else
{
p = new struct Prisoner();
p -> id = i;
p -> pass = R;
p -> pre = pr;
p -> next = pr->next;
pr -> next -> pre = p;
pr -> next = p;
pr = p;
}
}
// 寻找约瑟夫环里面第一个被处决的犯人的【节点指针】
firstPunishedPrision = head;
for(int i=2;ifirstPunishedPrision = this->firstPunishedPrision -> next;
}
}
// 输出约瑟夫环
void JosephCircle::print()
{
cout pre = q -> pre;
p = p -> next;
// 输出被处决的犯人的信息
cout