Java解決約瑟夫問(wèn)題代碼實(shí)例
import java.util.ArrayList;
/**
* Java約瑟夫問(wèn)題： n個(gè)人（不同id）圍成一個(gè)圈，從startId(任意數(shù))個(gè)開(kāi)始報(bào)數(shù)m(任意數(shù))個(gè)數(shù)，數(shù)m的人出列排成新隊(duì)列，m清零，
* 然后又從下一個(gè)人開(kāi)始數(shù)m個(gè)數(shù)開(kāi)始，數(shù)到m就出列接在新隊(duì)列尾部，如此重復(fù)，知道所有人都出列為止。
* 打印 出列后的新隊(duì)列
*
* eg
* int n = 10;//總?cè)藬?shù)
* int m = 3; //報(bào)數(shù)個(gè)數(shù)
* int startIndex = 1; //起點(diǎn)位置
* @author Hulk 2014 03 20
*
*/
public class JosephListTest {
public static void main(String[] args) {
long startTime = System.currentTimeMillis();
JosephListTest test = new JosephListTest();
int n = 10; //總?cè)藬?shù)
int m = 3; //報(bào)數(shù)個(gè)數(shù)
int startIndex = 12; //起點(diǎn)位置
System.out.println("JosephListTest: n= " + n + ", m= " + m +
", startIndex= " + startIndex + "\n\nQUEUE RESULT:");
ArrayList<Person> queueList = test.queuePreson(n, m, startIndex);
for (Person person : queueList) {
System.out.println("OUT person: " + person);
}
System.out.println("use time= " +
(System.currentTimeMillis() - startTime));
}
private ArrayList<Person> queuePreson(int n, int m, int startIndex) {
ArrayList<Person> queueList = null;
PersonList list = createList(n);
//list.search();
if ((list != null) && (list.head != null)) {
queueList = new ArrayList<JosephListTest.Person>();
PNode pNode = list.head;
if (startIndex > 0) {
startIndex = startIndex % n;
pNode = list.getNode(startIndex);
} else {
pNode = list.head;
}
int count = 1;
while (list.size > 0) {
Person outPerson = null;
//find
if (count == (m - 1)) {
//delete next node
Person prev = pNode.person;
outPerson = list.remove(prev);
queueList.add(outPerson);
//System.out.println("OUT person: " + outPerson + ", size= " + list.size);
count = 0;
}
pNode = pNode.next;
count++;
}
}
return queueList;
}
private PersonList createList(int n) {
PersonList list = new PersonList();
for (int i = 0; i < n; i++) {
Person person = new Person(i, "name_" + (i + 1));
list.add(i, person);
}
return list;
}
public class PersonList {
PNode head = null;
int size = 0;
public PersonList() {
}
public PersonList(Person person) {
head = new PNode(person, head);
size++;
}
public PersonList(PNode head) {
this.head = head;
head.setNext(head);
size++;
}
public PNode getHead() {
return head;
}
public void setHead(PNode head) {
this.head = head;
}
public int getSize() {
return size;
}
public void setSize(int size) {
this.size = size;
}
public void size(int size) {
this.size = size;
}
public boolean isEmpty() {
return this.size <= 0;
}
public void initHead(Person person) {
if (size == 0) {
head = new PNode(person, head);
} else {
PNode no = head;
head = new PNode(person, no);
}
size++;
}
public void add(int index, Person person) {
if (size == 0) {
head = new PNode(person, head);
head.setNext(head);
//System.out.println("head: " + head);
} else {
if (index < 0) {
index = 0;
}
if (index > size) {
index = size;
}
PNode no = head;
for (int i = 0; i < (index - 1); i++) {
no = no.next;
}
PNode newNode = new PNode(person, no.next);
no.next = newNode;
}
size++;
}
public Person delete(int index) {
PNode pNode = remove(index);
if ((pNode != null) && (pNode.next != null)) {
return pNode.next.person;
}
return null;
}
public PNode remove(int index) {
if (size == 0) {
return null;
} else {
if ((index < 0) || (index >= size)) {
return null;
}
}
PNode no = head;
for (int i = 0; i < (index - 1); i++) {
no = no.next;
}
no.next = no.next.next;
size--;
if ((no != null) && (no.next != null)) {
return no.next;
}
return null;
}
/**
* remove next node of person node, and return the deleted person
* @param prePerson
* @return removed Person
*/
public Person remove(Person prePerson) {
if (prePerson == null) {
return null;
}
if (size == 0) {
return null;
}
PNode preNode = head;
int index = -1;
for (int i = 0; i < size; i++) {
if (preNode.person.id == prePerson.id) {
index = i;
break;
} else {
preNode = preNode.next;
}
}
Person remPerson = null;
if (size <= 1) {
//only one node, get its person and set it as null
remPerson = preNode.person;
preNode = null;
} else {
//preNode.next.person is dest one
remPerson = preNode.next.person;
preNode.next = preNode.next.next;
}
size--;
//System.out.println("deleteing index= " + index + " : " + remPerson + ", size= " + size);
return remPerson;
}
public int update(Person src, Person dest) {
if (src == null) {
return -1;
}
int index = -1;
PNode no = head;
for (int i = 0; i < size; i++) {
if (src.id == no.person.id) {
no.person = dest;
break;
} else {
no = no.next;
}
}
return index;
}
public boolean set(int index, Person person) {
if (person == null) {
return false;
}
if (size == 0) {
return false;
} else {
if ((index < 0) || (index >= size)) {
return false;
}
}
PNode no = head;
for (int i = 0; i < index; i++) {
no = no.next;
}
no.person = person;
return true;
}
public Person get(int index) {
PNode no = getNode(index);
if (no != null) {
return no.person;
}
return null;
}
public PNode getNode(int index) {
if (size == 0) {
return null;
} else {
if ((index < 0) || (index >= size)) {
return null;
}
}
PNode no = head;
for (int i = 0; i < index; i++) {
no = no.next;
}
return no;
}
public void search() {
int sizeLong = size;
PNode no = head;
for (int i = 0; i < sizeLong; i++) {
System.out.println("search index= " + i + ", " + no);
no = no.next;
}
}
}
public class PNode {
Person person;
PNode next = null;
public PNode() {
}
public PNode(Person person) {
this.person = person;
}
public PNode(Person person, PNode next) {
this.person = person;
this.next = next;
}
@Override
public String toString() {
return "PNode [person=" + person.id + ", next=" + next.person.id +
"]";
}
public Person getPerson() {
return person;
}
public void setPerson(Person person) {
this.person = person;
}
public PNode getNext() {
return next;
}
public void setNext(PNode next) {
this.next = next;
}
}
public class Person {
int id = 0;
String name = "";
public Person() {
}
public Person(int id, String name) {
super();
this.id = id;
this.name = name;
}
@Override
public String toString() {
return "Person [id=" + id + ", name=" + name + "]";
}
}
}
- java基于雙向環(huán)形鏈表解決丟手帕問(wèn)題的方法示例
- Java用單向環(huán)形鏈表來(lái)解決約瑟夫環(huán)Josepfu問(wèn)題
- Java數(shù)據(jù)結(jié)構(gòu)與算法之雙向鏈表、環(huán)形鏈表及約瑟夫問(wèn)題深入理解
- Java 數(shù)據(jù)結(jié)構(gòu)與算法系列精講之環(huán)形鏈表
- java 實(shí)現(xiàn)約瑟夫環(huán)的實(shí)例代碼
- Java簡(jiǎn)單實(shí)現(xiàn)約瑟夫環(huán)算法示例
- java使用鏈表實(shí)現(xiàn)約瑟夫環(huán)
- Java數(shù)據(jù)結(jié)構(gòu)之環(huán)形鏈表和約瑟夫問(wèn)題詳解
相關(guān)文章
這篇文章主要介紹了Java的后臺(tái)文件夾下文件的遍歷完整代碼，首先分享了java中遍歷一個(gè)文件夾里邊的所有文件，然后介紹了用Java遍歷一個(gè)文件夾并獲取它里面的所有內(nèi)容詳細(xì)代碼，具有一定借鑒價(jià)值，需要的朋友可以參考下。2017-12-12
mybatis中批量更新多個(gè)字段的2種實(shí)現(xiàn)方法
當(dāng)我們使用mybatis的時(shí)候,可能經(jīng)常會(huì)碰到一批數(shù)據(jù)的批量更新問(wèn)題,因?yàn)槿绻粭l數(shù)據(jù)一更新,那每一條數(shù)據(jù)就需要涉及到一次數(shù)據(jù)庫(kù)的操作,本文主要介紹了mybatis中批量更新多個(gè)字段的2種實(shí)現(xiàn)方法,感興趣的可以了解一下2023-09-09
Springboot設(shè)置默認(rèn)訪問(wèn)路徑方法實(shí)現(xiàn)
這篇文章主要介紹了Springboot設(shè)置默認(rèn)訪問(wèn)路徑方法實(shí)現(xiàn),文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-12-12
文件上傳SpringBoot后端MultipartFile參數(shù)報(bào)空問(wèn)題的解決辦法
這篇文章主要介紹了文件上傳SpringBoot后端MultipartFile參數(shù)報(bào)空問(wèn)題的解決辦法,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-11-11
Java同步框架AbstractQueuedSynchronizer詳解
本篇文章主要介紹了Java同步框架AbstractQueuedSynchronizer詳解，小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-10-10
新建一個(gè)springboot單體項(xiàng)目的教程
這篇文章主要介紹了新建一個(gè)springboot單體項(xiàng)目的教程,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2025-04-04
這篇文章主要介紹了探究Java的常量，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2021-08-08
詳解spring batch的使用和定時(shí)器Quart的使用
spring Batch是一個(gè)基于Spring的企業(yè)級(jí)批處理框架，它通過(guò)配合定時(shí)器Quartz來(lái)輕易實(shí)現(xiàn)大批量的數(shù)據(jù)讀取或插入，并且全程自動(dòng)化，無(wú)需人員管理2017-08-08
spring boot 項(xiàng)目利用Jenkins實(shí)現(xiàn)自動(dòng)化部署的教程詳解
這篇文章主要介紹了spring boot 項(xiàng)目利用Jenkins實(shí)現(xiàn)自動(dòng)化部署的方法，本文給大家介紹的非常詳細(xì)，具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2018-07-07
升級(jí)dubbo2.7.4.1版本平滑遷移到注冊(cè)中心nacos
這篇文章主要為大家介紹了2.7.4.1的dubbo平滑遷移到注冊(cè)中心nacos的兩種版本升級(jí)方案，以及為什要升級(jí)，有需要的朋友可以借鑒參考下，希望能夠有所幫助2022-02-02