约瑟夫环

特点

单向循环链表

描述

N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3。
分析：
（1）由于对于每个人只有死和活两种状态，因此可以用布尔型数组标记每个人的状态，可用true表示死，false表示活。
（2）开始时每个人都是活的，所以数组初值全部赋为false。
（3）模拟杀人过程，直到所有人都被杀死为止。

代码实现

  1. /**
  2.  * @author laoduan
  3.  * @create 2020-04-09-22:27
  4.  */
  5. public class josepfu {
  6.     public static void main(String[] args) {
  9.         CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
  10.         circleSingleLinkedList.addBoy(25);
  11. //        circleSingleLinkedList.showboy();
  12.         circleSingleLinkedList.josepfu(1, 2, 25);
  13.     }
  14. }
  17. //创建一个环形的单向列表
  18. class CircleSingleLinkedList {
  19.     private Boy first = null;
  21.     //添加小孩节点，组成环形链表
  22.     public void addBoy(int nums) {
  23.         if (nums < 1) {
  24.             System.out.println("nums的值不正确");
  25.             return;
  26.         }
  27.         Boy curBoy = null;
  28.         //用for来创建环形链表
  29.         for (int i = 1; i <= nums; i++) {
  30.             Boy boy = new Boy(i);
  31.             //如果是第一个小孩
  32.             if (i == 1) {
  33.                 first = boy;
  34.                 first.setNext(first);
  35.                 curBoy = first;//让curBoy指向第一个小孩
  36.             } else {
  37.                 curBoy.setNext(boy);
  38.                 boy.setNext(first);
  39.                 curBoy = boy;
  40.             }
  41.         }
  42.     }
  44.     //遍历当前环形链表
  45.     public void showboy(){
  46.         if(first==null){
  47.             System.out.println("没有小孩");
  48.             return;
  49.         }
  50.         //first不能动，要用辅助指针
  51.         Boy curBoy =first;
  52.         while (true){
  53.             System.out.printf("当前小孩的编号%d\n",curBoy.getNo());
  54.             if(curBoy.getNext()==first){
  55.                 //说明循环完毕
  56.                 break;
  57.             }else {
  58.                 curBoy=curBoy.getNext();
  59.             }
  60.         }
  61.     }
  62.     //约瑟夫
  63.     public void josepfu(int startNo,int n,int nums){
  64.         if (first==null||startNo<1||startNo>nums){
  65.             System.out.println("参数有误");
  66.             return;
  67.         }
  68.         Boy helper = first;
  69.         while (true){
  70.             if(helper.getNext()==first){
  71.                 break;
  72.             }
  73.             helper=helper.getNext();
  74.         }
  75.         for(int j=0;j<startNo-1;j++){
  76.             first=first.getNext();
  77.             helper=helper.getNext();
  78.         }
  80.         while (true){
  81.             if(helper==first){
  82.                 break;
  83.             }
  84.             for (int x=0;x<n-1;x++){
  85.                 first=first.getNext();
  86.                 helper=helper.getNext();
  87.             }
  88.             System.out.printf("出圈的小孩编号为%d\n",first.getNo());
  89.             first=first.getNext();
  90.             helper.setNext(first);
  91.         }
  92.         System.out.printf("最后剩下的小孩是%d\n",first.getNo());
  93.     }
  94. }
  97. //创建一个boy类，表示一个结点
  98. class Boy {
  99.     public int getNo() {
  100.         return no;
  101.     }
  103.     public void setNo(int no) {
  104.         this.no = no;
  105.     }
  107.     public Boy getNext() {
  108.         return next;
  109.     }
  111.     public void setNext(Boy next) {
  112.         this.next = next;
  113.     }
  114.     public Boy (int no ){
  115.         this.no = no;
  116.     }
  117.     private int no;
  118.     private Boy next;
  120. }