Java使用單鏈表實現(xiàn)約瑟夫環(huán)
本文實例為大家分享了Java使用單鏈表實現(xiàn)約瑟夫環(huán)的具體代碼,供大家參考,具體內容如下
構建一個單向的環(huán)形鏈表思路
1.先創(chuàng)建第一個節(jié)點, 讓first指向該節(jié)點, 并形成環(huán)形
2.后面當我們每創(chuàng)建一個新的節(jié)點, 就把該節(jié)點加入到已有的環(huán)形鏈表中即可.
遍歷環(huán)形鏈表思路
1.先讓一個輔助指針(變量)curBoy, 指向first節(jié)點
2.然后通過一個while循環(huán)遍歷該環(huán)形鏈表即可 curBoy.next == first 結束
生成小孩出圈順序的思路
1.根據用戶的輸入, 生成一個小孩出圈的順序
n = 5, 即有 5 個人
k = 1, 即從第1個人開始數(shù)數(shù)
m =2, 每次進行數(shù)兩下
2.需求創(chuàng)建一個輔助指針(變量)helper, 事先應該指向環(huán)形鏈表的最后這個節(jié)點
3.在小孩報數(shù)前, 讓first 指針和 helper指針分別指向正確的位置, 即需要移動 k-1次
4.在小孩報數(shù)時, 每次讓first指針和helper指針移動 m-1次
5.此時 first指針 指向的節(jié)點就是出圈的節(jié)點
代碼實現(xiàn)
first = frist.getNext(); helper.next = first;
由于first指向的節(jié)點數(shù)就沒有任何引用, 就會被回收
package com.beyond.linkedlist; import org.omg.CORBA.PUBLIC_MEMBER; public class Josepfu { public static void main(String[] args){ CircleSingleLinkedList name = new CircleSingleLinkedList(); name.addBoy(5); name.showBoy(); name.countBoy(1, 2, 5); } } //創(chuàng)建一個環(huán)形的單向鏈表 class CircleSingleLinkedList { // 創(chuàng)建一個first節(jié)點,當前沒有編號的 private Boy first = new Boy(-1); // 添加小孩節(jié)點,構成一個環(huán)形的鏈表 public void addBoy(int nums) { if (nums < 1) { System.out.println("nums 的值不正常"); return; } Boy curBoy = null; // 輔助指針,幫助構造環(huán)形鏈表 // 使用for來創(chuàng)建我們的環(huán)形鏈表 for (int i = 1; i <= nums; i++) { // 根據編號,創(chuàng)建小孩節(jié)點 Boy boy = new Boy(i); // 如果是第一個小孩 if (i == 1) { first = boy; first.setNext(first); curBoy = first; } else { curBoy.setNext(boy); boy.setNext(first); curBoy = boy; } } } // 遍歷當前的環(huán)形鏈表 public void showBoy() { if (first == null) { System.out.println("沒有小孩!"); return; } // 因為first不能動, 因此我們仍然使用一個輔助指針完成遍歷 Boy curBoy = first; while (true) { System.out.printf("小孩的編號%d \n", curBoy.getNo()); if (curBoy.getNext() == first) { break; } curBoy = curBoy.getNext(); // 后移 } } // 根據用戶的輸入,計算出小孩出圈的順序 /** * * @param startNo 表示從第幾個小孩開始數(shù)數(shù) * @param countNum 表示數(shù)幾下 * @param nums 表示最初有多少個小孩在圈子中 */ public void countBoy(int startNo, int countNum, int nums) { if (first == null || startNo < 1 || startNo > nums) { System.out.println("輸入數(shù)據有誤~"); return; } // 創(chuàng)建所需要的輔助指針,幫助小孩出圈 Boy helper = first; // 需求創(chuàng)建一個輔助指針helper, 事先指向該環(huán)形列表的最后這個節(jié)點 while (true) { if (helper.getNext() == first) { break; } helper = helper.getNext(); } //小孩報數(shù)前,將指針移動到各自開始的位置,移動 k-1 次 for (int i = 0; i < startNo-1; i++) { first = first.getNext(); helper = helper.getNext(); } //當小孩報數(shù)時, 讓first 和 helper 指針同時移動 m-1次, 然后出圈 //這是一個循環(huán)操作,直到圈中只剩下一個小孩為止 while (true) { if (helper == first) { break; } for (int i = 0; i < countNum-1; i++) { first = first.getNext(); helper = helper.getNext(); } System.out.printf("小孩%d出圈!\n",first.getNo()); first = first.getNext(); helper.setNext(first); } System.out.printf("最后留在圈中的小孩編號為:%d",first.getNo()); } } //先創(chuàng)建一個Boy類, 表示一個節(jié)點 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) { this.no = no; } public Boy getNext() { return next; } public void setNext(Boy next) { this.next = next; } }
以上就是本文的全部內容,希望對大家的學習有所幫助,也希望大家多多支持腳本之家。
相關文章
springboot+vue實現(xiàn)七牛云頭像的上傳
本文將介紹如何在Spring Boot項目中利用七牛云進行圖片上傳并將圖片存儲在云存儲中,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2023-08-08SpringBoot2.4.2下使用Redis配置Lettuce的示例
這篇文章主要介紹了SpringBoot2.4.2下使用Redis配置Lettuce,Springboot2.4.2下默認使用的就是Lettuce而不是Jedis因此無需在依賴進行排除Jedis,本文給大家介紹的非常詳細,感興趣的朋友跟隨小編一起看看吧2022-01-01IntelliJ IDEA本地代碼提交到github網站不顯示與本地不同步問題的解決辦法
今天小編就為大家分享一篇關于IntelliJ IDEA本地代碼提交到github網站不顯示與本地不同步問題的解決辦法,小編覺得內容挺不錯的,現(xiàn)在分享給大家,具有很好的參考價值,需要的朋友一起跟隨小編來看看吧2018-10-10基于SpringBoot實現(xiàn)自定義插件的流程詳解
在SpringBoot中,插件是一種擴展機制,它可以幫助我們在應用程序中快速地添加一些額外的功能,在本文中,我們將介紹如何使用 SpringBoot實現(xiàn)自定義插件,需要的朋友可以參考下2023-06-06SpringCloud中NacosNamingService的作用詳解
這篇文章主要介紹了SpringCloud中NacosNamingService的作用詳解,NacosNamingService類完成服務實例注冊,撤銷與獲取服務實例操作,NacosNamingService初始化采用單例模式,使用反射生成,需要的朋友可以參考下2023-11-11