總目錄：地址如下看總綱
1、什么是約瑟夫問題
約瑟夫問題其實也是一個游戲(丟手絹)，也稱為約瑟夫環(huán)。
規(guī)則很簡單：就是有一群小鬼圍起來(例5個)成一個圈，先從第一個小鬼報數(shù) n，以第一個小鬼的第n 個小鬼，
既出列，出列的 第 n 個小鬼的后面一個 繼續(xù)報數(shù) n ，依次類推直到所有小鬼都離開這個圈中
image.png
解決方案：可以使用單向環(huán)形鏈表
2、單向環(huán)形鏈表的構建和遍歷分析
image.png
1、構建一個單向的環(huán)形鏈表思路
(1). 先創(chuàng)建第一個節(jié)點, 讓 first 指向該節(jié)點，并形成環(huán)形
(2). 后面當我們每創(chuàng)建一個新的節(jié)點，就把該節(jié)點，加入到已有的環(huán)形鏈表中即可
2、遍歷環(huán)形鏈表
(1). 先讓一個輔助指針(變量) curKid，指向first節(jié)點
(2). 然后通過一個while循環(huán)遍歷 該環(huán)形鏈表即可 curKid.next == first 結束
3、單向環(huán)形鏈表抓鬼
image.png
根據(jù)用戶的輸入，生成一個小鬼出圈的順序（方法：countKid）
n = 5 , 即有5只鬼
k = 1, 從第一個小鬼開始報數(shù)
m = 2, 數(shù)2下(包括它自己也得數(shù))
- 需求創(chuàng)建一個輔助指針(變量) helper (討債鬼), 事先應該指向環(huán)形鏈表的最后這個節(jié)點.
2.小鬼報數(shù)前，先讓 first 和 helper 移動 k - 1次- 當小鬼報數(shù)時，讓first 和 helper 指針同時 的移動 m - 1 次
- 這時就可以將first 指向的小鬼節(jié)點 出圈
first = first .next
helper.next = first
原來first 指向的節(jié)點就沒有任何引用，就會被回收
helper (討債鬼)：作用就是一直跟在first后面，得到first不行了就把鎖鏈套在下一個first脖子，直達所有都套死
出圈的順序
2->4->1->5->3
3、代碼實現(xiàn)
package com.kk.datastructure.linkedlist.josepfu;
/**
* title: 約瑟夫問題--單向環(huán)形鏈表
* @author 阿K
* 2020年11月28日 下午7:56:21
*/
public class Josepfu {
public static void main(String[] args) {
// 測試一把構建環(huán)形鏈表，和遍歷
CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
circleSingleLinkedList.addKid(5);// 加入5個小鬼節(jié)點
circleSingleLinkedList.showKid();
// 測試一把小鬼出圈
circleSingleLinkedList.countKid(1, 2, 5); // 2->4->1->5->3
}
}
//創(chuàng)建一個環(huán)形的單向鏈表
class CircleSingleLinkedList {
// 創(chuàng)建一個first節(jié)點,當前沒有編號
private Kid first = null;
// 添加小鬼節(jié)點，構成一個環(huán)形鏈表(并非一個個添加，而是初始化個數(shù))
public void addKid(int nums) {
if (nums < 1) {
System.out.println("數(shù)量錯誤，無法構建環(huán)形");
return;
}
// 輔助指針，幫助構建環(huán)形鏈表
Kid curKid = null;
// 使用for來創(chuàng)建我們的環(huán)形鏈表
for (int i = 1; i <= nums; i++) {
// 根據(jù)編號，創(chuàng)建小鬼節(jié)點
Kid kid = new Kid(i);
// 如果是第一個小鬼
if (i == 1) {
first = kid;
first.setNext(first);// 構成環(huán)
curKid = first; // 讓curKid指向第一個小鬼
} else {
curKid.setNext(kid);// 此時的輔助是指向 first,它后面則指向 新節(jié)點(編號 2...)
kid.setNext(first); // 構成環(huán)
curKid = kid; // 此時curKid 指向第二個小鬼....
}
}
}
// 遍歷當前環(huán)形鏈表
public void showKid() {
// 判空
if (first == null) {
System.out.println("沒有任何小鬼~~");
return;
}
// 因為first不能動，因此我們?nèi)匀皇褂靡粋€輔助指針完成遍歷
Kid curKid = first;
while (true) {
System.out.printf("小鬼的編號 %d \n", curKid.getNo());
if (curKid.getNext() == first) {
// 已經(jīng)遍歷結束
break;
}
// 后移
curKid = curKid.getNext();
}
}
/**
* 開始抓鬼
*
* @param startNo 表示從第幾個小鬼開始數(shù)數(shù)
* @param countNum 表示每次數(shù)了幾只小鬼(報數(shù)幾)
* @param nums 表示最初圈內(nèi)的總鬼數(shù)
*/
public void countKid(int startNo, int countNum, int nums) {
// 數(shù)據(jù)校驗
if (first == null || startNo < 1 || startNo > nums) {
System.out.println("參數(shù)輸入有誤， 請重新輸入");
return;
}
// 創(chuàng)建輔助指針，討債鬼，作用催命
Kid helper = first;// 初始化自己套自己，因為圈內(nèi)目前就一個
// 需求創(chuàng)建一個輔助指針(變量) helper , 事先應該指向環(huán)形鏈表的最后這個節(jié)點
while (true) {
if (helper.getNext() == first) {
// 已經(jīng)到最后一個
break;
}
// 后移
helper = helper.getNext();
}
// 考慮到 可能不是 k=1的情況：
// 小鬼報數(shù)前，先讓 first 和 helper 移動 k - 1(startNo - 1)次
for (int j = 0; j < startNo - 1; j++) {
first = first.getNext();
helper = helper.getNext();
}
// 當小鬼報數(shù)時，讓first 和 helper 指針同時 的移動 m - 1 次(countNum -1), 然后出圈
// 這里是一個循環(huán)操作，直到圈中只有一個節(jié)點
while (true) {
if (helper == first) {
// 說明圈中只有一個節(jié)點
break;
}
// 讓 first 和 helper 指針同時 的移動 countNum - 1
for (int j = 0; j < countNum - 1; j++) {
first = first.getNext();
helper = helper.getNext();
}
// 這時first指向的節(jié)點，就是要出圈的小鬼節(jié)點
System.out.printf("小鬼%d出圈\n", first.getNo());
// 這時將first指向的小鬼節(jié)點出圈
first = first.getNext();
helper.setNext(first); // 討債鬼的繩索套在了新frist脖子上
}
System.out.printf("最后留在圈中的小鬼編號%d \n", first.getNo());
}
}
//創(chuàng)建一個Kid類，表示一個節(jié)點
class Kid{
private int no;// 編號
private Kid next;// 指向下一個節(jié)點
public Kid(int no) {
this.no = no;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public Kid getNext() {
return next;
}
public void setNext(Kid next) {
this.next = next;
}
}
