淘宝面试题 n个人围成一圈,报到m的人出列 面试数据结构
程序员文章站
2024-02-24 00:00:22
...
有N个人围成一圈,第一个人从1开始报数,报到M的人出列,求最后一个出列的人。
这是一个约瑟夫环问题,下面给出了java实现的例子:
全文请访问:人人编程
这是一个约瑟夫环问题,下面给出了java实现的例子:
package com.juziku; import java.util.Arrays; /** * n个人围成一圈,报到m的人出列 * @author sunlightcs * 2011-3-8 * http://hi.juziku.com/sunlightcs/ */ public class Queue { public static void main(String[] args) { queue(10, 3); } /** * 最后出队的人 * @param total 总的人数 * @param num 第几号出队 */ public static void queue(int total, int num){ //定义一个数组,true表示没有出队列的,false表示已经出队列的 boolean []arr = new boolean[total]; Arrays.fill(arr, true); //移动变量,如:1 2 3 1 2 3 1 2 int next = 1; //数组下标 int index = 0; //剩下的人数 int count = total; //如果剩下的人数为1人时,停止报数 while(count>1){ if(arr[index] == true){ if(next == 3){ arr[index] = false; //剩下的人数减1 --count; //移动变量复位,从1开始报数 next = 1; System.out.println("依次出列的人为:"+(index+1)); }else{ ++next; } } ++index; if(index == total){ //数组下标复位,从0开始新重遍历 index = 0; } } for(int i=0; i<total; i++){ if(arr[i] == true){ System.out.println("最后出列的人为:"+(i+1)); } } } }
全文请访问:人人编程