[白俊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;
}
Reference
この問題について([白俊C+]1866ジョセフス問題), 我々は、より多くの情報をここで見つけました https://velog.io/@cldhfleks2/11866テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol