JavaScript에서 Josephus 순열을 효율적으로 계산하기

이 문제는 틀림없이 고대 역사가 요세푸스의 생애에서 가장 중요한 사건에 의해 이름이 지어졌습니다. 그의 이야기에 따르면 그와 그의 40명의 병사는 로마군에 의해 동굴에 갇혔습니다. 포위 공격.

적에게 항복하기를 거부하고 대신 그들은 반전을 지닌 집단 자살을 선택했습니다. 그들은 원을 형성하고 마지막 한 사람이 남을 때까지 세 명 중 한 명씩을 계속 살해했습니다. ).

요세푸스와 다른 남자가 마지막 두 사람이었고 이제 우리가 이야기의 모든 세부 사항을 알고 있으므로 원래 아이디어를 정확히 따르지 않았다고 올바르게 추측했을 수 있습니다.

Josephus 순열을 반환하는 JavaScript 함수를 작성해야 합니다.

매개변수로 순열될 항목의 초기 배열/목록을 마치 원 안에 있는 것처럼 사용하고 아무것도 남지 않을 때까지 k 자리마다 계산합니다.

예를 들어, n=7 및 k=3일 때 josephus(7,3)는 이런 식으로 작동해야 합니다.

[1,2,3,4,5,6,7] − initial sequence
[1,2,4,5,6,7] => 3 is counted out and goes into the result [3]
[1,2,4,5,7] => 6 is counted out and goes into the result [3,6]
[1,4,5,7] => 2 is counted out and goes into the result [3,6,2]
[1,4,5] => 7 is counted out and goes into the result [3,6,2,7]
[1,4] => 5 is counted out and goes into the result [3,6,2,7,5]
[4] => 1 is counted out and goes into the result [3,6,2,7,5,1]
[] => 4 is counted out and goes into the result [3,6,2,7,5,1,4]

따라서 최종 결과는 -

josephus([1,2,3,4,5,6,7],3)==[3,6,2,7,5,1,4];

예시

이에 대한 코드는 -

const arr = [1, 2, 3, 4, 5, 6, 7];
const num = 3;
const helper = (n, k, i, map) => {
   if (map.hasOwnProperty([n, k, i]))
   return map[[n, k, i]];
   if (i === 1)
   return map[[n, k, i]] = (k − 1) % n;
   return map[[n, k, i]] =
   (k + helper(n − 1, k, i − 1, map)) % n;
}
const josephus = (arr, k) => {
   let n = arr.length;
   let result = new Array(n);
   let map = {};
   for (let i=1; i<=n; i++)
   result[i − 1] = arr[ helper(n, k, i, map) ];
   return result;
};
console.log(josephus(arr, num));

출력

콘솔의 출력은 -

[
   3, 6, 2, 7,
   5, 1, 4
]