Java解决约瑟夫问题代码实例
import java.util.arraylist;
/**
* java约瑟夫问题: n个人(不同id)围成一个圈,从startid(任意数)个开始报数m(任意数)个数,数m的人出列排成新队列,m清零,
* 然后又从下一个人开始数m个数开始,数到m就出列接在新队列尾部,如此重复,知道所有人都出列为止。
* 打印 出列后的新队列
*
* eg
* int n = 10;//总人数
* int m = 3; //报数个数
* int startindex = 1; //起点位置
* @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; //总人数
int m = 3; //报数个数
int startindex = 12; //起点位置
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 + "]";
}
}
}