约瑟夫环描述:约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编號1,23…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数数到的那个人出列;他的下一个人又从1开始报数,数到的那个人又出列;依此规律重复下去直到圆桌周围的人全部出列。
约瑟夫环问题输入人数n,第个人出列最后一个人的编号是多少?
1.先把这n个人按順序加进LinkedList选择链表是因为链表在进行大量数据插入删除的时候会比顺序表ArrayList的效率要高,而ArrayList在查找的时候效率会相对高
2.从索引0开始报数,到索引-1的时候也就是第个人出列。
3.排在这个人后面的人都向前移了一位也就是如4的索引原来是3的,在3出列之后队伍里还有[1,2,4,5]四个人,这时候4的索引变成了3-1=25的索引变成了4-1=3。所以新的索引就要从出列的人重新开始数再次数到-1。再次执行上面的删除操作
4.我们还会发现┅个问题,就是index一直加的话岂不是会数组越界了?这时候该怎么办呢怎么样才能让一个链表排出一个圈的效果呢?
我们可以用 索引 % 链表长度 进行取余操作
5.最后我们总结一下。需要初始化的索引与循环体内的代码如下: