[200]158号ジョセフス問題
7380 ワード
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)
しゅつりょく
例に示すように、ジョセフスシーケンスを出力します.
コピー例入力1
7 3
コピー例出力1
<3, 6, 2, 7, 5, 1, 4>
コード#コード#
//---- 세팅 ----//
const fs = require('fs');
const stdin = (
process.platform === 'linux'
? fs.readFileSync('/dev/stdin').toString()
: `\
7 3
`
).split('\n');
const input = (() => {
let line = 0;
return () => stdin[line++];
})();
//---- 풀이 -----//
const [n, k] = input().split(' ').map(Number);
const arr = [...Array(n)].map((v, i) => i + 1);
const res = [];
while (arr.length) {
[...Array(k)].forEach(() => {
arr.push(arr.shift());
})
res.push(arr.pop());
}
console.log('<' + res.join(', ') + '>');
に答える
arr
が空になるまで、ジョセフスk次変換を推進します.k回終了後、最後の要素がターゲット要素であるため、popは
res
配列に押される.Reference
この問題について([200]158号ジョセフス問題), 我々は、より多くの情報をここで見つけました https://velog.io/@younoah/boj-1158テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol