總共3中解決方法，1、數學推導，2、使用ArrayList遞歸解決，3、使用首位相連的LinkedList解決
import java.util.ArrayList;
public class Josephus {
public static void main(String[] args) {
int n = 13;
int k = 3;
int last;
//last =getLast(n,k);//使用數學推導求結果
//System.out.println(last);
MyLinkedList list = new MyLinkedList();
for (int i = 1; i <= n; i++) {
list.add(i);
}
//隻要連結清單中元素個數大于1個，則指向下面步驟
while(list.length>1){
Node temp = list.first;//獲得頭節點
//将temp節點從頭節點向後挪k個位置
for (int i = 1; i < k; i++) {
temp = temp.next;
}
System.out.println("被移除的編号為："+temp.value);
list.remove(temp);//移除目前temp位置的節點
System.out.println("剩餘元素為："+list.toString()+",長度為"+list.length);
}
//當上面循環結束時，連結清單内隻剩1個元素
last = list.first.value;
System.out.println(last);
}
public static int getLast(int n , int k){
int last = 1;//這是初始值，即環内為1個人時剩餘的人的編号，必然為1，也是後面推導的基礎
//System.out.println("當環内有1個人時，剩餘的是:1");
for (int i = 2; i <= n; i++) {//當圈内為i個人時，結果是圈内為i-1個人的結果加K後對i求餘
last = ((last + k - 1) % i) + 1;//為避免出現結果為0，讓i-1的結果先減1，求餘後再加1
//System.out.println("當環内有" + i + "個人時，剩餘的是:" + last);
}
return last;
}
public static int getLast(ArrayList list, int k , int m){
int last = -1;//用來放置最後一個人的編号
int index = -1;//用來放置目前一輪被移除的人的下标
if (list.size() == 1) { // 如果集合内隻剩一個元素，則直接傳回該元素作為結果
last = list.get(0);
} else {
index = (m + k - 1) % list.size(); // 求出目前一輪被移除的人的下标
list.remove(index); // 将該人移除
m = index % list.size(); // 求出新一輪報數時開始的人在新集合裡的下标
last = getLast(list, k, m); // 使用剩餘的集合和m的位置重新開始下一輪計算
}
return last;
}
}
class Node{
Integer value;
Node next;
Node prev;
public Node(){
value = null;
prev=null;
next = null;
}
public Node(Integer value){
this.value = value;
next = null;
prev = null;
}
public String toString(){
return this.prev.value+""+this.next.value;
}
}
class MyLinkedList{
public Node first;
public Node last;
public int length;
public MyLinkedList(){
first = new Node();
last = first;
length = 0;
}
//在連結清單結尾增加元素的方法
public void add(Integer i){
if(length == 0){
first.value = i;//添加第一個元素，隻需要設定該元素的value
}else{
Node temp = new Node();//添加元素時，1、建立一個元素，
temp.value = i;
temp.prev = last;//2、然後先與last節點建立雙向關系，
last.next = temp;
first.prev = temp;//3、再與first節點建立雙向關系，
temp.next = first;
last = temp;//4、最後讓last指向該節點，3、4步可颠倒
}
length++;
}
//從連結清單中删除指定節點的方法
public void remove(Node node){
node.prev.next = node.next;//将前節點的next跳過本節點，指向下個節點
node.next.prev = node.prev;//将後節點的prev跳過本節點，指向前節點，此時該節點已經從連結清單中移除了
this.first = node.next;//指定後節點為頭節點
this.last = node.prev;//指定前節點為尾節點
node = null;
length--;
}
public String toString(){
String str ="[";
Node temp = first;
for (int i = 1 ; i < length; i++ ) {
str += temp.value+",";
temp = temp.next;
}
str += (temp.value+"]");
return str;
}
}