面试题约瑟夫: n个人围成一圈,报到m的人出列

2016-10-11  本文已影响0人  A_Coder

有N个人围成一圈,第一个人从1开始报数,报到M的人出列,求最后一个出列的人。
java实现的:

import java.util.Arrays;

public class Test {
    public static void main(String[] args) {
        queue(10, 3);
    }

    private static void queue(int total, int num) {
        // TODO Auto-generated method stub
        //定义一个数组,true表示没有出列的,false表示已经出队列的
        boolean []arr = new boolean[total];
        Arrays.fill(arr, true);
        
        //移动变量,如1 2 3
        int next= 0;
        
        //数组下标
        int index = 0;
        
        //剩下的人数
        int remain = total;
        
        //如果剩下的人为1时,停止报数
        while(remain > 1) {
            for(index = 0; index < total; index++){
            if (arr[index] == true) {
                next++; //自增到规定的出列数num
                if(next == num ) {
                    arr[index] = false;
                    remain--;
                    System.out.println("依次出列的人数为:" + (index + 1));
                    next = 0; //当数到规定的数是,从0开始数
                } 
            }
        }
        }
        for (int i = 0; i < total; i++){
            if (arr[i] == true) {
                System.out.println("最后剩下的人是:"  + (i + 1));
                break;
            }
        }
    
        
    }
}
上一篇 下一篇

猜你喜欢

热点阅读