本文主要是介绍【DataStructure】 Classical Question: Josephus Cycle，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【Description】
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-Hillimport 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-Hillimport 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这篇关于【DataStructure】 Classical Question: Josephus Cycle的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
