分析约瑟夫问题(循环单链表）

分析约瑟夫问题(循环单链表）

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; }}

此代码仅为个人见解，还需更改

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。