博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
约瑟夫环问题较简单的解决办法
阅读量:5061 次
发布时间:2019-06-12

本文共 1660 字,大约阅读时间需要 5 分钟。

问题描述:

已知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

你可能感兴趣的文章
Range和xrange的区别
查看>>
STL容器之vector
查看>>
无法向会话状态服务器发出会话状态请求
查看>>
数据中心虚拟化技术
查看>>
01入门
查看>>
复习文件操作
查看>>
C#Hashtable与Dictionary性能
查看>>
10个让你忘记 Flash 的 HTML5 应用演示
查看>>
SQL Server 使用作业设置定时任务之一(转载)
查看>>
Primary definition
查看>>
第二阶段冲刺-01
查看>>
BZOJ1045 HAOI2008 糖果传递
查看>>
发送请求时params和data的区别
查看>>
JavaScript 克隆数组
查看>>
eggs
查看>>
一步步学习微软InfoPath2010和SP2010--第七章节--从SP列表和业务数据连接接收数据(4)--外部项目选取器和业务数据连接...
查看>>
如何增强你的SharePoint 团队网站首页
查看>>
FZU 1914 Funny Positive Sequence(线性算法)
查看>>
oracle 报错ORA-12514: TNS:listener does not currently know of service requested in connec
查看>>
基于grunt构建的前端集成开发环境
查看>>