使用单向环形链表实现约瑟夫(Josephu)问题
1.约瑟夫（Josephu）问题描述
Josephu 问题为：设编号为 1，2，… n 的 n 个人围坐一圈，约定编号为 k（1<=k<=n）的人从 1 开始报数，数到 m 的那个人出列，它的下一位又从 1 开始报数，数到 m 的那个人又出列，依次类推，直到所有人出列为止，由此 产生一个出队编号的序列。
2.小提示
用一个不带头结点的循环链表来处理 Josephu 问题：先构成一个有 n 个结点的单循环链表，然后由 k 结点起从 1 开 始计数，计到 m 时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从 1 开始计数，直到最后一个结点从链表中删除算法结束。
3.约瑟夫(Josephu)问题—创建单向环形单链表的思路和图解
思路：
(1)先创建一个结点，让first指针指向该节点，并使first.next=first使得第一个结点自己 形成一个环，并将辅助指针指向该节点。核心代码是：
if(i==1)
{
first=boy;
//如果只有一个结点，就先自己构成一个环
first.next=first;
//让辅助指针curBoy指向第一个小孩
curBoy=first;
}
(2)后面没创建一个结点，就将该节点加入到该环形链表中，核心代码是
curBoy.next=boy;
boy.next=first;
curBoy=boy;
图解：
4.约瑟夫(Josephu)问题—遍历环形单链表思路
(1)创建一个辅助指针curBoy,指向first结点
(2)然后通过while循环遍历单向环形单链表，直到curBoy.next==first结束
5.约瑟夫（Josephu）问题核心—小孩子出圈顺序思路分析
(1)举例：根据用户的输入，生成一个小孩的顺序
n=5:表示单链表中有五个结点，即初始时圈中有五个小孩
k=1:表示从第一个孩子开始报数
m=2:每次数两个人，出圈一个孩子
(2)思路分析
—创建一个helper指针，起始时指向唤醒链表的最后一个结点。
—小孩报数前，先让first指针和helper指针同时移动k-1次（因为题目不一定是从第一个孩子开始报数）
—之后小孩报数时，将first指针和helper指针同时移动m-1次
----这时可以将first指向的小孩结点同时出圈:first=first.next helper.next=first；
(3)案例出圈顺序为：2–>4–>1–>5–>3
6.约瑟夫(Josephu)问题代码实现
package cn.zzw.algorithm.LinkedList;
//使用单向环形链表实现约瑟夫问题
public class Josepfu {
public static void main(String[] args) {
//测试环形链表和遍历
CircleSingleLinkedList circleSingleLinkedList=new CircleSingleLinkedList();
circleSingleLinkedList.addBoy(5);
circleSingleLinkedList.show();
//测试小孩结点出圈顺序是否正确
circleSingleLinkedList.countBoy(1,2,5);
}
}
//创建一个Boy类，表示一个环形链表中的一个结点
//当然可以把属性no和next设为私有，之后使用get和set方法进行访问
class Boy
{
public int no;
public Boy next;//表示结点的下一个结点，默认值为null
public Boy(int no) {
this.no = no;
}
@Override
public String toString() {
return "Boy{" +
"no=" + no +
'}';
}
}
//创建一个环形的单链表
class CircleSingleLinkedList
{
//创建一个first结点，当前默认为null，没有后继结点
private Boy first=null;
//添加小孩结点，构建一个环形的链表
public void addBoy(int nums)
{
//为了防止nums不合法，对其进行数据校验
if(nums<1)
{
System.out.println("nums数据值不合法");
return;
}
//使用辅助指针，帮助构建环形链表
Boy curBoy=null;
for(int i=1;i<=nums;i++)
{
//根据编号，创建小孩结点
Boy boy=new Boy(i);
//如果小孩是第一个结点
if(i==1)
{
first=boy;
//如果只有一个结点，就先自己构成一个环
first.next=first;
//让辅助指针curBoy指向第一个小孩
curBoy=first;
}
else
{
curBoy.next=boy;
boy.next=first;
curBoy=boy;
}
}
}
//遍历当前链表
public void show()
{
//判断当前链表是否为空
if (first==null)
{
System.out.println("当前链表为空,没有任何结点");
return;
}
//first指针不能动,应该使用一个辅助指针完成链表的遍历
Boy curBoy=first;
while (true)
{
System.out.printf("当前小孩的编号为：%d\n",curBoy.no);
if(curBoy.next==first)
{
break;
}
//后移辅助指针
curBoy=curBoy.next;
}
}
/**
*
* @param startNo
* startNo表示从第几个小孩开始报数
* @param countNum
* countNo表示一次数几下
* @param nums
* nums表示一个圈中初始有几个孩子(结点)
*/
//根据用户输入,指定小孩出圈的顺序，也是整个约瑟夫问题的核心
public void countBoy(int startNo,int countNum,int nums)
{
//首先进行数据校验
if(first==null||startNo<1||startNo>nums)
{
System.out.println("数据输入有误,请重新输入");
return;
}
//创建辅助指针，帮助完成小孩出圈
Boy helper=first;
//开始时将辅助指针指向环形链表的最后一个结点
while (true)
{
if(helper.next==first)
{
break;
}
helper=helper.next;
}
//因为有时题目开始报数的并不是1,所以应该先让first和helper同时移动startNo-1次
for (int j=0;j<startNo-1;j++)
{
first=first.next;
helper=helper.next;
}
//当小孩报数时，让first和helper指针同时移动countNum-1次，然后出圈
//这里是一个循环操作，直到圈里面的人数只有一个
while(true)
{
if (helper==first)
{
//此时表示链表中只有一个结点
break;
}
//让first指针和helper指针同时移动countNum-1次
for(int j=0;j<countNum-1;j++)
{
first=first.next;
helper=helper.next;
}
//这时first指向的就是将要出圈的孩子
System.out.printf("小孩%d出圈\n",first.no);
//这时将first指向的小孩结点出圈
first=first.next;
helper.next=first;
}
System.out.printf("最后留在圈中的小孩编号%d\n",first.no);
}
}
7.代码测试结果
"C:\Program Files\Java\jdk1.8.0_181\bin\java.exe" "-javaagent:D:\IntelliJ IDEA\IntelliJ IDEA 2019.3.3\lib\idea_rt.jar=12960:D:\IntelliJ IDEA\IntelliJ IDEA 2019.3.3\bin" -Dfile.encoding=UTF-8 -classpath "C:\Program Files\Java\jdk1.8.0_181\jre\lib\charsets.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\deploy.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\access-bridge-64.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\cldrdata.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\dnsns.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\jaccess.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\jfxrt.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\localedata.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\nashorn.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\sunec.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\sunjce_provider.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\sunmscapi.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\sunpkcs11.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\ext\zipfs.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\javaws.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\jce.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\jfr.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\jfxswt.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\jsse.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\management-agent.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\plugin.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\resources.jar;C:\Program Files\Java\jdk1.8.0_181\jre\lib\rt.jar;C:\Users\1\IdeaProjects\algorithm\out\production\algorithm" cn.zzw.algorithm.LinkedList.Josepfu
当前小孩的编号为：1
当前小孩的编号为：2
当前小孩的编号为：3
当前小孩的编号为：4
当前小孩的编号为：5
小孩2出圈
小孩4出圈
小孩1出圈
小孩5出圈
最后留在圈中的小孩编号3
Process finished with exit code 0