约瑟夫问题
规则: 约定s个人（大于等于1个人）围成一圈，规定顺时针从第m个人开始数n个数，被数到最后一个数的人被淘汰，继续从被淘汰的下一个人开始数，依此进行，直至所有人被淘汰出局。(类似于丢手帕游戏)
解决思路-java单向环形队列
思路：图解如下
image.png
步骤如下:
1、首先构建一个头节点为图中first one位置的环形队列。
2、找到first one节点的助手helper,helper必须为first one的前一个节点。
3、规定从第几个人开始报数，从first one开始顺时针移动m-1个位置，所在位置的节点成为first one，同时helper做相应的移动，总是保持在first one的前一个位置。
4、first one节点开始报n个数，first one节点和helper节点同时顺时针移动n-1个位置。
5、将数到最后一个数的节点删除，first one节点成为被淘汰节点的下一个节点，helper节点指向最新的first one节点。
6、依次循环进行，直到helper节点和first one节点为同一节点，即自己指向自己，淘汰最后一个节点，游戏结束。
代码如下
/**
* 单向环形链表，约瑟夫问题，丢手帕游戏
* 规则：定义s:一共多少个人 定义m:从第几个人开始数数，定义n:每次数几下
* 结果:每次被数到最后一个数的人弹出，直到最后
*/
public class CircleLinkedList {
private Persion firstPersion;//第一个人，头部指针，同时用于将被数到的人弹出
private int m;
private int n;
public CircleLinkedList(int size, int m, int n){
if (size <= 0){
throw new RuntimeException("初始化的环形链表必须大与0");
}
if (m <= 0){
throw new RuntimeException("从第几个人开始必须大与0");
}
if (n <= 0){
throw new RuntimeException("每次数几下必须大与0");
}
this.m = m;
this.n = n;
addPersion(size);
}
private void addPersion(int size){
Persion currentPersion = null;
for (int i = 1; i <= size; i++){
Persion persion = new Persion(i);
if (i == 1){
firstPersion = persion;
currentPersion = firstPersion;
currentPersion.next = firstPersion;
}else {
currentPersion = currentPersion.next;
currentPersion.next = persion;
persion.next = firstPersion;
}
}
}
public void startGame(){
if (isEmpty()){
throw new RuntimeException("当前环形链表为空");
}
Persion persionhelper;//辅助指针，总是在firstPersion之后，用于将指针指向被弹出人的后一个人
Persion currPersion = firstPersion;
while (true){
if (currPersion.next == firstPersion){
persionhelper = currPersion;
break;
}else {
currPersion = currPersion.next;
}
}
for (int i =1; i <=m -1; i++){
firstPersion = firstPersion.next;
persionhelper = persionhelper.next;
}
while (true){
if (firstPersion == persionhelper){
System.out.println("弹出最后一个序号为:" + firstPersion.getNo() + "的同学,下一个序号为:" + firstPersion.getNo());
break;
}
for (int i =0; i < n; i++){
firstPersion = firstPersion.next;
persionhelper = persionhelper.next;
}
System.out.println("弹出一个序号为:" + firstPersion.getNo() + "的同学,下一个序号为:" + firstPersion.next.getNo());
firstPersion = firstPersion.next;
persionhelper.next = firstPersion;
}
}
public void listPersion(){
if (isEmpty()){
throw new RuntimeException("当前环形链表为空");
}
Persion currPersion = firstPersion;
while (true){
if (currPersion.next == firstPersion){
System.out.println("编号为:" + currPersion.getNo() + "下一个编号为:" + currPersion.next.getNo());
break;
}else {
System.out.println("编号为:" + currPersion.getNo() + "下一个编号为:" + currPersion.next.getNo());
currPersion = currPersion.next;
}
}
}
public boolean isEmpty(){
return firstPersion == null;
}
class Persion{
private int no;//编号
private Persion next;
public Persion(int no){
this.no = no;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
}
}
执行代码如下
public static void main(String[] args) {
//设定10个人玩游戏，从第3个人开始报数，每次报2下
CircleLinkedList circleLinkedList = new CircleLinkedList(10, 3, 2);
circleLinkedList.startGame();
}
输出如下:
image.png
欢迎留言，我们一起成长～～
