Josephus问题Java实现

  1 package com.qingfeng;
  2 /**
  3  * @author Administrator
  4  * 功能：约瑟夫问题：
  5  * 设编号分别为:1,2,...,n的n个人围坐一圈。
  6  * 约定序号为k(1 <= k < = n)的人从1开始计数，数到m的那个人出列，
  7  * 他的下一位又从1开始计数，数到m的那个人又出列，依次类推，直到所有人出列为止。
  8  */
  9 public class Josephus {
 10 
 11     public static void main(String[] args) {
 12         // TODO Auto-generated method stub
 13         KidLink kid = new KidLink();
 14         kid.setLength(5);
 15         kid.creatLink();
 16         kid.setM(2);
 17         kid.setK(3);
 18         
 19         kid.show();
 20         kid.play();
 21     }
 22 }
 23 //孩子类
 24 class Kid
 25 {
 26     //成员变量
 27     int no;//孩子编号
 28     Kid nextKid;//下一个孩子的引用   关键点！
 29     
 30     //构造方法
 31     public Kid(int no)//设置孩子的编号
 32     {
 33         this.no = no;
 34     }
 35 }
 36 
 37 //孩子环形链表类
 38 class KidLink
 39 {
 40     //成员变量
 41     Kid firstKid;//第一个孩子的引用  不能动!！关键点！
 42 
 43     int i;
 44     int len;//圈的长度：多少个人
 45     
 46     Kid temp;//跑龙套
 47     
 48     int m;//约定开始数数的那个人
 49     int k;//约定数几下出圈
 50     
 51     //成员方法
 52     //设置循环链表的长度即
 53     public void setLength(int len)
 54     {
 55         this.len = len;
 56     }
 57     
 58     //1.创建孩子3.连成环状
 59     public void creatLink()
 60     {
 61         for(i=1; i<=len; i++)
 62         {
 63             if(i==1)//第一个孩子
 64             {
 65                 Kid ch = new Kid(i);//创建第一个孩子 ch为第一个孩子的引用
 66                 firstKid = ch;//firstKid指向第一个孩子！
 67                 temp = ch;//跑龙套temp也指向当前孩子！
 68             }
 69             else
 70             {
 71                 if(i == len)//最后一个孩子
 72                 {
 73                     Kid ch = new Kid(i);//创建最后一个孩子
 74                     temp.nextKid = ch;
 75                     temp = ch;
 76                     temp.nextKid = firstKid;
 77                 }
 78                 else
 79                 {
 80                     Kid ch = new Kid(i);//创建剩余的孩子
 81                     temp.nextKid = ch;//跑龙套（孩子的引用）的下一个孩子（相当于next指针）指向当前 孩子！
 82                     temp = ch;//跑龙套指向新的当前孩子！
 83                 }                                                                  
 84             }
 85         }
 86     }
 87     //打印孩子编号即围成的圈
 88     public void show()
 89     {
 90         temp = firstKid;
 91         do{
 92             System.out.print(temp.no+" ");
 93             temp = temp.nextKid;
 94         }while(temp!= firstKid);//理解do while的好处
 95     }
 96     
 97     //设置m的值
 98     public void setM(int m)
 99     {
100         this.m = m;
101     }
102     //设置n的值
103     public void setK(int k)
104     {
105         this.k = k;
106     }
107     //开始玩游戏
108     public void play()
109     {
110         temp = firstKid;
111         //1.先找到数数的那个人m  
112         for(i=1; i<m; i++)//易错！不是"等于"
113         {
114             temp = temp.nextKid;
115         }
116         while(len!=1){
117             System.out.print(" m的值为"+temp.no);
118             //2.数n下找到出圈的人即temp
119             for(i=1; i<k; i++)//易错！不是"等于"
120             {
121                 temp = temp.nextKid;
122             }
123             //3.temp退圈
124             //先找到temp的前一个人即temp2
125             Kid temp2;
126             temp2 =temp;
127             while(temp2.nextKid != temp)
128             {
129                 temp2 = temp2.nextKid;
130             }
131             temp2.nextKid = temp.nextKid; //删除语句 如第二人指向第四个人
132             System.out.print(" 出圈人"+temp.no);
133             temp = temp.nextKid;//开始数数的人temp指向被删的下一个
134             
135             len--;//每次少一个人
136         }
137         System.out.println(" 最后出圈的是"+temp.no);
138     }
139 }