【DataStructure】 Classical Question: Josephus Cycle
3726 단어 자바CollectionDataStructure
This problem is based upon a report by the historian Joseph ben Matthias (Josephus) on the outcome of a suicide pact that he had made between himself and 40 soldiers as they were besieged by superior Roman forces in 67 A.D. Josephus proposed that each man slay his neighbor. This scheme necessarily leaves one to kill himself. Josephus cleverly contrived to be that one, thus surviving to tell the tale.
【Implementation】
package com.albertshao.ds.ring;
// Data Structures with Java, Second Edition
// by John R. Hubbard
// Copyright 2007 by McGraw-Hill
import java.util.*;
public class Ring<E> extends AbstractList<E> implements List<E> {
private Node<E> last;
private int size;
public boolean add(E element) {
if (size == 0) {
last = new Node<E>(element, null);
last.next = last;
} else {
last.next = new Node<E>(element, last.next);
last = last.next;
}
++size;
return true;
}
public E get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
Node<E> p = last.next;
for (int i=0; i<index; i++) {
p = p.next;
}
return p.element;
}
public Iterator<E> iterator() {
return new RingIterator();
}
public String toString() {
Node<E> p = last.next;
StringBuilder buf = new StringBuilder("[" + p.element);
while (p != last) {
p = p.next;
buf.append(", " + p.element);
}
buf.append("]");
return buf.toString();
}
public int size() {
return size;
}
private class RingIterator implements Iterator<E> {
private Node<E> preLastNext = last;
private Node<E> lastNext;
public boolean hasNext() {
return size > 0;
}
public E next() {
if (lastNext == null) {
lastNext = preLastNext.next;
} else {
preLastNext = lastNext;
lastNext = lastNext.next;
}
return lastNext.element;
}
public void remove() {
if (lastNext == null) {
throw new IllegalStateException();
}
if (size == 1) {
last = preLastNext = null;
} else {
preLastNext.next = lastNext.next;
}
if (lastNext == last) {
last = preLastNext;
}
lastNext = null;
--size;
}
}
private static class Node<E> {
E element;
Node<E> next;
Node(E element, Node<E> next) {
this.element = element;
this.next = next;
}
}
}
package com.albertshao.ds.ring;
// Data Structures with Java, Second Edition
// by John R. Hubbard
// Copyright 2007 by McGraw-Hill
import java.util.*;
public class Josephus {
public static final int SOLDIERS = 8;
public static final String ALPHA = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
public static void main(String[] args) {
Ring<String> ring = new Ring<String>();
for (int i=0; i<SOLDIERS; i++) {
ring.add(ALPHA.substring(i, i+1));
}
System.out.println(ring);
Iterator<String> it = ring.iterator();
String killer = it.next();
while (ring.size() > 1) {
String victim = it.next();
System.out.println(killer + " killed " + victim);
it.remove();
killer = it.next();
}
System.out.println("The lone survivor is " + it.next());
}
}
【Result】
[A, B, C, D, E, F, G, H]
A killed B
C killed D
E killed F
G killed H
A killed C
E killed G
A killed E
The lone survivor is A
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Is Eclipse IDE dying?In 2014 the Eclipse IDE is the leading development environment for Java with a market share of approximately 65%. but ac...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.