首页 > ACM题库 > 九度OJ > 九度-1188-约瑟夫环[解题代码]
2013
12-13

九度-1188-约瑟夫环[解题代码]

题目来源:2003-2005年华中科技大学计算机研究生机试真题

题目描述:

    N个人围成一圈顺序编号,从1号开始按1、2、3……顺序报数,报p者退出圈外,其余的人再从1、2、3开始报数,报p的人再退出圈外,以此类推。
    请按退出顺序输出每个退出人的原序号。

输入:

包括一个整数N(1<=N<=3000)及一个整数p。

输出:

测试数据可能有多组,对于每一组数据,
按退出顺序输出每个退出人的原序号。

样例输入:
7 3
样例输出:
3 6 2 7 5 1 4

java 代码如下:
import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.PrintWriter;
import java.util.Scanner;

public class Main{
	static int n;
	static int p;
	static int arr[];
	static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
	public static void main(String[] args) {
		Scanner s = new Scanner(new BufferedInputStream(System.in));
		while (s.hasNextInt()) {
			n = s.nextInt();
			p = s.nextInt();
			arr = new int[n];
			int start = 0;
			for(int i=0; i<n; i++){
				int count = 0;
				for(int j=start; j<n; j=(j+1)%n){
					if(arr[j] == 0)
						count ++;
					if(count == p){
						if(i!=0)
							out.print(" "+(j+1));
						else
							out.print((j+1));
						start = (j+1)%n;
						arr[j] = 1;
						break;
					}
				}
			}
			out.println();
			out.flush();
		}

	}



}
/**************************************************************
	Problem: 1188
	User: coder
	Language: Java
	Result: Accepted
	Time:1190 ms
	Memory:37896 kb
****************************************************************/


  1. 代码是给出了,但是解析的也太不清晰了吧!如 13 abejkcfghid jkebfghicda
    第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3),为什么要这样拆分,原则是什么?