1.Josephu question：

設編號為1，2，3…n的n個人圍坐一圈，約定編號為k(1<=k<=n)的人從1開始報數(shù)，數(shù)到m的那個人出列，它的下一位又從1開始報數(shù)，數(shù)到m的那個人又出列，依次類推，直到所有人出列為止，由此產(chǎn)生一個出隊編號的序列

---

2.思路

1.構成一個有n個節(jié)點的單循環(huán)鏈表
2.從第k個節(jié)點開始報數(shù)(k是第一個)，當報的數(shù)等于m時停止，將該節(jié)點刪除
3.從上一個刪除節(jié)點的下一個節(jié)點繼續(xù)報數(shù)，直到所有節(jié)點刪除

3.代碼實現(xiàn)方式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; //指向循環(huán)鏈表的第一個節(jié)點，始終保持不變/***構建一個循環(huán)鏈表*@param nums 循環(huán)鏈表長度*/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;}}}/***核心函數(shù)* @param k 從第幾個位置開始* @param m 數(shù)幾個數(shù)* @param n 環(huán)形隊列的長度*/public void Joseph(int k, int m, int n) {if (n < 1 || k < 1 || m < 1) {System.out.println("n或k或m不符合規(guī)則!");return;}add(n); //創(chuàng)建一個長度為n的循環(huá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);}} } //節(jié)點類 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.代碼實現(xiàn)方式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;}}

此代碼僅為個人見解，還需更改

總結

以上是生活随笔為你收集整理的分析约瑟夫问题(循环单链表）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。