1.Josephu question： 设编号为1，2，3…n的n个人围坐一圈，约定编号为k(1=k=n)的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有
1.Josephu question：
设编号为1，2，3…n的n个人围坐一圈，约定编号为k(1<=k<=n)的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列
2.思路
1.构成一个有n个节点的单循环链表
2.从第k个节点开始报数(k是第一个)，当报的数等于m时停止，将该节点删除
3.从上一个删除节点的下一个节点继续报数，直到所有节点删除
3.代码实现方式1
package com.company;/**
* @author:抱着鱼睡觉的喵喵
* @date:2021/2/11
* @description:
*/
public class JosephDemo3 {
public static void main(String[] args) {
System.out.println("出列的顺序为:");
new CircleSingleLinkedList().Joseph(2, 10, 5);
}
}
class CircleSingleLinkedList {
private CircleNodes front; //指向循环链表的第一个节点，始终保持不变
/**
*构建一个循环链表
*@param nums 循环链表长度
*/
public void add(int nums) {
if (nums < 1) {
System.out.println("LinkedList is empty!");
return;
}
CircleNodes cur = null;
for (int i = 1; i <= nums; i++) {
CircleNodes circleNodes = new CircleNodes(i);
if (i == 1) {
front = circleNodes;
front.setNext(circleNodes);
cur = circleNodes;
} else {
cur.setNext(circleNodes);
circleNodes.setNext(front);
cur = circleNodes;
}
}
}
/**
*核心函数
* @param k 从第几个位置开始
* @param m 数几个数
* @param n 环形队列的长度
*/
public void Joseph(int k, int m, int n) {
if (n < 1 || k < 1 || m < 1) {
System.out.println("n或k或m不符合规则!");
return;
}
add(n); //创建一个长度为n的循环链表
CircleNodes cur = front;
CircleNodes temp = front;
while (cur.getNext() != front) { //将
cur = cur.getNext();
}
for (int s = 1; s < k; s++) {
cur = cur.getNext();
temp = temp.getNext();
}
int nums = n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < ((m - 1) % nums); j++) {
cur = cur.getNext();
temp = temp.getNext();
}
nums--;
System.out.printf("%d->",temp.getSno());
temp = temp.getNext();
cur.setNext(temp);
}
}
}
//节点类
class CircleNodes {
private int sno;
private CircleNodes next;
public CircleNodes getNext() {
return next;
}
public void setNext(CircleNodes next) {
this.next = next;
}
public CircleNodes(int sno) {
this.sno = sno;
}
public int getSno() {
return sno;
}
public void setSno(int sno) {
this.sno = sno;
}
}
4.代码实现方式2
package com.company;/**
* @author:抱着鱼睡觉的喵喵
* @date:2021/2/11
* @description:
*/
public class JosephDemo2 {
public static void main(String[] args) {
CircleNode2 circleNode = new CircleNode2(1);
CircleNode2 circleNode2 = new CircleNode2(2);
CircleNode2 circleNode3 = new CircleNode2(3);
CircleNode2 circleNode4 = new CircleNode2(4);
CircleLinkedList2 circleLinkedList2 = new CircleLinkedList2();
circleLinkedList2.add(circleNode);
circleLinkedList2.add(circleNode2);
circleLinkedList2.add(circleNode3);
circleLinkedList2.add(circleNode4);
Joseph(1, 1, circleLinkedList2);
}
public static void Joseph(int k, int m, CircleLinkedList2 circleLinkedList2) {
int length = circleLinkedList2.getLength();
if (k <= 0 || m <= 0 || length <= 0) {
System.out.println("k或m或链表长度不符合条件：（k>0 && m>0 && length>0)!");
return;
}
CircleNode2 head = circleLinkedList2.front;
int nums = 0;
CircleNode2 cur = circleLinkedList2.front;
while (nums != k - 1) {
nums++;
cur = cur.next;
}
CircleNode2 pNode = circleLinkedList2.front;
for (int j = 0; j < k - 2; j++) {
pNode = pNode.next;
}
for (int i = 0; i < length; i++) {
nums = 0;
while (nums != m - 1) {
nums++;
pNode = pNode.next;
cur = cur.next;
}
System.out.printf("%d->", cur.sno);
pNode.next = cur.next;
cur = cur.next;
}
}
}
class CircleNode2 {
public int sno;
public CircleNode2 next;
public CircleNode2(int sno) {
this.sno = sno;
}
}
class CircleLinkedList2 {
CircleNode2 front;
CircleNode2 cur;
public void add(CircleNode2 node) {
if (front == null) {
front = node;
node.next = node;
cur = node;
} else {
cur.next = node;
node.next = front;
cur = node;
}
}
public void list() {
if (front == null) {
System.out.println("LinkedList is empty!");
return;
}
System.out.println(front);
CircleNode2 temp = front.next;
while (temp != front) {
System.out.println(temp);
temp = temp.next;
}
}
public int getLength() {
int nums = 0;
if (front == null) {
return nums;
}
nums++;
CircleNode2 temp = front;
while (temp.next != front) {
nums++;
temp = temp.next;
}
return nums;
}
}
此代码仅为个人见解，还需更改