요세푸스 문제 계산기

점화식 J(1) = 0, J(m) = (J(m−1) + k) mod m으로 구하고 답은 J(n)에 1을 더한 값입니다. 한 명이 빠지고 나면 남은 사람들로 이루어진 「크기가 하나 작은 같은 문제」가 되고 세기 시작하는 자리만 k칸 옮겨 가기 때문입니다. 이 방법은 덧셈 n번이면 끝나므로 실제로 한 명씩 지워 볼 필요가 없습니다.

4번이 남습니다. 빠지는 순서는 3, 6, 2, 7, 5, 1입니다. 3번이 먼저 빠지고 그다음 4번부터 다시 세어 6번이 빠지는 식으로 이어집니다.

있습니다. n을 2의 거듭제곱과 나머지로 n = 2^m + l(0 ≤ l < 2^m)처럼 쪼개면 살아남는 자리가 2l + 1입니다. 다르게 말하면 n을 2진법으로 적고 맨 앞의 1을 떼어 맨 뒤에 붙인 수입니다. 예를 들어 13은 1101이므로 1011 = 11번이 남습니다. n이 2의 거듭제곱이면 나머지가 0이라 언제나 1번이 남습니다.

세는 규약이 달라서일 가능성이 큽니다. 이 계산기는 사람 번호를 1부터 세고 1번 사람부터 세기 시작합니다. 0부터 세는 자료와는 답이 1만큼 다르고, 「k번째」를 「k명 건너뛴 다음 사람」으로 읽는 자료와는 k가 1만큼 다릅니다. 규약을 맞추면 대개 같은 답이 됩니다.

술래를 정하는 놀이나 순번을 돌리는 규칙이 모두 같은 구조입니다. 계산 쪽에서는 「원형 자료에서 일정 간격으로 지워 나갈 때 남는 것」을 다루는 연습 문제로 자주 나오며, 원형 연결 리스트나 큐를 다루는 예제로도 쓰입니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.