问题描述:
已知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,但他们代表的意思是不相同的。