[白俊C+]1866ジョセフス問題

質問する

ジョセフス問題は以下の通りです.
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 ≤ 1,000)

しゅつりょく

例に示すように、ジョセフスシーケンスを出力します.
https://www.acmicpc.net/problem/11866

に答える

頻繁にデータを追加および削除する場合は、配列やベクトルではなく、キューまたはスタック構造を使用することが望ましい.しかしここの問題は毎回N,N−1,N−2...1番からK番を抽出して出力する問題なので、方向は固定されており、キュー1、2、…K-1番popとpushの後
K番目はpop出力だけでいいです.
次はソースコードです.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
using namespace std;

int main(void) {
	queue<int> q, res; //큐 선언
	int N, K;
	scanf("%d%d", &N, &K);
	int test = N;
	for (int i = 1; i <= N; i++) { //큐에 다넣음
		q.push(i);
	}
	while (test--) {
		int loop = K-1;
		while (loop--) {
			int temp = q.front();
			q.pop();
			q.push(temp);
		}
		int temp = q.front();
		q.pop();
		res.push(temp);
	}
	// 출력
	printf("<");
	for (int i = 0; i < N - 1; i++) {
		printf("%d, ", res.front());
		res.pop();
	}
	printf("%d>", res.front());

	return 0;
}