双方向チェーンテーブルによるジョセフの実現


 
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; 
} 

}