Josephu问题与单向环形链表
1. 什么是约瑟夫问题(Josephu)
-
Josephu问题的设定为:假设编号为1,2,...,n的n个人围坐成一圈,从编号为k(1≤k≤n)的人开始报数,当报至m时报m的这个人出列,其下一个人再次重新开始报数报m的人再次出列,重复此过程,直至所有人都出列,即产生了一个出列编号的顺序排列。
-
可以用一个不带头节点的环形链表来处理Josephu问题。
![Josephu问题示意图](/i/l/?n=23&i=blog/3116926/202303/3116926-20230325174254394-1268101302.png)
假设n=5;k=1,即从第一个开始数;m=2,即数2个就出列
则出列的编号顺序为:2->4->1->5->3
2. 单向环形链表的构建与遍历
![创建单向环形链表](/i/l/?n=23&i=blog/3116926/202303/3116926-20230325174634414-1581479744.png)
-
构建单向环形链表的思路:
- 先创建两个辅助指针first和cur,初始为null;
- 创建第一个节点,让first和cur指向该节点,并构成环形(如虚线所示);
- 之后每创建一个新的节点newNode,就令cur.next=newNode,并再次构成环形(如虚线),之后让cur后移指向当前节点。
-
遍历单向环形链表的思路:
- 定义一个辅助指针temp指向first,然后将temp不断后移遍历链表,直至temp.next==first遍历结束。
package com.datastructure;
/**
* @author SnkrGao
* @create 2023-03-25 14:16
*/
public class JosephuQuestion {
public static void main(String args[]) {
CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
circleSingleLinkedList.addKids(5);
circleSingleLinkedList.showKids();
}
}
class kidNode {
private int No;
private kidNode next;
public kidNode(int no) {
this.No = no;
}
// 整体封装为类,两个属性都是private,需要生成set方法和get方法以便后续操作
public int getNo() {
return No;
}
public void setNo(int no) {
No = no;
}
public kidNode getNext() {
return next;
}
public void setNext(kidNode next) {
this.next = next;
}
}
class CircleSingleLinkedList {
private kidNode first = null;
private kidNode cur = null;
/**
* 添加节点构建环形链表
* @param num 传入参数为添加的kidNode个数
*/
public void addKids(int num) {
if (num < 2) {
System.out.println("输入num有误,请重新输入!");
return;
}
for (int i = 1; i <= num; i++) {
kidNode newKid = new kidNode(i);
if (i==1) { // 需要单独判断第一个节点
first = newKid;
first.setNext(first); // 构成环形
cur = first;
}else {
cur.setNext(newKid);
newKid.setNext(first);
cur = newKid;
}
}
}
// 遍历当前环形链表
public void showKids() {
if (first == null) {
System.out.println("链表为空!");
return;
}
// first不能动
kidNode temp = first;
// 此处需注意环形链表只有一个节点,以及是否忽略最后一个节点未打印的情况
while (true) {
System.out.println("kid编号:"+temp.getNo());
if (temp.getNext() == first) break;
temp = temp.getNext();
}
}
}
3. 解决Josephu问题
![单向环形链表解决Josephu问题示意图](/i/l/?n=23&i=blog/3116926/202303/3116926-20230325174710110-1085524875.png)
- 思路:
- 先创建一个辅助指针last,初始时应指向环形链表的最后一个节点;
- 在报数之前,首先让first和last同时移动k-1次,目的是让first指向开始报数的那个人;
- 开始报数时,让first和last再次同时移动m-1次,目的是计数让报m的那个人出列;
- 将first指向的节点删除:
- 先让first后移,以便再次报数时从删除节点的下一个节点重新开始报数:first=first.next;
- last.next=first。
- 方法代码:
/**
* 单向环形链表解决Josephu问题
* @param startNo 传入参数startNo表示开始报数的人的编号即k
* @param countNum 传入参数countNum表示需要出列的报数即m
* @param num 传入参数num表示环形链表的长度即n
*/
public void solveJosephu(int startNo, int countNum, int num) {
// 参数合理性校验并判断链表是否为空
if (first == null || startNo < 1 || startNo > num) {
System.out.println("输入参数有误,请重新输入!");
return;
}
// 定义辅助指针last,并令其指向环形链表最后一个节点
kidNode last = first;
while (last.getNext() != first) last = last.getNext();
// 报数前,first与last同时移动k-1次,找到开始报数的人
for (int i = 0; i < startNo - 1; i++) {
first = first.getNext();
last = last.getNext();
}
// 开始报数
while (last != first) {
// first与last同时移动m-1次
for (int i = 0; i < countNum - 1; i++) {
first = first.getNext();
last = last.getNext();
}
// 此时first指向出列的kid
System.out.println("kid-"+first.getNo()+"出列");
first = first.getNext();
last.setNext(first);
}
System.out.println("最后一个应出列的kid为:"+first.getNo());
}
标签:last,int,单向,Josephu,环形,链表,报数,first
From: https://www.cnblogs.com/SnkrGao/p/17255235.html