202052 - 序号4- （4399-2020年）

约瑟夫环（java实现）

题目描述：

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

输入描述：

一行，一个正整数n（1<=n<=1000000）。

输出描述：

输出答案。

示例1：

输入

5

输出

4

说明

出局的编号依次为3,1,5,2，最后留下的是4

备注:

编号从1开始。

问题分析：

约瑟夫环.
可以使用队列来实现，计数到3的时候删除该元素并计数清零，否则加到队列末尾。

相关知识：

略

参考代码：

思路一实现：

import java.util.*;
public class Main {

    public static void main(String[] args)
    {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        //Queue<Integer> qu = new Queue<>();
        Queue<Integer> qu = new LinkedList<Integer>();
        for (int i=1; i<=n; i++)
        {
            qu.add(i);
        }
        int count = 0;
        while(1 != qu.size())
        {
            while (count < 2)//if (count < 3)
            {
                qu.add(qu.element());
                qu.remove();
                count++;
            }
            count = 0;
            qu.remove();
        }
        System.out.println(qu.element());
    }
}