前言
约瑟夫环问题，是一个经典的循环链表问题，题意是：已知 n 个人（分别用编号 1，2，3，…，n 表示）围坐在一张圆桌周围，从编号为 k 的人开始顺时针报数，数到 m 的那个人出列；他的下一个人又从 1 开始，还是顺时针开始报数，数到 m 的那个人又出列；依次重复下去，直到圆桌上剩余一个人。
如图所示，假设此时圆周周围有 5 个人，要求从编号为 3 的人开始顺时针数数，数到 2 的那个人出列：
出列顺序依次为：
编号为 3 的人开始数 1，然后 4 数 2，所以 4 先出列；
4 出列后，从 5 开始数 1，1 数 2，所以 1 出列；
1 出列后，从 2 开始数 1，3 数 2，所以 3 出列；
3 出列后，从 5 开始数 1，2 数 2，所以 2 出列；
最后只剩下 5 自己，所以 5 胜出。
约瑟夫环问题有多种变形，比如顺时针转改为逆时针等，虽然问题的细节有多种变数，但解决问题的中心思想是一样的，即使用循环链表，而循环链表与普通链表没有较大区别，只是将尾指针指向头指针而已。
一、概念了解
由上面提出的概念可以知道，约瑟夫环问题要求指定一个开始位置，从这个开始位置，顺时针或逆时针的循环读取下一个数据，且数到2的数据要求被移除，而其之后的数据接上来。因此我们需要做到：
1：构建一个链表且这个链表是首尾相连
2：若数据数到2，那么这个数据被移除
3：一个数据被删除后另一个数据要接上去
4：当链表只有一个数据时，结束
特殊情况：如果从编号1开始，且念到1的人出列，那么应该是上面情况
二、实验设计
1.链表初始化
#include <cstdio> #include <iostream> typedef struct Joseph { int number; //编号 struct Joseph* next; //下一个地址 }Ring; Ring* InitRing(int n) //n为所需要构造的数量 { Ring* head,*tail,*p; //头指针 新建指针 临时指针 p= head = (Ring*)malloc(sizeof(Joseph)); //指针初始化 head->number = 1; //编号1的元素 head->next = NULL; //暂时指向空 for (int i = 2; i <= n; i++) { tail = (Ring*)malloc(sizeof(Joseph)); //开辟新空间，存放编号 tail->number = i; //赋予编号 tail->next = NULL; //暂时指向空 p->next = tail; //衔接 p = p->next; //p指向下一个节点，以便下一次p的next能指向新节点 } p->next = head; //首尾相接 return head; //返回头指针 }
2.功能实现
void MoveRing(Ring* head, int start, int num) { Ring* p, * tail; //tail用来指向要删除的数据的前一个位置，保证能数据删除后还能形成完整链条 p= tail = head; while (tail->next != head)//特殊处理，如果要删除的数据就是头指针指向的数据 tail = tail->next;//那么为了保证删除该数据后还能形成一个环而作的处理 while (p->number != start)//找到要删除的序号的位置 { tail = p; //保证tail是要删除数据的前一位 p = p->next; //p为要删除的数据的位置 } while (p->next != p)//最后的情况是tail->next=p->next,p=tail->next,因此最后p->next==p { for(int i = 1;i < num; i++)//达到了要删除的编号 { tail = p; //保证tail是要删除的前一位 p = p->next;//p为要删除的数据 } tail->next = p->next;//tail的下一位指向的是被删除的数据的下一位 cout << "出列的序号是" << p->number << endl;; free(p);//释放被删除数据的空间 p = tail->next; //使得p指向被删除数据的下一位 } cout << "胜利者的序号是" << p->number << endl; free(p);//函数全部结束，直接释放还没释放的空间，防止空间浪费 }
3.完整代码
#include <cstdio> #include <iostream> #include <algo.h> typedef struct Joseph { int number; //编号 struct Joseph* next; //下一个地址 }Ring; Ring* InitRing(int n) //n为所需要构造的数量 { Ring* head,*tail,*p; //头指针 新建指针 临时指针 p= head = (Ring*)malloc(sizeof(Joseph)); //指针初始化 head->number = 1; //编号1的元素 head->next = NULL; //暂时指向空 for (int i = 2; i <= n; i++) { tail = (Ring*)malloc(sizeof(Joseph)); //开辟新空间，存放编号 tail->number = i; //赋予编号 tail->next = NULL; //暂时指向空 p->next = tail; //衔接 p = p->next; //p指向下一个节点，以便下一次p的next能指向新节点 } p->next = head; //首尾相接 return head; //返回头指针 } void MoveRing(Ring* head, int start, int num) { Ring* p, * tail; //tail用来指向要删除的数据的前一个位置，保证能数据删除后还能形成完整链条 p= tail = head; while (tail->next != head)//特殊处理，如果要删除的数据就是头指针指向的数据 tail = tail->next;//那么为了保证删除该数据后还能形成一个环而作的处理 while (p->number != start)//找到要删除的序号的位置 { tail = p; //保证tail是要删除数据的前一位 p = p->next; //p为要删除的数据的位置 } while (p->next != p)//最后的情况是tail->next=p->next,p=tail->next,因此最后p->next==p { for(int i = 1;i < num; i++)//达到了要删除的编号 { tail = p; //保证tail是要删除的前一位 p = p->next;//p为要删除的数据 } tail->next = p->next;//tail的下一位指向的是被删除的数据的下一位 cout << "出列的序号是" << p->number << endl;; free(p);//释放被删除数据的空间 p = tail->next; //使得p指向被删除数据的下一位 } cout << "胜利者的序号是" << p->number << endl; free(p);//函数全部结束，直接释放还没释放的空间，防止空间浪费 } int main() { printf("输入圆桌上的人数n:"); int n; scanf("%d", &n); Ring* head = InitRing(n); printf("从第k人开始报数(k>1且k<%d)：", n); int k; scanf("%d", &k); printf("数到m的人出列："); int m; scanf("%d", &m); MoveRing(head, k, m); return 0; }
4.效果
三、约瑟夫生死者游戏
1.概念
30个旅客同乘一条船，因为严重超载，必须将全船一半的旅客投入海中，其余人才能幸免遇难。大家同意一种办法：30人围成一圈，由第一个人数起，依次报数，数到第9人，便把他投入大海中，然后再从他的下一个人数起，数到第9人，再将他扔进大海中，如此循环地进行，直到剩下15个乘客为止。
要求实现如下功能：
1.建立一个具有30个结点的单循环链表；
2.生者与死者的选择：从位置为1的结点开始数，数到第8个结点，将其下一个结点从单循环链表中删除，然后，再从被删除结点的下一个结点开始数，数到第8个结点，再将其下一个结点删除，如此下去，直到剩下15个结点为止；
3.输出所有生者的位置。
2.解决
可以发现约瑟夫生死者游戏只不过是再约瑟夫环上增加了一些限制条件，例如:
1.最后需要剩余人数为15人
2.数到9的人下船
3.报出幸存者的编号
知道了这些，我们只需要再约瑟夫环的代码上进行一些修改就可以得到约瑟夫生死者游戏的代码
3.C实现
#include <cstdio> #include<cstdlib> #include<iomanip> typedef int Status; typedef int ElemType; typedef char cElemType; #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define MAXSIZE 20 #define make (struct student*)malloc(sizeof(struct student)); using namespace std; typedef struct Joseph { int remain; //剩余人数 int number; //编号 struct Joseph* next; //下一个地址 }Ring; Ring* InitRing(int n) //n为所需要构造的数量 { Ring* head,*tail,*p; //头指针 新建指针 临时指针 p= head = (Ring*)malloc(sizeof(Joseph)); //指针初始化 head->remain = 30; //初始剩余人数30 head->number = 1; //编号1的元素 head->next = NULL; //暂时指向空 for (int i = 2; i <= n; i++) { tail = (Ring*)malloc(sizeof(Joseph)); //开辟新空间，存放编号 tail->number = i; //赋予编号 tail->next = NULL; //暂时指向空 p->next = tail; //衔接 p = p->next; //p指向下一个节点，以便下一次p的next能指向新节点 } p->next = head; //首尾相接 return head; //返回头指针 } void MoveRing(Ring* head, int start, int num) { Ring* p, * tail; //tail用来指向要删除的数据的前一个位置，保证能数据删除后还能形成完整链条 p= tail = head; while (tail->next != head)//特殊处理，如果要删除的数据就是头指针指向的数据 tail = tail->next;//那么为了保证删除该数据后还能形成一个环而作的处理 while (p->number != start)//找到要删除的序号的位置 { tail = p; //保证tail是要删除数据的前一位 p = p->next; //p为要删除的数据的位置 } while (head->remain>15)//最后的情况是tail->next=p->next,p=tail->next,因此最后p->next==p { for(int i = 1;i < num; i++)//达到了要删除的编号 { tail = p; //保证tail是要删除的前一位 p = p->next;//p为要删除的数据 } tail->next = p->next;//tail的下一位指向的是被删除的数据的下一位 cout << "出列的序号是" << p->number << endl; free(p);//释放被删除数据的空间 p = tail->next; //使得p指向被删除数据的下一位 head->remain -= 1; //有人被移除，剩余人数减1 } for (int j = 1; j <= 15; j++) { cout << "幸存者的序号是" << p->number << endl; //输出胜利者的序号 p = p->next; //让p指向下一个地址 } free(head);//函数全部结束，直接释放还没释放的空间，防止空间浪费 } int main() { printf("输入圆桌上的人数n:"); int n; scanf("%d", &n); Ring* head = InitRing(n); printf("从第k人开始报数(k>1且k<%d)：", n); int k; scanf("%d", &k); printf("数到m的人出列："); int m; scanf("%d", &m); MoveRing(head, k, m); return 0; }
4.Java实现
public class JosephusRing{ /** * * @param numOfPeople 总人数 * @param perpleOrder 出去的人叫道的号 * @param startNum 从第几个人开始 */ public static void josephusRing(int numOfPeople,int perpleOrder,int startNum){ Queue<Integer>queue=new Queue<Integer>(); for(int i=0;i<numOfPeople;i++){ //把这几个人入队列 queue.enqueue(i); } for(int i=0;i<startNum;i++){//找到开始的那个人的编号 把他放在队头 queue.enqueue(queue.dequeue()); } while(numOfPeople>0){ for(int i=1;i<perpleOrder;i++){//假设叫道3的出去,那么从1开始 1 2 3 循环两次 然后队头就是要出去的 queue.enqueue(queue.dequeue()); } System.out.println("出去的人的编号是:"+queue.dequeue()); numOfPeople--; } } public static void main(String[] args) { new JosephusRing().josephusRing(5,3,0); } }
