双方向チェーンテーブルによるジョセフの実現
2335 ワード
public class Count3Quit1 {
//
public static int count(int num) {
boolean[] flags = new boolean[num];
int leftNum = flags.length;
int countNum = 0;
int index = 0;
while (leftNum > 1) {
if (!flags[index]) {
countNum++;
if (countNum == 3) {
flags[index] = true;
leftNum--;
countNum = 0;
}
}
index++;
if (index == flags.length) {
index = 0;
}
}
for (int i = 0; i < flags.length; i++) {
if (!flags[i]) {
return i + 1;
}
}
return -1;
}
//
public static int countByLink(int num) {
Node head = new Node(null, 1, null);
Node tail = head;
for (int i = 2; i <= num; i++) {
Node next = new Node(tail, i, null);
tail.setNext(next);
tail = next;
}
tail.setNext(head);
head.setPrevious(tail);
int length = num;
int countNum = 0;
Node currentNode = head;
while (currentNode.getData() != currentNode.getNext().getData()) {
countNum++;
if (countNum == 3) {
currentNode.getPrevious().setNext(currentNode.getNext());
currentNode.getNext().setPrevious(currentNode.getPrevious());
countNum = 0;
}
currentNode = currentNode.getNext();
}
return currentNode.getData();
}
public static void main(String[] args) {
System.out.println(countByLink(500));
}
}
class Node {
private int data;
private Node next;
private Node previous;
public Node getPrevious() {
return previous;
}
public void setPrevious(Node previous) {
this.previous = previous;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public Node(Node previous, int data, Node next) {
super();
this.data = data;
this.next = next;
this.previous = previous;
}
}