首页 > 专题系列 > Java解POJ > POJ 3750 小孩报数问题 [解题报告] Java
2013
11-13

POJ 3750 小孩报数问题 [解题报告] Java

小孩报数问题

问题描述 :

有N个小孩围成一圈,给他们从1开始依次编号,现指定从第W个开始报数,报到第S个时,该小孩出列,然后从下一个小孩开始报数,仍是报到S个出列,如此重复下去,直到所有的小孩都出列(总人数不足S个时将循环报数),求小孩出列的顺序。

输入:

第一行输入小孩的人数N(N<=64)

接下来每行输入一个小孩的名字(人名不超过15个字符)

最后一行输入W,S (W < N),用逗号","间隔

输出:

按人名输出小孩按顺序出列的顺序,每行输出一个人名

样例输入:

5
Xiaoming
Xiaohua
Xiaowang
Zhangsan
Lisi
2,3

样例输出:

Zhangsan
Xiaohua
Xiaoming
Xiaowang
Lisi

解题代码:

import java.io.BufferedInputStream;   
import java.util.LinkedList;   
import java.util.Scanner;   
  
/*  
 * To change this template, choose Tools | Templates  
 * and open the template in the editor.  
 */  
/**  
 *Poj3750 easy 约瑟夫循环  
 * @author NC  
 */  
public class Main {   
  
    public static void main(String[] args) {   
        Scanner scanner = new Scanner(new BufferedInputStream(System.in));   
        //用nextInt的话,与下文的nextLine会有点冲突,会报异常,还是统一用一个方法就好   
        int n = Integer.parseInt(scanner.nextLine());   
        LinkedList queue = new LinkedList();   
        for (int i = 0; i < n; i++) {   
            String name = scanner.nextLine();   
            queue.add(name.trim());   
        }   
        String ws = scanner.nextLine();   
        String[] wss = ws.split(",");   
        int w = Integer.parseInt(wss[0]);   
        int s = Integer.parseInt(wss[1]);   
        int count = 0;   
//找出第w个人,从第w个人开始报数   
        while (true) {   
            count++;   
            if (count == n + 1) {   
                count = 1;   
            }   
            if (count == w) {   
                break;   
            }   
            String person = queue.removeFirst();   
            queue.add(person);   
  
        }   
//从第w个开始报数,报到s的出队   
        count = 0;   
        while (true) {   
            //从1开始报数   
            count++;   
            if (count == n + 1) {   
                count = 1;   
            }   
            if (queue.isEmpty()) {   
                break;   
            }   
            //出来一个人报数   
            String person = queue.removeFirst();   
            if (count == s) {   
                System.out.println(person);   
                count = 0;//出完队后,重新报数   
            } else {   
                queue.add(person);   
            }   
  
        }   
    }   
}

  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮