• • 約瑟夫問(wèn)題
  • • 問(wèn)題來(lái)歷
    • 循環(huán)鏈表進(jìn)行模擬
    • 思路

約瑟夫問(wèn)題

問(wèn)題來(lái)歷

據(jù)說(shuō)著名猶太歷史學(xué)家Josephus有過(guò)以下的故事：在羅馬人占領(lǐng)喬塔帕特后，39 個(gè)猶太人與Josephus及他的朋友躲到一個(gè)洞中，39個(gè)猶太人決定寧愿死也不要被敵人抓到，于是決定了一個(gè)自殺方式，41個(gè)人排成一個(gè)圓圈，由第1個(gè)人開(kāi)始報(bào)數(shù)，每報(bào)數(shù)到第3人該人就必須自殺，然后再由下一個(gè)重新報(bào)數(shù)，直到所有人都自殺身亡為止。然而Josephus 和他的朋友并不想遵從。首先從一個(gè)人開(kāi)始，越過(guò)k-2個(gè)人（因?yàn)榈谝粋€(gè)人已經(jīng)被越過(guò)），并殺掉第k個(gè)人。接著，再越過(guò)k-1個(gè)人，并殺掉第k個(gè)人。這個(gè)過(guò)程沿著圓圈一直進(jìn)行，直到最終只剩下一個(gè)人留下，這個(gè)人就可以繼續(xù)活著。問(wèn)題是，給定了和，一開(kāi)始要站在什么地方才能避免被處決。Josephus要他的朋友先假裝遵從，他將朋友與自己安排在第16個(gè)與第31個(gè)位置，于是逃過(guò)了這場(chǎng)死亡游戲。

循環(huán)鏈表進(jìn)行模擬

因?yàn)榧s瑟夫問(wèn)題是一個(gè)環(huán)狀，因此又被稱(chēng)為約瑟夫環(huán)，結(jié)構(gòu)與循環(huán)鏈表相似，因此可以用循環(huán)鏈表進(jìn)行模擬。

思路

• 創(chuàng)建節(jié)點(diǎn)

  class Person {//序號(hào)private int num;//后繼指針,指向下一個(gè)節(jié)點(diǎn)private Person next;public Person(int num) {this.num = num;}public int getNum() {return num;}public void setNum(int num) {this.num = num;}public Person getNext() {return next;}public void setNext(Person next) {this.next = next;} }

• 創(chuàng)建一個(gè)單向的環(huán)形鏈表

• 先創(chuàng)建第一個(gè)頭節(jié)點(diǎn)，并讓first指針指向該節(jié)點(diǎn)，next指針指向本身，形成環(huán)狀。

• 后面每創(chuàng)建一個(gè)新的節(jié)點(diǎn)，就把其加到已有的環(huán)形鏈表中。

/*** 單向的環(huán)形鏈表*/ class CircleSingleLinkedList {/*** 創(chuàng)建一個(gè)first節(jié)點(diǎn)*/private Person first;/*** 添加節(jié)點(diǎn)構(gòu)建環(huán)形鏈表* @param nums 要?jiǎng)?chuàng)建的節(jié)點(diǎn)個(gè)數(shù)*/public void addPerson(int nums){if (nums < 1){System.out.println("nums值不正確！");return;}//幫助構(gòu)建環(huán)形鏈表Person temp = null;//使用for來(lái)創(chuàng)建我們的環(huán)形鏈表for (int i = 1; i <= nums ; i++){//根據(jù)編號(hào)創(chuàng)建節(jié)點(diǎn)Person person = new Person(i);//頭節(jié)點(diǎn)if (i == 1){first = person;//構(gòu)成環(huán)狀first.setNext(first);//讓指針指向第一個(gè)節(jié)點(diǎn)temp = first;continue;}temp.setNext(person);person.setNext(first);temp = person;}} }

• 遍歷環(huán)形鏈表

• 先讓一個(gè)輔助指針temp指向first頭節(jié)點(diǎn)
• 通過(guò)while循環(huán)遍歷該環(huán)形鏈表
public void list() {if (first == null){System.out.println("空鏈表");return;}//頭節(jié)點(diǎn)不能動(dòng),用輔助指針來(lái)實(shí)現(xiàn)遍歷Person temp = first;while (true){System.out.printf("編號(hào):%d\n",temp.getNum());//遍歷完畢if (temp.getNext() == first){break;}//指針后移temp = temp.getNext();} }

• 計(jì)算各個(gè)節(jié)點(diǎn)出表順序

• 創(chuàng)建一個(gè)輔助指針end指向鏈表的最后一個(gè)節(jié)點(diǎn)

• 根據(jù)起始報(bào)數(shù)位置startNum，讓first和end指針同時(shí)移動(dòng)startNum-1次

• 開(kāi)始報(bào)數(shù)，每次報(bào)數(shù)讓first和end指針向后移動(dòng)countNums-1次

• 最后first指針指向的節(jié)點(diǎn)就是要出表的節(jié)點(diǎn)

• 移出該節(jié)點(diǎn)，重復(fù)34步驟。

/*** 根據(jù)用戶(hù)的輸入計(jì)算出人出圈的順序* @param startNum 表示從第幾個(gè)人開(kāi)始報(bào)數(shù)* @param countNums 表示每次數(shù)幾次* @param personNums 表示最初有多少人*/ public void play(int startNum,int countNums,int personNums) {if (first == null || startNum < 1 || startNum > personNums){System.out.println("參數(shù)輸入有誤，請(qǐng)重新輸入");return;}//創(chuàng)建輔助指針Person end = first;//開(kāi)始報(bào)數(shù)之前讓end指針指向最后一個(gè)節(jié)點(diǎn)while (true){if (end.getNext() == first){break;}end = end.getNext();}//報(bào)數(shù)前讓first和end根據(jù)startNum進(jìn)行校準(zhǔn)for (int i = 0; i < startNum - 1; i++){first = first.getNext();end = end.getNext();}//報(bào)數(shù)時(shí)，讓first和end指針同時(shí)移動(dòng)(countNums-1)次while (true){//圈中只有一個(gè)節(jié)點(diǎn)if (end == first){break;}for (int i = 0; i < countNums - 1; i++){first = first.getNext();end = end.getNext();}System.out.printf("出圈號(hào)碼:%d\n",first.getNum());first = first.getNext();end.setNext(first);}System.out.printf("最后留在圈中的號(hào)碼是：%d\n",first.getNum()); }

---

測(cè)試

public class Josephu {public static void main(String[] args) {CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();//添加節(jié)點(diǎn)circleSingleLinkedList.addPerson(6);//遍歷鏈表circleSingleLinkedList.list();//計(jì)算出圈順序并輸出circleSingleLinkedList.play(1,5,6);} } ------------------------------------------------------------------------------------------------------------------- //輸出結(jié)果: 編號(hào):1 編號(hào):2 編號(hào):3 編號(hào):4 編號(hào):5 編號(hào):6 出圈號(hào)碼:5 出圈號(hào)碼:4 出圈號(hào)碼:6 出圈號(hào)碼:2 出圈號(hào)碼:3 最后留在圈中的號(hào)碼是：1 5->4->6->2->3->1

如有錯(cuò)誤或不足歡迎評(píng)論指正。

總結(jié)

以上是生活随笔為你收集整理的数据结构：循环链表解决约瑟夫问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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