看小朋友做游戲頓時解決了約瑟夫問題

前言

★ 這里是小冷的博客
? 優質技術好文見專欄
個人公眾號，分享一些技術上的文章，以及遇到的坑
當前系列：資料結構系列
源代碼 git 倉庫 ‘
資料結構代碼地址 代碼Git 倉庫地址

環形鏈表

認識單向環形鏈表

這里我們以單向環形鏈表為例子

就是我們最后一個節點的next域指向頭結點，形成倍訓

參考場景以及問題

Josephu(約瑟夫、約瑟夫環) 問題

Josephu 問題為：設編號為 1，2，… n 的 n 個人圍坐一圈，約定編號為 k（1<=k<=n）的人從 1 開始報數，數 到 m 的那個人出列，它的下一位又從 1 開始報數，數到 m 的那個人又出列，依次類推，直到所有人出列為止，由

此產生一個出隊編號的序列，

思路提示：

提示：用一個不帶頭結點的回圈鏈表來處理 Josephu 問題：先構成一個有 n 個結點的單回圈鏈表，然后由 k 結 點起從 1 開始計數，計到 m 時，對應結點從鏈表中洗掉，然后再從被洗掉結點的下一個結點又從 1 開始計數，直 到最后一個結點從鏈表中洗掉演算法結束，

Josephu 問題解題思路

認識約瑟夫問題，以及我們想要實作的場景，

1. 撰寫實作 單向環形鏈表
2. 約瑟夫問題的要求 根據區間報數 報數的小孩出列
3. coding 出我們需要的需求

實作單向回圈鏈表

思路

大體上和我們的單向鏈表有雷同的地方，區別在于：

1. 我們需要在創建鏈表的時候將尾結點的最后一個指向頭結點，這也就意味著我們需要有至少兩個指標來記錄頭尾節點，
2. 遍歷的方式也要有些許的變化，結束回圈的條件從head.next = null改變成CurBoy.next(指向尾部節點的指標) = first;最后為頭節點的時候遍歷為第二個

我們簡單的先創建一個實作鏈表需要的節點物件

約瑟夫問題環形鏈表的節點

//環形鏈表 約瑟夫問題 節點
class Boy {
    private int No;
    private Boy Next;

    public Boy(int no) {
        this.No = no;
    }

    public int getNo() {
        return No;
    }

    public void setNo(int no) {
        No = no;
    }

    public Boy getNext() {
        return Next;
    }

    public void setNext(Boy next) {
        Next = next;
    }

}

創建環形鏈表物件實作生成鏈表和遍歷鏈表，以及解決約瑟夫問題的方（具體的實作思路見代碼注釋）

// 環形單向鏈表
class CircleSingleLinkeList {
    Boy first = null;

    /**
     * @author 冷環淵 Doomwatcher
     * @context: 一個環形鏈表  引數是這個鏈表有多少節點
     * @date: 2021/12/21 15:47
     * @param nums
     * @return: void
     */
    public void CreateListNode(int nums) {

        if (nums < 1) {
            System.out.println("無法開始游戲，因為鏈表小于最小的游戲節點數量");
            return;
        }
        // 創建一個 輔助之間用于遍歷和指向節點
        Boy curBoy = null;
        for (int i = 1; i <= nums; i++) {
            Boy boy = new Boy(i);
            //如果只有一個節點的話 也可以生成環形鏈表
            if (i == 1) {
                first = boy;
                first.setNext(first);
                curBoy = first;//將輔助指標指向鏈表的第一個節點 形成倍訓
            } else {
                //    如果不是一個的話就生成多個節點
                curBoy.setNext(boy);
                boy.setNext(first);
                curBoy = boy;
            }
        }
    }

    public void showListBoy() {
        if (first == null) {
            System.out.println("鏈表為空，不能遍歷");
            return;
        }
        //   frist 節點不能移動 我們創建一個指標
        Boy curboy = first;
        while (true) {
            System.out.printf("小孩的編號是： %d \n", curboy.getNo());
            // 說明已經遍歷完畢
            if (curboy.getNext() == first) {
                break;
            }
            //后移 curboy
            curboy = curboy.getNext();
        }

    }

    /**
     * @author 冷環淵 Doomwatcher
     * @context: 這里我們以小孩做游戲來解決約瑟夫問題，
     * @date: 2021/12/22 21:16
     * @param nums 一共有多少個小孩
     * @param start 從那個小孩開始報數
     * @param index 每隔幾個小孩報數一次
     * @return: void
     */
    public void JosephuFunc(int nums, int start, int index) {
        if (first == null || start < 1 || start > nums) {
            System.out.println("引數不對，請重新輸入引數");
            return;
        }
        Boy helper = first;
        //將 helper遍歷到最后一個節點
        while (true) {
            if (helper.getNext() == first) {
                break;
            }
            helper = helper.getNext();
        }
        // 小孩子 報數之前，要遍歷指標到從start開始的小孩的節點
        for (int i = 0; i < start - 1; i++) {
            first = first.getNext();
            helper = helper.getNext();
        }
        //當小孩報數的時候 讓 first和helper 同時移動m-1次 然后出圈
        //這里回圈操作 知道圈中的一個節點
        while (true) {
            //說明串列只有一個節點
            if (helper == first) {
                break;
            }
            //回圈之后將 指標后移
            for (int i = 0; i < index - 1; i++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            //    這個時候 first選中的節點就是要出圈的小孩
            System.out.printf("小孩 %d 出圈\n", first.getNo());
            //出圈操作
            first = first.getNext();
            helper.setNext(first);
        }
        System.out.printf("最后剩下的小孩 %d \n", first.getNo());
    }
}

實作結果