Question

C++编程：约瑟夫环问题。

【基本要求】
古代某法官要判决N个犯人的死刑，他有一条荒唐的法律，将犯人站成一个圆圈，从第S个人开始数起，每数到第D个犯人，就拉出来处决，然后再数D个，数到的人再处决———直到剩下的最后一个可赦免。 发展的约瑟夫的描述： 古代某法官要判决N个犯人的死刑，但这N个人每人持有一个密码，他有一条荒唐的法律，将犯人站成一个圆圈，法官先给出一个密码M，从第S个人开始数起，每数到第M个犯人，就拉出来处决，再根据这个人所持有的密码F，然后再数F个，数到的人再处决，以此类推———直到剩下的最后一个可赦免。
【测试数据】
数据请自己添加。
用类进行编译

Answer 1

/*
【基本要求】
基本的约瑟夫的描述：
古代某法官要判决N个犯人的死刑，他有一条荒唐的法律，将犯人站成一个圆圈，
从第S个人开始数起，每数到第D个犯人，就拉出来处决，然后再数D个，数到的人再处决，
直到剩下的最后一个可赦免。

发展的约瑟夫的描述：
古代某法官要判决N个犯人的死刑，
但这N个人每人持有一个密码，他有一条荒唐的法律，将犯人站成一个圆圈，
法官先给出一个密码M，从第S个人开始数起，每数到第M个犯人，就拉出来处决，
再根据这个人所持有的密码F，然后再数F个，数到的人再处决，
以此类推直到剩下的最后一个可赦免。

【测试数据】
数据请自己添加。
*/
#include <iostream>
using namespace std;

// 表示一个犯人的结构体
struct Prisoner
{
// 编号
int id;
// 密码
int pass;
// 用于链表的指针
struct Prisoner * pre;
struct Prisoner * next;
};

class JosephCircle
{
public:
// 基本的约瑟夫构造函数
JosephCircle(int N,int S,int D);
// 发展的约瑟夫构造函数
JosephCircle(int N,int S,int M,int password[]);

// 输出约瑟夫环
void print();
// 开始处决犯人
void start();
private:
// 约瑟夫环的头指针
struct Prisoner * head;
// 第一个被处决的犯人的节点指针
struct Prisoner * firstPunishedPrision;
};

JosephCircle::JosephCircle(int N,int S,int D)
{
struct Prisoner * p , *pr;
// 约瑟夫环的头指针初始化为空
this->head = NULL;
// 构造一个由 N 个犯人组成的约瑟夫环
for(int i=1;i<=N;i++)
{
// 当前添加的犯人是第一个犯人，要特殊处理一下
if(this->head == NULL)
{
// 新增一个犯人
p = new struct Prisoner();
// 犯人编号
p -> id = i;
// 犯人密码
p -> pass = D;
// 紧挨着的下一个犯人（因为是环状的，每个人都会有紧挨着的其他犯人）
p -> pre = p;
p -> next = p;
// 约瑟夫环的头指针
this->head = pr = p;
}
else
{
p = new struct Prisoner();
p -> id = i;
p -> pass = D;
p -> pre = pr;
p -> next = pr->next;

pr -> next -> pre = p;
pr -> next = p;

pr = p;
}
}

// 寻找约瑟夫环里面第一个被处决的犯人的【节点指针】
firstPunishedPrision = head;
for(int i=2;i<=(S+D-1);i++)
{
this->firstPunishedPrision = this->firstPunishedPrision -> next;
}
}

JosephCircle::JosephCircle(int N,int S,int M,int password[])
{
struct Prisoner * p , *pr;
// 约瑟夫环的头指针初始化为空
this->head = NULL;
// 构造一个由 N 个犯人组成的约瑟夫环
for(int i=1;i<=N;i++)
{
// 当前添加的犯人是第一个犯人，要特殊处理一下
if(this->head == NULL)
{
// 新增一个犯人
p = new struct Prisoner();
// 犯人编号
p -> id = i;
// 犯人密码
p -> pass = password[i-1];
// 紧挨着的下一个犯人（因为是环状的，每个人都会有紧挨着的其他犯人）
p -> pre = p;
p -> next = p;
// 约瑟夫环的头指针
this->head = pr = p;
}
else
{
p = new struct Prisoner();
p -> id = i;
p -> pass = password[i-1];
p -> pre = pr;
p -> next = pr->next;

pr -> next -> pre = p;
pr -> next = p;

pr = p;
}
}

// 寻找约瑟夫环里面第一个被处决的犯人的【节点指针】
firstPunishedPrision = head;
for(int i=2;i<=(S+M-1);i++)
{
this->firstPunishedPrision = this->firstPunishedPrision -> next;
}
}
// 输出约瑟夫环
void JosephCircle::print()
{
struct Prisoner * p = this->head;
if(p != NULL)
{
do
{
cout << "[编号：" << p->id << "，密码：" << p->pass << "]" ;
if(p->next != this->head)
{
cout<<" -> ";
}
p = p->next;
}while(p != this->head);
}
cout << endl << endl;
}

// 开始处决犯人
void JosephCircle::start()
{
struct Prisoner * p = this->firstPunishedPrision,*pr,*q;
int counter = 1;
/*
因为约瑟夫环是一个循环链表（也就是一个圈），
当 p->next != p 的时候，说明圈里面还有多余一个的节点（犯人），
继续数数并处决犯人
*/
while(p->next != p)
{
// q 向当前被处决的犯人
q = p;
// 从约瑟夫环里面删除被处决掉的犯人
q -> pre -> next = q -> next;
q -> next -> pre = q -> pre;
p = p -> next;
// 输出被处决的犯人的信息
cout << "第 "<< (counter++) << " 个被处决的犯人编号：" << q->id <<endl;
// 寻找下一个将要处决的犯人
for(int i=1;i<=(q->pass-1);i++)
{
p = p->next;
}
// 释放内存（被处决掉的犯人）。
free(q);
}

// 输出被赦免的犯人的信息
cout << "被赦免的犯人的编号：" << p->id << endl << endl;;
}

int main(int argc, char *argv[])
{
// 基本的约瑟夫环： JosephCircle(int N,int S,int D);
JosephCircle j1 = JosephCircle(3,1,2);
j1.print();
j1.start();
// 发展的约瑟夫环： JosephCircle(int N,int S,int M,int password[]);
int pass[]={1,5,3};
JosephCircle j2 = JosephCircle(3,1,2,pass);
j2.print();
j2.start();
return 0;
}

Answer 2

#include <iostream>
#include <list>
using namespace std;

// 数学推理方法
int circle_math( int n, int m )
{
int ans = 0;
for( int i = 2; i <= n; i ++ )
ans = ( ans + m ) % i;
return ans + 1 ;
}

// 链表模拟方法
int circle( int n, int m )
{
list<int> data;
list<int>::iterator it, temp;

for( int i = 0; i < n; i ++ )
data.push_back(i);

it = data.begin();

while( data.size() > 1 )
{
for(int i = 1; i < m; i ++ )
{
it ++ ;
if( it == data.end() ) it = data.begin();
}
temp = it;
it ++;
if( it == data.end() ) it = data.begin();
data.erase( temp );
}
return *data.begin() + 1 ;
}

int main()
{
int n, m;
while( n != 0 )
{
cin >> n >> m;
cout << circle_math( n, m ) << endl;
cout << circle( n, m ) << endl;
}
return 0;
}

Answer 3

修改后的版本，解决初始m为1的情况。

#include<stdio.h>
#include<malloc.h>

typedef struct node{
int num;
int val;
struct node* next;
}listnode;
//两个结构体可以合并以减少程序复杂度
typedef listnode* linklist;

int main(){
int n,i,b,m,j;
linklist q=(listnode*)malloc(sizeof(listnode));
q->next=q;//即使只有一个元素，他也是个循环链表
listnode *p;
printf("请输入总人数:");
scanf("%d",&n);
p=q;
for(j=1;j<=n;j++){
printf("请输入第 %d 学生的密码: ",j);
scanf("%d",&b);
q->val=b;
q->num=j;
if(j!=n){
q->next=(listnode*)malloc(sizeof(listnode));
q=q->next;
}
q->next=p;
}//循环结束后，q->next就是链表头
printf("last: num-%d val-%d\n",q->num,q->val);
printf("请输入初值: ");
scanf("%d",&m);
if(m<=0){
printf("错误！\n");
return(1);
}
m=m-1;//提前使q停下，p=q->next，p就是目标。
printf("结果是:\n");
printf("出列顺序是： ");
//使用q为起始点
do{
i=0;//避免m减一后为零的问题
while(i!=m){
q=q->next;
i++;
}
p=q->next;
q->next=p->next;
printf(" %d",p->num);
m=p->val;//你少了这一步。
m=m-1;//提前使q停下，p=q->next，p就是目标。
free(p);
}while(q->next!=q);
printf(" %d\n",q->num);
free(q);
//free(head); //此时head也许已经被free掉
getchar();
getchar();
return(0);
}

Answer 4

解决初始m为1的情况。

#include<stdio.h>
#include<malloc.h>

typedef struct node{
int num;
int val;
struct node* next;
}listnode;
//两个结构体可以合并以减少程序复杂度
typedef listnode* linklist;

int main(){
int n,i,b,m,j;
linklist q=(listnode*)malloc(sizeof(listnode));
q->next=q;//即使只有一个元素，他也是个循环链表
listnode *p;
printf("请输入总人数:");
scanf("%d",&n);
p=q;
for(j=1;j<=n;j++){
printf("请输入第 %d 学生的密码: ",j);
scanf("%d",&b);
q->val=b;
q->num=j;
if(j!=n){
q->next=(listnode*)malloc(sizeof(listnode));
q=q->next;
}
q->next=p;
}//循环结束后，q->next就是链表头
printf("last: num-%d val-%d\n",q->num,q->val);
printf("请输入初值: ");
scanf("%d",&m);
if(m<=0){
printf("错误！\n");
return(1);
}
m=m-1;//提前使q停下，p=q->next，p就是目标。
printf("结果是:\n");
printf("出列顺序是： ");
//使用q为起始点
do{
i=0;//避免m减一后为零的问题
while(i!=m){
q=q->next;
i++;
}
p=q->next;
q->next=p->next;
printf(" %d",p->num);
m=p->val;//你少了这一步。
m=m-1;//提前使q停下，p=q->next，p就是目标。
free(p);
}while(q->next!=q);
printf(" %d\n",q->num);
free(q);
//free(head); //此时head也许已经被free掉
getchar();
getchar();
return(0);
}

谢谢楼主采纳，希望可以帮助到您，不懂得追问。

追问

能不能再解释得详细些啊？谢谢

追答

那句话不懂，你让我解释，大哥，没有什么高级的函数，都能看懂，

Answer 5

不好搞