约瑟夫问题



package 约瑟夫问题;


public class MainClass {

 public static void main(String[] args) {
  Cyclink cl = new Cyclink();
  cl.setLen(1000000000);
  cl.createLink();
  //cl.print();
  int k=3;
  cl.play(1, 3);
 }


}
class Node{
 int num;
 Node next;
 public Node(int num) {
  this.num = num;
 }
}
class Cyclink{
 Node firstnode=null;//第一个节点
 Node temp=null;
 int len=0;// 链表为0
 public void setLen(int len){
  this.len=len;
 }

 public Cyclink() {
 }

 public void createLink(){
  for (int i=1;i<=len;i++){
   if (i==1){
    Node node=new Node(i);
    firstnode=node;
    temp=node;
   }else{
    if(i==len){
     //最后一个节点
     Node node=new Node(i);
     temp.next=node;
     temp=node;
     temp.next=firstnode;
    }else{
    Node node=new Node(i);
    temp.next=node;
    temp=node;
    }
   }



  }


 }
public void print(){
 Node temp=firstnode ;
 do{
  System.out.println(temp.num);
  temp=temp.next;
 }while (temp!=firstnode);
}
public void play(int k,int m){
 //从k开始数，数m次
 Node temp=firstnode ;
 //找到K在哪里
 for(int i=1;i<k;i++){
  temp=temp.next;
 }
 while(len!=1){
 //s数m次
 for (int i=1;i<m;i++){
  temp=temp.next;
 }
 //找到m之前的那个节点
 Node temp2=temp;
 while(temp2.next!=temp){
  temp2=temp2.next;
 }
 //删除
 System.out.println(temp.num);
 temp2.next=(temp.next);
 temp=temp.next;
 len--;
 }
 //最后一个
 System.out.println("最后"+temp.num);
}
}