據(jù)說著名猶太歷史學(xué)家Josephus有過以下的故事：

在羅馬人占領(lǐng)喬塔帕特后，39 個(gè)猶太人與Josephus及他的朋友躲到一個(gè)洞中，39個(gè)猶太人決定寧愿死也不要被敵人抓到，于是決定了一個(gè)自殺方式，41個(gè)人排成一個(gè)圓圈，由第1個(gè)人開始報(bào)數(shù)，每報(bào)數(shù)到第3人該人就必須自殺，然后再由下一個(gè)重新報(bào)數(shù)，直到所有人都自殺身亡為止。

然而Josephus 和他的朋友并不想遵從。

首先從一個(gè)人開始，越過k-2個(gè)人（因?yàn)榈谝粋€(gè)人已經(jīng)被越過），并殺掉第k個(gè)人。接著，再越過k-1個(gè)人，并殺掉第k個(gè)人。這個(gè)過程沿著圓圈一直進(jìn)行，直到最終只剩下一個(gè)人留下，這個(gè)人就可以繼續(xù)活著。

問題是，給定了和，一開始要站在什么地方才能避免被處決。Josephus要他的朋友先假裝遵從，他將朋友與自己安排在第16個(gè)與第31個(gè)位置，于是逃過了這場死亡游戲。

這個(gè)問題被世人們稱作為約瑟夫問題，這個(gè)圈也可以稱作為約瑟夫環(huán)！

我們也可以將這個(gè)問題和小時(shí)候玩過的丟手絹聯(lián)想起來，一群小朋友圍成一個(gè)圈，約定其中一個(gè)小朋友從1開始報(bào)數(shù)，然后后面的小朋友按順序報(bào)數(shù)，當(dāng)一個(gè)小朋友報(bào)數(shù)為k時(shí)，則出列，他的下一位又從1開始報(bào)數(shù)，直到所有人都出列為止~

對于這個(gè)問題：我們需要使用一個(gè)不帶頭節(jié)點(diǎn)的單向環(huán)形鏈表來處理，先構(gòu)成一個(gè)有n個(gè)結(jié)點(diǎn)的單向循環(huán)鏈表，然后從k結(jié)點(diǎn)起，開始從1計(jì)數(shù)，計(jì)數(shù)到m時(shí)，對應(yīng)結(jié)點(diǎn)從鏈表中刪除，被刪除結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)又從1開始計(jì)數(shù)，直到最后一個(gè)結(jié)點(diǎn)也被刪除后，算法結(jié)束！
單向環(huán)形鏈表的具體實(shí)現(xiàn)思路

• 首先，創(chuàng)建一個(gè)first結(jié)點(diǎn)指向第一個(gè)結(jié)點(diǎn)，并且這個(gè)first結(jié)點(diǎn)不能移動！然后再創(chuàng)建一個(gè)輔助結(jié)點(diǎn)pNode，同樣指向第一個(gè)結(jié)點(diǎn)！而且，即使只有一個(gè)結(jié)點(diǎn)，我們也可以讓其形成環(huán)狀結(jié)構(gòu)，也就是將第一個(gè)結(jié)點(diǎn)的next域指向自己！
• 當(dāng)?shù)诙€(gè)結(jié)點(diǎn)加入進(jìn)鏈表的時(shí)候，我們將第一個(gè)結(jié)點(diǎn)的next域指向第二個(gè)結(jié)點(diǎn)，也就是將pNode.next指向第二個(gè)結(jié)點(diǎn)，然后再將第二個(gè)結(jié)點(diǎn)的next域指向first結(jié)點(diǎn)，最后將pNode結(jié)點(diǎn)下移！依次類推，我們就可以得到一個(gè)環(huán)形的單向鏈表！

// 添加結(jié)點(diǎn)public void addNode(int number) {if (number < 2) {System.out.println("至少需要兩個(gè)結(jié)點(diǎn)！");return;}Node pNode = null;for (int i = 1; i <= number; i++) {Node node = new Node(i);if (i == 1) {first = node;first.next = first;pNode = node;} else {pNode.next = node;node.next = first;pNode = node;}}}// 遍歷結(jié)點(diǎn)public void display() {if (first == null) {System.out.println("該鏈表為空！");return;}Node pNode = first;while(true) {System.out.println(pNode);if (pNode.next == first) {break;}pNode = pNode.next;}} }

約瑟夫問題的具體實(shí)現(xiàn)

假設(shè)鏈表中一共有5個(gè)結(jié)點(diǎn)，我們從第1個(gè)結(jié)點(diǎn)開始計(jì)數(shù)，當(dāng)計(jì)數(shù)到2時(shí)，對應(yīng)結(jié)點(diǎn)從鏈表中刪除，下一個(gè)結(jié)點(diǎn)繼續(xù)從1開始計(jì)數(shù)，直到剩下最后一個(gè)結(jié)點(diǎn)！簡單的演算，我們可以得到刪除的順序?yàn)?->4->1->5->3。

具體實(shí)現(xiàn)以上所述的操作，我們需要創(chuàng)建一個(gè)輔助結(jié)點(diǎn)helper，事先指向first結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)，假設(shè)此時(shí)first指向第一個(gè)結(jié)點(diǎn)，那么helper就指向最后一個(gè)結(jié)點(diǎn)！

但在問題的描述中，我們可以定義從第k個(gè)結(jié)點(diǎn)開始計(jì)數(shù)，于是我們先將first結(jié)點(diǎn)和helper結(jié)點(diǎn)移動k-1次！

• 設(shè)置一個(gè)變量count存儲規(guī)定的計(jì)數(shù)，當(dāng)計(jì)數(shù)為count時(shí)，對應(yīng)結(jié)點(diǎn)從鏈表中刪除，同時(shí)，first結(jié)點(diǎn)和helper結(jié)點(diǎn)也需要移動count-1次，這樣first正好指向待刪除的結(jié)點(diǎn)，而help指向前一個(gè)結(jié)點(diǎn)。
• 此時(shí)，開始進(jìn)行結(jié)點(diǎn)刪除操作！首先將first結(jié)點(diǎn)向下移動一次，即first=first.next，然后再將helper.next指向first！

// 約瑟夫public void Josephus(int startNo, int count) {if (startNo < 1 || first == null || count < 0 || count > size) {System.out.println("參數(shù)輸入有誤！");return;}Node helper = first;// 將helper和first移動至第一個(gè)計(jì)數(shù)的結(jié)點(diǎn)for (int i = 0; i < startNo - 1; i++) {helper = helper.next;first = first.next;}// 將helper移動到first的前一個(gè)結(jié)點(diǎn)while(true) {if (helper.next == first) {break;}helper = helper.next;}while(true) {if (helper == first) {break;}// 開始計(jì)數(shù)，將first移動至刪除結(jié)點(diǎn)for (int i = 0; i < count - 1; i++) {first = first.next;helper = helper.next;}System.out.println(first);first = first.next;helper.next = first;}System.out.println("最后的結(jié)點(diǎn)為：" + first);} }

總結(jié)

以上是生活随笔為你收集整理的数据结构-约瑟夫环的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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