约瑟夫环问题较简单的解决办法

问题描述:

已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。

代码:

整体思路:用一个ArrayList来存储编号的元素,用一个int array[]数组来存储移除元素的编号,下面的代码多数是变量的定义以及代码的规则,主要代码为:

while(list.size()>0) {
    rmIndex=(rmIndex+m-1)%list.size();//对于第一次因为开始位置就要编号所以-1 
    //后面的因为每循环一次list的大小就减一,而rmIndex是根据移除元素之前得到的,为了适应这种情况就需要减一
    array[index++]=list.get(rmIndex);//存储移除的编号;
    list.remove(rmIndex);
  }

//整个代码如下

import java.util.ArrayList;
import java.util.List;

public class YSF {
/*
* count :元素的数目
* start:开始报数的位置(与数组下标不对应,是从1开始的)
* m:间隔,即从1开始报数,需要报数到的号数
* */
public static int[] ysf(int count,int start,int m) {
  List<Integer> list=new ArrayList<>();
  int array[]=new int[count];//按顺序存储移除元素的编号
  for(int i=0;i<count;i++) {//编号
    list.add(i+1);
  }
  int index=0;//array的数组指针
  int rmIndex=start-1;//编号与下标的不对应所以-1,
  while(list.size()>0) {
    rmIndex=(rmIndex+m-1)%list.size();//对于第一次因为开始位置就要编号所以-1
    //后面的因为每循环一次list的大小就减一,而rmIndex是根据移除元素之前得到的,为了适应这种情况就需要减一
    array[index++]=list.get(rmIndex);//存储移除的编号;
    list.remove(rmIndex);
  }
  return array;
}

public static void main(String[] args) {
  int array[]=ysf(10,2,3);
  for(int i:array) {
    System.out.print(i+" ");
  }
 }

}

对于ArrayList的一些说明:当使用remove()方法后集合的大小会减一,并且会将移除元素的后面的元素往前移动(这是符合数组的删除规则的)

整个程序的重点在于理解一句程序:rmIndex=(rmIndex+m-1)%list.size();上面有一些说明,下面我们再以一个例子的方式来说明

一共有四个元素,从第二个元素开始报数,报数到3的元素移除。

第一次报数时因为第二个元素就需要报数了,所以报数到3的元素应该是第二个元素往后的第(3-1)个元素

而除了第一次以外的报数,他们得到的rmIndex是上一次移除元素的位置,开始报数是从rmIndex的下一个位置开始的,所以报数到3的 元素是rmIndex往后的第3个元素,但是需要注意的是上一次移除元素后list的大小减小了1,需要前面的规则也能用到这次上面就需要下标减1。

所以第一次报数和后面的报数都需要减1,但他们代表的意思是不相同的。

心有多大,天有多高,一起奋斗!!
原文地址:https://www.cnblogs.com/zhaolei1996/p/10972180.html