我是白骏1158号。

ジョセフス問題

質問する

ジョセフス問題は以下の通りです.
1番からN番までは、N人が1つの円に座り、正の整数K(≦N)を与えます.今は順番にK人目を除いています.一人が取り除かれると、残りの人からなる円に沿ってこの過程が続きます.この過程はN人全員がクリアされるまで続く.円上の人々が消去される順序を(N,K)−ジョセフス配列と呼ぶ.例えば、(7,3)−ジョセフス配列<3,6,2,7,5,1,4>である.
NとKをあげると(N,K)-ジョセフスシーケンスを求めるプログラムを書きます.

入力

第1行NとKは、スペースを隔てて順次与えられる.(1 ≤ K ≤ N ≤ 5,000)

しゅつりょく

例に示すように、ジョセフスシーケンスを出力します.

例

コード#コード#

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		sb.append('<');
		
		Queue<Integer> queue = new LinkedList<>();
		
		int N = sc.nextInt();
		int K = sc.nextInt();
		sc.close();
		
		for(int i=1; i<=N; i++)
			queue.add(i);
		
		while(queue.size() > 1) {
			for(int i=1; i<K; i++) {
				int value = queue.poll();
				queue.offer(value);
			}
			
			sb.append(queue.poll()).append(", ");
		}
		
		sb.append(queue.poll()).append('>');
		
		System.out.println(sb);
	}
}

に答える

Queueを用いて問題を解決した.
1からNまでoffer()を用いてキューを挿入する.
最初の数からKまでの前の数はpoll()で、その後、キューの最後のoffer()に並びます.その後、Kに対してpoll()を行い、その値をStringBuilderに格納する.
このプロシージャは、queueの内部が呼び出されるまでwhileによって文を繰り返します.