java模擬環(huán)形鏈表解決約瑟夫問題

此文是觀看尚硅谷韓老師的數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)視頻整理的筆記

約瑟夫問題描述

約瑟夫問題（有時也稱為約瑟夫斯置換，是一個出現(xiàn)在計算機科學(xué)和數(shù)學(xué)中的問題。在計算機編程的算法中，類似問題又稱為約瑟夫環(huán)。又稱“丟手絹問題”.）

Josephu(約瑟夫、約瑟夫環(huán)) 問題
Josephu 問題為：設(shè)編號為 1，2，… n 的 n 個人圍坐一圈，約定編號為 k（1<=k<=n）的人從 1 開始報數(shù)，數(shù)到 m 的那個人出列，它的下一位又從 1 開始報數(shù)，數(shù)到 m 的那個人又出列，依次類推，直到所有人出列為止，由此產(chǎn)生一個出隊編號的序列

環(huán)形鏈表介紹

環(huán)形鏈表是另一種形式的鏈式存貯結(jié)構(gòu)。它的特點是表中最后一個結(jié)點的指針域指向頭結(jié)點，整個鏈表形成一個環(huán)。

解決約瑟夫圖解問題思路

構(gòu)建環(huán)形鏈表思路

解決約瑟夫問題代碼思路

代碼演示(代碼中有詳細解釋)

package com.fs.demo_2020_07_17_CircleSingleLinkedListTable; /* 環(huán)形鏈表解決約瑟夫問題*/ public class CircleSingleLinkedListTable {public static void main(String[] args) {//測試一下CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();//形成5個節(jié)點的環(huán)形鏈表 // circleSingleLinkedList.addNode(5); // circleSingleLinkedList.showNode();System.out.println("-----------測試計算約瑟夫問題----------");//測試約瑟夫問題circleSingleLinkedList.countNode(1,2,5);} }//創(chuàng)建一個環(huán)形的單向鏈表 class CircleSingleLinkedList{//創(chuàng)建一個first 節(jié)點,當前沒有編號private Node first = null;//添加一個節(jié)點,構(gòu)建成一個環(huán)形的鏈表public void addNode(int nums){//先對nums進行判斷,if (nums<1){System.out.println("給定的nums的值請大于1");return;}//創(chuàng)建一個輔助指針,幫助構(gòu)建環(huán)形鏈表Node curNode = null;//使用for來創(chuàng)建我們的環(huán)形鏈表for (int i = 1; i <= nums; i++) {//根據(jù)編號,來創(chuàng)建小孩節(jié)點Node node = new Node(i);//如果是第一個小孩,先讓自己構(gòu)成環(huán)if (i==1){//先讓first指向第一個節(jié)點first = node;//然后讓第一個 節(jié)點的next指向第一個節(jié)點,形成環(huán)形first.setNext(first);//讓輔助指針也指向我們的第一個節(jié)點curNode = first;}else {//如果不是第一個節(jié)點了//就先讓輔助指針指向的節(jié)點的下一個節(jié)點為當前循環(huán)創(chuàng)建的nodecurNode.setNext(node);//讓當前循環(huán)創(chuàng)建的節(jié)點的下一個節(jié)點指向first,形成環(huán)形node.setNext(first);//最后讓輔助指針指向循環(huán)創(chuàng)建的新的節(jié)點curNode = node;}}}//遍歷當前的環(huán)形鏈表public void showNode(){//先判斷鏈表是否為空if (first == null){System.out.println("沒有任何節(jié)點,請給入正確的值,讓鏈表形成環(huán)形");return;}//因為first在遍歷的時候不能移動,我們還是需要使用一個輔助指針完成遍歷Node curNode = first;//先讓輔助指針指向頭指針while (true){System.out.println("當前的節(jié)點編號為:"+curNode.getNum());if (curNode.getNext() == first){//當指針移動到最后一個節(jié)點的時候,那么這個節(jié)點的下一個節(jié)點是first,所以遍歷完了break;}//否則就還有節(jié)點,那就將輔助指針移動到下一個節(jié)點curNode = curNode.getNext();}}/*** 根據(jù)用戶輸入的節(jié)點個數(shù),解決節(jié)點出圈的循序,解決約瑟夫的問題* Josephu 問題為：設(shè)編號為 1，2，… n 的 n 個人圍坐一圈，約定編號為 k（1<=k<=n）的人從 1 開始報數(shù)，數(shù)* 到 m 的那個人出列，它的下一位又從 1 開始報數(shù)，數(shù)到 m 的那個人又出列，依次類推，直到所有人出列為止，由* 此產(chǎn)生一個出隊編號的序列。* @param startNum 表示從第幾個小孩開始報數(shù)* @param countNum 表示數(shù)幾下,就出列* @param nums 表示最初有多少個節(jié)點*/public void countNode(int startNum,int countNum,int nums){//創(chuàng)建鏈表addNode(nums);//先對數(shù)據(jù)進行校驗if (first == null || startNum < 1 || startNum > nums ){System.out.println("請正確傳入?yún)?shù)~~~");return;}//創(chuàng)建一個輔助指針curNode,事先應(yīng)該指向環(huán)形鏈表最后這個節(jié)點Node curNod = first;while (true){if (curNod.getNext() == first){//說明輔助指針指向最后一個節(jié)點break;}//一直循環(huán),直到輔助指針指向了最后一個節(jié)點curNod = curNod.getNext();}//節(jié)點因為first和curNod現(xiàn)在一個是指向頭節(jié)點,一個是指向最后一個節(jié)點//當對節(jié)點進行計數(shù)的時候,從那個節(jié)點開始計數(shù),假設(shè)我要從第二個節(jié)點開始計數(shù),// 我就需要讓first和curNod移動一位,那么就是startNum-1位for (int i = 0; i < startNum - 1; i++) {//讓first移動startNum - 1位first = first.getNext();//讓curNod移動startNum - 1位curNod = curNod.getNext();}//節(jié)點開始計數(shù)時候,讓first和curNod同時移動 countNum -1 次,然后讓first指向的節(jié)點斷開(也就是出圈)//假設(shè)從1開始數(shù)數(shù)2下就出列,那么就是2號出列因為前面first指向的是1號,while (true){if (curNod == first){//說明環(huán)形鏈表只有一個節(jié)點break;}//讓first和curNod同時移動 countNum -1 次for (int i = 0; i < countNum - 1; i++) {//移動first = first.getNext();curNod = curNod.getNext();}//這時first指向的節(jié)點,就是要出圈的節(jié)點System.out.println("當前first指向的出圈節(jié)點為:"+first.getNum());//將first指向first的下一個節(jié)點first = first.getNext();//在將輔助指針指向firstcurNod.setNext(first);}//循環(huán)完成后,那么就只有一個節(jié)點了,那樣就會自己指向自己,就是最后一個出圈System.out.println("最后一個出圈的節(jié)點為:"+first.getNum());}}//創(chuàng)建一個類來表示一個節(jié)點 class Node {public int num;//當前節(jié)點數(shù)public Node next;//當前節(jié)點存儲的下一個節(jié)點信息//提供構(gòu)造方法來初始化這個節(jié)點信息public Node(int num) {this.num = num;}//提供get,set方法來獲取Node對象public int getNum() {return num;}public void setNum(int num) {this.num = num;}public Node getNext() {return next;}public void setNext(Node next) {this.next = next;} }

測試結(jié)果

總結(jié)

以上是生活随笔為你收集整理的java模拟单链表环形链表解决约瑟夫问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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