100人报数，数到3退出游戏

不念不忘少年蓝@ 2022-11-06 12:53 127阅读 0赞

## 题目信息 ##

有n个人围成一圈，顺序排号。从第一个人开始报数（从1到3报数），凡报到3的人退出圈子，问最后留下的是原来第几号的那位。

## 题解 ##

这个题目比较经典，也被成为约瑟夫环问题，有兴趣的朋友可以去搜搜约瑟夫环。

做一个简单的示例，取10个人来报数，然后退出

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hZ2kxMjAx_size_16_color_FFFFFF_t_70][] 数组位置对照10人报出退出问题

从上面的示例，可以看出：

1.  定义初始数组，数组位置初始值为0
2.  报数器只在值为0的位置报数
3.  报数器报到3时，修改位置值为1，剩余人数减1
4.  循环报数，在剩余人数为1时退出
5.  数组循环至末尾时，数组位置置0
6.  如果循环到的位置值不为0，位置加1后移
7.  循环退出时，打印数组，输出值为0的位置

## 编码 ##

### 数组实现 ###

根据上面的题解分析，利用数组来实现该算法

/**
    	 * 报数退出
    	 * @param m 总人数
    	 * @param n 报到n时退出
    	 */
    	public static void reportNumber(int m, int n) {
    		// 初始化数组长度为m,初始化报数器speaker为0
    		int[] arr = new int[m];
    		int speaker = 0;
    		
    		// 初始化剩余人数left为m,数组元素位置arrLocation为0
    		int left = m;
    		int arrLocation = 0;
    		
    		// 循环数组，报数，剩余人数为1时退出
    		while (left > 1) {
    			if (arr[arrLocation] == 0) {
    				// 数组位置为0时，报数
    				speaker++;
    				
    				// 报到n时，报数器speaker置0
    				// 数组位置值修改为1，剩余人数left减1
    				if (speaker == n) {
    					speaker = 0;
    					arr[arrLocation] = 1;
    					left--;
    				}
    				
    				// 完成当次报数后，位置加1
    				// 若数组位置值为数组长度时，说明到了数组末尾，将位置置0，开启新一轮的循环
    				arrLocation++;
    				if (arrLocation == m) {
    					arrLocation = 0;
    				}
    			} else {
    				// 数组位置不为0时，直接移动位置；
    				// 若数组位置值为数组长度时，说明到了数组末尾，将位置置0，开启新一轮的循环
    				arrLocation++;
    				if (arrLocation == m) {
    					arrLocation = 0;
    				}
    			}
    		}
    		
    		for (int i=0; i<arr.length; i++) {
    			if (arr[i] == 0) {
    				System.out.println(i+1);
    			}
    		}
    	}

上面实现的是剩余最后一个人，若题目稍作修改，将剩余1人修改为人数小于n，则将while条件中 left > 1修改为left > n即可。

### list实现 ###

list实现方式与数组类似，略有不同，如下

/**
    	 * 报数退出
    	 * @param m 总人数
    	 * @param n 报到n时退出
    	 */
    	public static void reportNumberList(int m, int n) {
    		// 初始化list，list置每个位置初始值
    		List<Integer> list = new ArrayList<>();
    		for (int i=0; i<m; i++) {
    			list.add(i+1);
    		}
    		
    		// 初始化报数器speaker为0
    		int speaker = 0;
    		
    		// 初始化list元素位置arrLocation为0
    		int arrLocation = 0;
    		
    		// 循环list，报数，剩余1个人时退出
    		while (list.size() > 1) {
    			// 报数
    			// 同数组实现不同，list中将报到为n的位置直接删除了
    			speaker++;
    			
    			// 报到n时，报数器speaker置0
    			// 删除list该位置的元素
    			if (speaker == n) {
    				speaker = 0;
    				list.remove(arrLocation);
    				
    				// 若数组位置值为list长度，说明到了list末尾，将位置置0，开启一次新的循环
    				if (arrLocation == list.size()) {
    					arrLocation = 0;
    				}
    			} else {
    				// 完成当次报数后，位置加1
    				// 若数组位置值为list长度，说明到了list末尾，将位置置0，开启一次新的循环
    				arrLocation++;
    				if (arrLocation == list.size()) {
    					arrLocation = 0;
    				}
    			}
    		}
    		
    		System.out.println(list.get(0));
    	}

### 代码测试 ###

public static void main(String[] args) {
    		reportNumber(10, 3);
    		reportNumberList(10, 3);
    		
    		reportNumber(100, 3);
    		reportNumberList(100, 3);
    	}

4  
4  
91  
91

测试发现，10个人时，最后剩余人位置为4，与题解分析相同；100人时，最后剩余人位置为91

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hZ2kxMjAx_size_16_color_FFFFFF_t_70]: /images/20221023/0287588ccb5841b89002a9b89b857a1c.png