1、約瑟夫問題原題：
n個小孩子手拉手圍成一個圈，編號為k(1 <= k <= n )的人從1開始報數(shù)，報到m的那個人出列，它的下一位又從1開始報數(shù)，報到m的又出列……依此類推，直到所有人都出列，由此產(chǎn)生一個出隊(duì)編號的序列。
2、問題分析：
根據(jù)題目的描述，很容易可以想到用單向循環(huán)鏈表來模擬。先構(gòu)成一個有n個節(jié)點(diǎn)的單向循環(huán)鏈表，然后節(jié)點(diǎn)K由1開始計(jì)數(shù)，計(jì)到m時，對應(yīng)的節(jié)點(diǎn)從鏈表中刪除，然后再從被刪除的下一個節(jié)點(diǎn)由1開始計(jì)數(shù)，直到所有節(jié)點(diǎn)都被刪除掉。
如上圖，n等于5，假設(shè)從1號開始報數(shù)，報到2就出列，即k等于1，m等于2。那么最后出列的結(jié)果應(yīng)該是：2，4，1，5，3。
1、構(gòu)建思路：
依此類推，就可以構(gòu)建出單向環(huán)形鏈表。遍歷的時候，當(dāng)節(jié)點(diǎn)的next等于first時，表示遍歷完畢。
2、代碼實(shí)現(xiàn)：
根據(jù)上面的分析，可以寫出如下代碼：
package com.zhu.study.linkedList;
/**
* 約瑟夫問題，即單向循環(huán)鏈表問題
* @author: zhu
* @date: 2020/8/30 17:57
*/
public class Josepfu {
public static void main(String[] args){
CircleSingleLinkedlist linkedlist = new CircleSingleLinkedlist();
linkedlist.add(5);
linkedlist.showNodes();
}
}
/**
* 單向循環(huán)鏈表
*/
class CircleSingleLinkedlist{
private Node first = null;
/**
* 添加節(jié)點(diǎn)
* @param num 需要添加的節(jié)點(diǎn)個數(shù)
*/
public void add(int num){
if (num < 1){
throw new RuntimeException("非法參數(shù)");
}
Node cur = null; // 當(dāng)前node
for (int i = 1; i <= num; i++) {
Node node = new Node(i);
if (i == 1) {
first = node;
first.setNext(first); // next指向自己，構(gòu)成環(huán)
cur = first;
} else {
cur.setNext(node);
node.setNext(first);
cur = node;
}
}
}
/**
* 遍歷
*/
public void showNodes(){
if (first == null){ // 鏈表為空
return;
}
Node cur = first;
while (true){
System.out.printf("小孩編號%d \n", cur.getNo());
if (cur.getNext() == first){ // 遍歷完畢
break;
} else {
cur = cur.getNext();
}
}
}
}
/**
* 節(jié)點(diǎn)內(nèi)部類
*/
class Node{
private int no; // 編號
private Node next; // 下一個節(jié)點(diǎn)
public Node(int no){
this.no = no;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
1、思路：
先要找到開始報數(shù)的節(jié)點(diǎn)，用cur記錄下來，比如從第k個開始數(shù)，那么cur應(yīng)該指向k號節(jié)點(diǎn)；然后再找到cur的前一個節(jié)點(diǎn)，用pre記錄下來；找到這兩個節(jié)點(diǎn)后，由cur開始數(shù)(m-1)次，即cur和pre同時移動(m-1)次，此時cur就指向了要被刪除的節(jié)點(diǎn)；打印要被刪除的節(jié)點(diǎn)，然后將cur移動到被刪除節(jié)點(diǎn)的下一個節(jié)點(diǎn)，即cur = cur.next，pre的next指向新的cur，即pre.next = cur。
2、代碼實(shí)現(xiàn)：
/**
* 出圈，圈中共有n個人，從第k個開始，數(shù)m個開始出圈
* @param k
* @param m
* @param n
*/
public void get(int k, int m, int n){
if (k > n || k < 1 || first == null || m > n){
throw new IllegalArgumentException("非法參數(shù)");
}
// 先找到k節(jié)點(diǎn)，即開始報數(shù)的節(jié)點(diǎn)，用cur記錄下來
Node cur = first;
for (int i = 1; i < k; i++) {
cur = cur.getNext();
}
// 找到k的前一個節(jié)點(diǎn)，用pre記錄下來
Node pre = cur;
while (true){
if (pre.getNext() == cur){
break;
} else{
pre = pre.getNext();
}
}
// 出圈
while (true) {
if (pre == cur) { // 只有一個節(jié)點(diǎn)了
System.out.printf("小孩編號%d\n", cur.getNo());
break;
}
// cur和pre同時移動 m-1次
for (int i = 1; i < m; i++) {
cur = cur.getNext(); // 這個就是要出圈的節(jié)點(diǎn)
pre = pre.getNext(); // 這個是要出圈節(jié)點(diǎn)的前一個節(jié)點(diǎn)
}
System.out.printf("小孩編號%d\n", cur.getNo());
cur = cur.getNext();
pre.setNext(cur);
}
}
調(diào)用該方法，k、m、n分別輸入1、2、5，最后發(fā)現(xiàn)結(jié)果和上面分析的一樣，打印的是2,4,1,5,3。
