요셉푸스 문제

컴퓨터 과학과 수학에서 요셉푸스 문제(또는 요셉푸스 순열)는 어떤 계산 게임과 관련된 이론적인 문제다.

500명이 요셉푸스 문제 시퀀스를 그린 그림으로, 6명은 생략한다. 가로축은 사람의 숫자다. 수직축(위부터 아래까지)은 시간(사이클 수)이다. 살아있는 사람은 초록색으로, 죽은 사람은 검은색으로 그려진다.^[1]

사람들이 원형으로 서서 처형되기를 기다리고 있다. 카운트는 원의 지정된 지점에서 시작하여 지정된 방향으로 원을 중심으로 진행한다. 지정된 수의 사람을 건너뛰고 나면 다음 사람이 처형된다. 다음 사람부터 시작해서 한 사람만 남을 때까지 같은 방향으로 가서 같은 수의 사람을 건너뛰고, 그 절차는 반복되어 자유로워진다.

문제는 인원, 시작점, 방향, 건너뛸 수 있는 숫자로 볼 때, 실행을 피하기 위해 초기 원의 위치를 선택하는 것이다.

역사

이 문제는 1세기에 살고 있는 유대인 역사학자 플라비우스 요셉푸스의 이름을 따서 명명되었다. 요셉푸스가 요드파트의 포위작전에 대해 설명한 바에 따르면 그와 그의 40명의 병사들은 로마 병사들에 의해 동굴에 갇혔다고 한다. 그들은 포획보다 자살을 택했고, 제비뽑기로 자살하는 연쇄적인 방법을 정착시켰다. 요셉푸스는 운에 의해 또는 어쩌면 신의 손에 의해, 자신과 다른 사람이 끝까지 남아 자살하기보다는 로마인들에게 항복했다고 말한다. 요셉푸스의 <유대인 전쟁> 제3권 제8장 제7부에 주어진 이야기는 다음과 같다.

그러나 이 극도의 괴로움 속에서 그는 평소의 총명함을 잃지 않고 하나님의 섭리를 믿고 [다음과 같은 방식으로] 목숨을 위험에 빠뜨렸다. 이제 너희가 죽는다는 것이 너희 가운데서 해결되었으니, 너희는 서로 죽는 것을 제비뽑기로 결정하자. 그 몫이 먼저 되는 사람은, 그 몫이 두 번째 몫인 그에게 죽임을 당하게 하여라. 그러면 그 행운이 우리 모두를 통해 그 진보를 이루게 될 것이다. 또 다른 몫이 없어졌을 때, 누군가가 뉘우치고 자신을 구원한다면, 우리 중 누구도 그 오른손으로 죽지는 않을 것이다.' 이 제안은 그들에게 매우 정당해 보였다; 그리고 그가 제비뽑기로 이 문제를 결정하려고 그들과 함께 이겼을 때, 그는 또한 스스로 제비뽑기 중 하나를 그렸다. 처음 제비를 뽑은 사람은, 장군이 바로 그들 가운데서 죽는다고 가정하여, 그 다음이 있는 자기 목을 드러누웠다. 그들은 요셉푸스가 죽더라도 목숨보다 더 달다고 생각하였기 때문이다. 그러나 요셉푸스가 우연히 그렇게 되었다고 말해야 할지, 아니면 신의 섭리에 의해 그렇게 되었다고 말해야 할지, 마지막 남은 것은 또 하나였다. 그리고 그는 제비뽑기에 의해 비난받지 않고, 마지막까지 남아 있었다면, 동포들의 피에 오른손을 담그고 싶었기 때문에, 그에게 충절을 믿고, 자기 자신처럼 잘 살도록 설득했다.
— Josephus n.d., p. 579, Wars of the Jews, Book III, Ch. 8, para 7

이 위업에 사용된 메커니즘의 세부 사항은 다소 모호하다. 제임스 다우디와 마이클 메이스에 따르면 1612년 클로드 가스파르 바첼트 드 메지락은 남성을 원을 그리며 세 개씩 세어 제거 순서를 결정하는 구체적인 메커니즘을 제안했다.^[2]^[3] 이 이야기는 종종 반복되어 왔고 구체적인 내용은 출처마다 상당히 다르다. 예를 들어, 이스라엘 나단 헤르슈타인과 어빙 카플란스키(1974년)는 요셉푸스와 39명의 전우들이 일곱 번째 사람이 탈락할 때마다 원을 그리며 서게 한다.^[4] 문제의 이력은 피보나치 분기 편집자에게 보내는 S. L. 자벨의 서신에서 찾을 수 있다.^[5]

요셉푸스는 공범자가 있었다; 문제는 그때 마지막으로 남은 두 생존자의 장소를 찾는 것이었다. 자신과 상대 남성을 각각 31위와 16위( $아래$ k=3의 경우)에 앉혔다는 주장이 있다.^[6]

변형 및 일반화

중세판 요셉푸스 문제는 폭풍우 속에서 15명의 터키인과 15명의 기독교인이 배에 타고 있는데, 승객의 절반이 배 밖으로 던져지지 않으면 침몰할 것이다. 30명 모두가 원을 그리며 서 있고, 아홉 명마다 바다에 던져진다. 기독교인들은 터키인들만 던질 수 있도록 어디에 서야 할지 결정할 필요가 있다.^[7] 다른 버전에서는 터키인과 기독교인의 역할이 상호 교환된다.

Graham, Knuth & Patashnik 1989, 페이지 8은 "표준" 변종을 설명하고 연구한다. 출발할 사람이 $n명인지$ , 2인자( $아래$ k = 2)가 모두 탈락하는지 마지막 생존자가 어디에 서 있는지 결정한다.

이 문제의 일반화는 다음과 같다. 모든 m번째 사람은 p번째 사람이 생존자인 n $크기$ 의 그룹에서 처형될 것으로 추정된다. 원에 $x명$ 이 추가되면 생존자는 $p$ + mx-th 위치에 있고, $이것$ 이 n + $x$ 보다 작거나 같으면 p + mx-th $위치$ 에 있다. $만약$ x가 ( $p$ + $mx)$ > ( $n$ + x) > (n + x $)$ 의 가장 작은 값이라면 생존자는 ( $p$ + $mx)$ - $(n$ + x) $위치$ 에 있다 $.$ ^[8]

해결책

다음에서 $n$ $n$ 은 $n$ (는) 초기 원의 인구 수를 $,$ k {\ $displaystyle$ k-1}은 $k-1$ $($ 는) 각 단계의 카운트를 나타내며 $k$ , $k-1$ $k$ $k-1$ - $k-1$ ${\displaystyle$ $k-1$ }은 $($ 는) 건너뛰고 k ${\displaystyle$ k} -th가 $k$ 실행된다. 원 안의 사람들은 $1$ $1$ 에서 $n$ $n$ 까지 $1$ 번호가 매겨지고 $n$ 시작 위치는 $1$ $1$ 이며 $1$ , 카운트는 포함이다.

k=2

문제는 모든 두 번째 사람이 살해될 때, $k=2$ k $k=2$ = $k=2$ ${\displaystyle k=2$ (더 일반적인 사례 $k\neq 2$ $k\neq 2$ 2 $k\neq 2$ 의 경우 $k\neq 2$ 아래에 해결 방법이 설명되어 있다.) 해결책은 반복적으로 표현된다. f $f(n)$ ( $f(n)$ ) ${\displaystyle f(n$ )}은 $($ 와 $)$ 초기에 사람이 $n명일$ 때 생존자의 위치를 나타낸다 $f(n)$ ( $k=2$ k = $k=2$ {\ $displaystyle k=2$ ). $k=2$ 처음으로 원을 돌면 짝수 사람들이 모두 죽는다. 두 번째로 원을 돌면 두 번째 사람이 죽고, 그 다음 네 번째 사람이 죽는다. 마치 원을 돌면 처음이 없었던 것과 같다.

초기 인원수가 짝수였다면, 두 번째 원 주위에서 x $위치$ 에 있는 사람은 $2x-1$ 2 $2x-1$ - $2x-1$ $2x-1$ 위치에 있었다( $2x-1$ x의 모든 $선택$ 에 대해). $n=2j$ = $n=2j$ $n=2j$ 을(를) 두십시오 $n=2j$ $f(j)$ ( $f(j)$ ) $f(j)$ 에서 생존할 $f(j)$ 사람은 원래 $2f(j)-1$ 2 $2f(j)-1$ ( $2f(j)-1$ ) - $2f(j)-1$ $2f(j)-1$ 에 있었다 $2f(j)-1$ 이렇게 하면 재발할 수 있다.

f(2j)=2f(j)-1\;.

만약 초기 사람의 수가 홀수였다면, 사람 1은 원을 중심으로 처음의 마지막에 죽는 것으로 생각할 수 있다. 다시, 원을 두 바퀴 도는 동안, 새로운 두 번째 사람이 죽고, 그 다음 네 번째 사람이 죽는다. 이 경우, 위치 $x$ 에 있는 사람은 원래 위치 $2x+1$ $2x+1$ + 1 $2x+1$ 에 있었다 $2x+1$ 이것은 재발을 낳는다.

f(2j+1)=2f(j)+1\;.

값이 $n$ 과 $f(n)$ ( $f(n)$ ) $f(n)$ 로 표에 표시되면 패턴이 $f(n)$ 나타난다(OEIS: A006257).

$n$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
$f(n)$	1	1	3	1	3	5	7	1	3	5	7	9	11	13	15	1

$f(n)$ 는 f $f(n)$ (n ) $f(n)$ 이(가) 지수 n이 2의 검정력일 때마다 $f(n)=1$ $f(n)=1$ ( $f(n)=1$ $f(n)=1$ = 1 ${\displaystyle f(n)=1$ 로 재시작되는 증가하는 홀수 시퀀스임을 $f(n)$ 시사한다. $0\leq l<2^{m}$ $n=2^{m}+l$ = $n=2^{m}+l$ + l ${\displaystyle n=2^{m}+l$ $0\leq l<2^{m}$ 0 $0\leq l<2^{m}$ l $0\leq l<2^{m}$ < $0\leq l<2^{m}$ ${\$ l $<2^{m}}},$ $f(n)=2\cdot l+1$ = $f(n)=2\cdot l+1$ $f(n)=2\cdot l+1$ + $f(n)=2\cdot l+1$ ${\displaysty f(n)=2\cdot$ l $1}.$ 표의 값이 이 방정식을 만족한다는 것은 분명하다. 또는 $사람$ 이 죽은 후 $2^{m}$ ${\$ 2 $^{m}$ 에 $2^{m}$ 불과하고 $2l+1$ + $2l+1$ $2l+1$ 인 것으로 $2l+1$ 생각할 수 있다. 이 사람이 생존자임이 틀림없다. $f(n)=2l+1$ f $f(n)=2l+1$ ( $f(n)=2l+1$ ) $f(n)=2l+1$ = $f(n)=2l+1$ $f(n)=2l+1$ + 1 ${\displaystyle f(n)=2l+1$ 아래에서는 유도에 의해 증거가 제시된다.

정리: $n=2^{m}+l$ = $f(n)=2l+1$ $n=2^{m}+l$ + $n=2^{m}+l$ $n=2^{m}+l$ 과 $n=2^{m}+l$ ( $0\leq l<2^{m}$ ) $0\leq l<2^{m}$ l $0\leq l<2^{m}$ < $f(n)=2l+1$ ${\$ $f(n)=2l+1$ ( $f(n)=2l+1$ ) $f(n)=2l+1$ = 2 $f(n)=2l+1$ + $f(n)=2l+1$ ${\displaystyle f(n)=2l+1$

증명: 강한 유도는 $n$ 에 사용된다. base case $n=1$ = $n=1$ ${\displaystyle n=1$ }은 $n=1$ $($ 는) 참이다. $이$ 경우는 n이 짝수일 때와 $n$ 이 홀수일 때 별도로 고려한다.

만약 n를 넘어서는 것과 n/2=2m1+나는 1{\displaystyle n/2=2^{m_{1}}+l_{1}}와 0≤ 나는 1<>2m1{\displaystyle 0\leq l_{1}<, 2^{m_{1}}}. 내가 1)는 a=l/2{\displaystyle l_{1}=l/2습니다, 그 다음}과 1m{\displaystyle m_{1}}}. f(나는 1{\displaystyle l_{1}을 선택합니다. nx) $f(n)=2f(n/2)-1=2((2l_{1})+1)-1=2l+1$ $f(n)=2f(n/2)-1=2((2l_{1})+1)-1=2l+1$ ( $f(n)=2f(n/2)-1=2((2l_{1})+1)-1=2l+1$ / $f(n)=2f(n/2)-1=2((2l_{1})+1)-1=2l+1$ ) $f(n)=2f(n/2)-1=2((2l_{1})+1)-1=2l+1$ - $f(n)=2f(n/2)-1=2((2l_{1})+1)-1=2l+1$ = 2 $f(n)=2f(n/2)-1=2((2l_{1})+1)-1=2l+1$ ( ( $f(n)=2f(n/2)-1=2((2l_{1})+1)-1=2l+1$ ( $f(n)=2f(n/2)-1=2((2l_{1})+1)-1=2l+1$ $f(n)=2f(n/2)-1=2((2l_{1})+1)-1=2l+1$ $f(n)=2f(n/2)-1=2((2l_{1})+1)-1=2l+1$ ) $f(n)=2f(n/2)-1=2((2l_{1})+1)-1=2l+1$ + $f(n)=2f(n/2)-1=2((2l_{1})+1)-1=2l+1$ ) $f(n)=2f(n/2)-1=2((2l_{1})+1)-1=2l+1$ - 1 $f(n)=2f(n/2)-1=2((2l_{1})+1)-1=2l+1$ = $f(n)=2f(n/2)-1=2((2l_{1})+1)-1=2l+1$ $f(n)=2f(n/2)-1=2((2l_{1})+1)-1=2l+1$ + 1 $(\displaystyle f(n)=2f(n/2$ )-1 $=2((2l_{1}+1$ )-1 $=1=2l+1$ }은 유도 가설에서 두 번째 동등성이 따르는 곳이다 $f(n)=2f(n/2)-1=2((2l_{1})+1)-1=2l+1$ .

만약 n은 이상한 후}과 m 1{\displaystyle m_{1}}나는 1{\displaystyle l_{1}을 선택하도록(n− 1)/2=2m1+나는 1{\displaystyle(n-1)/2=2^{m_{1}}+l_{1}}와 0≤ 나는 1<>2m1{\displaystyle 0\leq l_{1}<, 2^{m_{1}}}니다 내가 1)(나는 − 1)/2{\displaystyle l_{.1}=(l- $1)/2}$ . $f(n)=2f((n-1)/2)+1=2((2l_{1})+1)+1=2l+1$ ( $f(n)=2f((n-1)/2)+1=2((2l_{1})+1)+1=2l+1$ ) $f(n)=2f((n-1)/2)+1=2((2l_{1})+1)+1=2l+1$ = $f(n)=2f((n-1)/2)+1=2((2l_{1})+1)+1=2l+1$ $f(n)=2f((n-1)/2)+1=2((2l_{1})+1)+1=2l+1$ ( $f(n)=2f((n-1)/2)+1=2((2l_{1})+1)+1=2l+1$ ( $f(n)=2f((n-1)/2)+1=2((2l_{1})+1)+1=2l+1$ - $f(n)=2f((n-1)/2)+1=2((2l_{1})+1)+1=2l+1$ ) $f(n)=2f((n-1)/2)+1=2((2l_{1})+1)+1=2l+1$ / 2 $f(n)=2f((n-1)/2)+1=2((2l_{1})+1)+1=2l+1$ ) $f(n)=2f((n-1)/2)+1=2((2l_{1})+1)+1=2l+1$ + $f(n)=2f((n-1)/2)+1=2((2l_{1})+1)+1=2l+1$ = $f(n)=2f((n-1)/2)+1=2((2l_{1})+1)+1=2l+1$ ( $f(n)=2f((n-1)/2)+1=2((2l_{1})+1)+1=2l+1$ ( 2 $f(n)=2f((n-1)/2)+1=2((2l_{1})+1)+1=2l+1$ $f(n)=2f((n-1)/2)+1=2((2l_{1})+1)+1=2l+1$ ) $f(n)=2f((n-1)/2)+1=2((2l_{1})+1)+1=2l+1$ + $f(n)=2f((n-1)/2)+1=2((2l_{1})+1)+1=2l+1$ ) $f(n)=2f((n-1)/2)+1=2((2l_{1})+1)+1=2l+1$ + $f(n)=2f((n-1)/2)+1=2((2l_{1})+1)+1=2l+1$ = $f(n)=2f((n-1)/2)+1=2((2l_{1})+1)+1=2l+1$ $f(n)=2f((n-1)/2)+1=2((2l_{1})+1)+1=2l+1$ + 1 $(\$ $displaystyle f(n)=2f((n-1)=2)+1({1}+1)+1=2l+1}$ 은 유도 가설에서 두 번째 동등성이 뒤따르는 곳이다 $f(n)=2f((n-1)/2)+1=2((2l_{1})+1)+1=2l+1$ . 이것으로 증거가 완성되었다.

$f(n)$ ( $f(n)$ ) $f(n)$ 에 대한 명시적 식을 얻기 위해 해결할 수 있다 $f(n)$

f(n)=2(n-2^{\lfloor \log _{2}(n)\bloor }+1

답의 가장 우아한 형태는 n $크기$ n: $f(n)$ ( $){\displaystyle f(n)}$ 의 이진표현과 관련이 있다. $n$ 그 자체의 1비트 왼쪽 주기적 이동으로 얻을 $f(n)$ 수 있다. If $n$ is represented in binary as $n=1b_{1}b_{2}b_{3}\dots b_{m}$ , then the solution is given by $f(n)=b_{1}b_{2}b_{3}\dots b_{m}1$ . 이에 대한 증거는 $2^{m}+l$ 을 $2^{m}+l$ + l $2^{m}+l$ {\ $displaystyle 2^{$ m}+ $l}$ 로 표현하거나 $2^{m}+l$ $f(n)$ ( $f(n)$ ) $f(n)$ 에 대한 위의 표현에서 나타난다 $f(n)$

구현: n이 인구수를 나타내는 경우, 안전한 위치는 $f(n)=2l+1$ $f(n)=2l+1$ = $f(n)=2l+1$ $f(n)=2l+1$ + 1 $f(n)=2l+1$ 기능으로 주어진다 $f(n)=2l+1$ 여기서 n $n=2^{m}+l$ = $n=2^{m}+l$ + l $n=2^{m}+l$ 및 $n=2^{m}+l$ $0\leq l<2^{m}$ $0\leq l<2^{m}$ $0\leq l<2^{m}$ < $0\leq l<2^{m}$ > 2m ${\displaystystyleq l<2^{m$

이제 숫자가 이진 형식으로 표시되면 첫 번째 비트는 $2^{m}$ ${\$ 를 나타내고, 나머지 $2^{m}$ 비트는 $l$ 를 나타낸다. 예를 들어, $n=41$ = $n=41$ $n=41$ 인 경우 $n=41$ 이항 표현은

n = 1 0 0 0 0 1 2 1 = 1 0 0 0 0 0 l = 0 1 0 0 0 1

    /**   *    * @param n 원 안에 서 있는 사람 수   * @사형 집행에서 살아남을 수 있는 안전한 위치 반환    * f(N) = 2L + 1 여기서 N = 2^M + L 및 0 <= L < 2^M>   */  공중의 인트로 getSafePosition(인트로 n) {   // 방정식에 대한 L 값 찾기   인트로 ValueOfL = n - 정수.highstOneBit(n);   돌아오다 2 * ValueOfL  + 1;  }

비트 와이즈

안전한 위치를 찾는 가장 쉬운 방법은 비트 연산자를 사용하는 것이다. 이 접근법에서 가장 유의미한 n의 집합 비트를 가장 유의하지 않은 비트로 이동하면 안전 위치가 반환된다.^[9] 입력은 양의 정수여야 한다.

n = 1 0 0 0 0 1 n = 0 1 0 0 1

    /**      *       * @param n (41) 원 안에 서 있는 사람 수      * @사형 집행에서 살아남을 수 있는 안전한 위치 반환       */     공중의 인트로 getSafePosition(인트로 n) {         돌아오다 ~정수.highstOneBit(n*2) & ((n<<1)   1);         //     ---------------------- ---    ------------         // 첫 번째 세트 비트 왼쪽 이동 n 및 마지막 비트 이동         // 그리고 그것의 보완을 받아라.                //                                           // n을 2로 곱하기            // Bitwise And 그리고 두 피연산자 모두에 비트를 복사하는 것이 있다.     }

k=3

1997년 로렌츠 할바이젠과 노르베르트 헝거뷔흘러는 케이스 $k=3$ = $k=3$ $k=3$ 에 대한 폐쇄형 형식을 발견했다 $k=3$ 그들은 일정한 상수가 있다는 것을 보여주었다.

약 0.8111원...}

임의의 정밀도로 계산할 수 있다. Given this constant, choose $m$ to be the greatest integer such that $\operatorname {round} (\alpha \cdot (3/2)^{m})\leq n$ (this will be either $m^{\prime }=\operatorname {round} (\log _{3/2}n/\alpha )$ or $m^{\prime }-1$ $1 (\displaystyle$ m $^{\premy }-1$ } $)$ 그렇다면 마지막 생존자는.

f(n)=3(n-\operatorname {round} (\alpha \cdot (3/2)^{m}))+2

f

f(n)=3(n-\operatorname {round} (\alpha \cdot (3/2)^{m}))+2

f(n)=3(n-\operatorname {round} (\alpha \cdot (3/2)^{m}))+2

(

f(n)=3(n-\operatorname {round} (\alpha \cdot (3/2)^{m}))+2

)

f(n)=3(n-\operatorname {round} (\alpha \cdot (3/2)^{m}))+2

= 3

f(n)=3(n-\operatorname {round} (\alpha \cdot (3/2)^{m}))+2

( n

f(n)=3(n-\operatorname {round} (\alpha \cdot (3/2)^{m}))+2

-

f(n)=3(n-\operatorname {round} (\alpha \cdot (3/2)^{m}))+2

f(n)=3(n-\operatorname {round} (\alpha \cdot (3/2)^{m}))+2

(

f(n)=3(n-\operatorname {round} (\alpha \cdot (3/2)^{m}))+2

f(n)=3(n-\operatorname {round} (\alpha \cdot (3/2)^{m}))+2

(

f(n)=3(n-\operatorname {round} (\alpha \cdot (3/2)^{m}))+2

/

f(n)=3(n-\operatorname {round} (\alpha \cdot (3/2)^{m}))+2

)

f(n)=3(n-\operatorname {round} (\alpha \cdot (3/2)^{m}))+2

)

f(n)=3(n-\operatorname {round} (\alpha \cdot (3/2)^{m}))+2

) +

f(n)=3(n-\operatorname {round} (\alpha \cdot (3/2)^{m}))+2

{\displaystyle f(n)=3(n-\cdname {round})(\cdot (3/2)^{m})+2

}

$n\geq 5$ n $n\geq 5$ 5 $n\geq 5$ 에 대해 $n\geq 5$

연산 예로서 할바이젠과 헝거뷔흘러는 $n=41,k=3$ = $n=41,k=3$ k $n=41,k=3$ = $n=41,k=3$ ${\displaystyle n=41,k=3}($ 실제 요셉푸스 문제의 원래 공식이다). 이들은 다음을 계산한다.

m^{\premy }\cHBN {round}(\log _{3/2}41/0.8111)\cHBN {round}(9.68)=10

\operatorname {round} (\alpha \cdot (3/2)^{m^{\prime }})\approx \operatorname {round} (0.8111\cdot (3/2)^{10})=47

and therefore

m=9

\operatorname {round} (0.8111\cdot (3/2)^{9})\approx \operatorname {round} (31.18)=31

\operatorname {round} (0.8111\cdot (3/2)^{9})\approx \operatorname {round} (31.18)=31

(0

\operatorname {round} (0.8111\cdot (3/2)^{9})\approx \operatorname {round} (31.18)=31

\operatorname {round} (0.8111\cdot (3/2)^{9})\approx \operatorname {round} (31.18)=31

(

\operatorname {round} (0.8111\cdot (3/2)^{9})\approx \operatorname {round} (31.18)=31

3

\operatorname {round} (0.8111\cdot (3/2)^{9})\approx \operatorname {round} (31.18)=31

\operatorname {round} (0.8111\cdot (3/2)^{9})\approx \operatorname {round} (31.18)=31

)

\operatorname {round} (0.8111\cdot (3/2)^{9})\approx \operatorname {round} (31.18)=31

)

\operatorname {round} (0.8111\cdot (3/2)^{9})\approx \operatorname {round} (31.18)=31

\operatorname {round} (0.8111\cdot (3/2)^{9})\approx \operatorname {round} (31.18)=31

\operatorname {round} (0.8111\cdot (3/2)^{9})\approx \operatorname {round} (31.18)=31

\operatorname {round} (0.8111\cdot (3/2)^{9})\approx \operatorname {round} (31.18)=31

)

\operatorname {round} (0.8111\cdot (3/2)^{9})\approx \operatorname {round} (31.18)=31

=

\operatorname {round} (0.8111\cdot (3/2)^{9})\approx \operatorname {round} (31.18)=31

{\displaystyle \operatorname {round} (0.8111\cdot (3/2)^{9}\

cdn}\cdnot {

round}

일반적인 경우

동적 프로그래밍은 첫 번째 단계를 수행한 다음 나머지 문제의 해결책을 사용하여 일반적인 사례에서 이 문제를 해결하는 데 사용된다. 지수가 1에서 시작되면 $첫$ 번째 사람으로부터 $s$ 교대하는 $s$ 사람이 위치 $((s-1){\bmod {n}})+1$ ( $((s-1){\bmod {n}})+1$ ( $((s-1){\bmod {n}})+1$ - $((s-1){\bmod {n}})+1$ ) $((s-1){\bmod {n}})+1$ $((s-1){\bmod {n}})+1$ ) $((s-1){\bmod {n}})+1$ + $((s-1){\bmod {n}})+1$ ${\displaystyle ((s-1){\bmod{n})+1$ }가 된다 $((s-1){\bmod {n}})+1$ 여기서 n은 총 인원수다. $f(n,k)$ f $f(n,k)$ ( $f(n,k)$ , $f(n,k)$ ) $f(n,k)$ 는 생존자의 위치를 나타낸다 $f(n,k)$ . $k$ $k$ -th $k$ 번째 사람이 살해된 $n-1$ n - $n-1$ {\ $displaystyle n-1}$ 의 원이 남아 $n-1$ 있고, 다음 카운트는 원래 문제의 번호가 $(k{\bmod {n}})+1$ mod $(k{\bmod {n}})+1$ ) + $(k{\bmod {n}})+1$ {\ $displaystyle (k{\bmod{n}})+1}$ 이었던 사람부터 시작한다 $(k{\bmod {n}})+1$ $1$ $1$ 에서 카운팅을 시작하면 $f(n-1,k)$ 나머지 원의 생존자 위치는 $f(n-1,k)$ - 1, $f(n-1,k)$ ) $f(n-1,k)$ 이(가) 될 것이다 $1$ 시작점이 $(k{\bmod {n}})+1$ $(k{\bmod {n}})+1$ $(k{\bmod {n}})+1$ ) $(k{\bmod {n}})+1$ + $(k{\bmod {n}})+1$ ${\displaystystyle(k{\bmod{n}}})+1$ }인 $(k{\bmod {n}})+1$ ^[10] 점을 고려하여 전환한다.

f(n,k)=(f(n-1,k)+k-1){\bmod{n}+1,{\text{{}, }f(1,k)=1\

더 간단한 형태를 취하는 것

g(n,k)=(g(n-1,k)+k){\bmod{n},{\text{{}g(1,k)=0

대신 위치 번호가 $n-1$ $0$ $0$ 에서 $0$ $n-1$ - 1 $n-1$ 사이에 있는 경우.

이 접근방식은 $O(n)$ 시간 $O(n)$ ( n $O(n)$ ) $O(n)$ 이 $O(n)$ 가) 있지만, 작은 $k$ $k$ 및 $k$ 큰 $n$ ${\displaystyn}$ 의 경우 다른 접근방식이 있다 $n$ . 두 번째 접근법도 동적 프로그래밍을 사용하지만 $O(k\log n)$ 시간 O $O(k\log n)$ $O(k\log n)$ $O(k\log n)$ ) ${\displaystyle O(k\log$ n $)}$ 이(가) 있다 $O(k\log n)$ k-th, 2k-th, ..., ( $(\lfloor n/k\rfloor k)$ / $(\lfloor n/k\rfloor k)$ k ) ${\displaystyle (\llfloor$ n/ $k\rfloor$ k $)}$ -th를 $(\lfloor n/k\rfloor k)$ 한 단계로 죽이고, 번호를 바꾸는 것을 기본으로 한다.^{[citation needed]}

이 개선된 접근방식은 형식을 취한다.

g(n,k)={\begin{cases}0&{\text{if }}n=1\\(g(n-1,k)+k){\bmod {n}}&{\text{if }}1<n<k\\\left\lfloor {\frac {k((g(n',k)-n{\bmod {k}}){\bmod {n}}')}{k-1}}\right\rfloor {\text{where }}n'=n-\left\lfloor {\frac {n}{k}}\right\rfloor &{\text{if }}k\leq n\\\end{cases}}

참조

인용구

^ R.Ugalde, Laurence. "Josephus problem in Fōrmulæ programming language". Fōrmulæ. Retrieved July 26, 2021.
^ Dowdy & Mays 1989, 페이지 125.
^ 바첼트 1612 페이지 174.
^ 허슈타인 & 카플란스키 1974년 121-126페이지.
^ 자벨 1976, 페이지 48, 51.
^ Rouse Ball 1905 페이지 19.
^ 뉴먼 1988, 페이지 2403–2405.
^ 로빈슨 1960, 페이지 47-52.
^ "Josephus Problem using Bitwise Operation (Java)". GitHub. January 7, 2018. Retrieved January 7, 2018.
^ Park & Teixeira 2018, 페이지 1-7.

원천

Bachet, C. G. (1612). Problemes Plaisants ed Delectables qui se font par les Nombres (in French).
Graham, R. L.; Knuth, D. E.; Patashnik, O. (1989). Concrete Mathematics: A Foundation for Computer Science. Addison Wesley. ISBN 978-0-201-14236-5.
Herstein, I. N.; Kaplansky, I. (1974). Matters Mathematical. Harper and Row. ISBN 9780060428037.
Josephus, Flavius (n.d.). The works of Flavius Josephus : in three volumes ; with illustrations. Translated by William Whiston. London: George Routledge & Sons.
Newman, J. R. (1988). The World of Mathematics. Vol. 4. Tempus.
Park, Jang-Woo; Teixeira, Ricardo (2018). "Serial execution Josephus Problem". Korean J. Math. 26 (1): 1–7. doi:10.11568/kjm.2018.26.1.1.
Robinson, W. J. (1960). "The Josephus problem". Math. Gazette. 44 (347): 47–52. doi:10.2307/3608532. JSTOR 3608532.
Rouse Ball, W. W. (1905). Mathematical Recreations and Essays (2nd ed.). London: Macmillan.
Zabell, S. L. (1976). "Letter to the editor" (PDF). Fibonacci Quarterly. 14: 48–51.

추가 읽기

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Chapter 14: Augmenting Data Structures". Introduction to Algorithms (Second ed.). MIT Press and McGraw-Hill. p. 318. ISBN 0-262-03293-7.
Dowdy, James; Mays, Michael E. (1989). "Josephus Permutations". Journal of Combinatorial Mathematics and Combinatorial Computing. 6: 125–130.
Halbeisen, L.; Hungerbühler, N. (1997). "The Josephus Problem". J. Théor. Nombres Bordeaux. 9 (2): 303–318. doi:10.5802/jtnb.204.
Jakóbczyk, F. (1973). "On the generalized Josephus problem". Glasow Math. J. 14 (2): 168–173. doi:10.1017/S0017089500001919.
Lloyd, Errol L. (1983). "An O(n logm) algorithm for the Josephus Problem". J. Algor. 4 (3): 262–270. doi:10.1016/0196-6774(83)90025-1.
Odlyzko, Andrew M.; Wilf, Herbert S. (1991). "Functional iteration and the Josephus problem". Glasgow Math. J. 33 (2): 235–240. doi:10.1017/S0017089500008272.
Ruskey, Frank; Williams, Aaron (2010). "The Feline Josephus Problem". Lect. Not. Comp. Sci. Lecture Notes in Computer Science. 6099: 343–354. Bibcode:2010LNCS.6099..343R. doi:10.1007/978-3-642-13122-6_33. ISBN 978-3-642-13121-9. FUN2010
Ruskey, Frank; Williams, Aaron (2012). "The Feline Josephus Problem". Theory Comput. Syst. 50: 20–34. doi:10.1007/s00224-011-9343-6. S2CID 2273820.
Sullivan, Shaun; Insko, Erik (2018). "A variant on the Feline Josephus Problem". arXiv:1803.11340 [math.CO].
Shams-Baragh, Armin (2002). "Formulating the Extended Josephus Problem" (PDF). Archived from the original (PDF) on 2018-07-30.
Theriault, Nicolas (2001). "Generilazations of the Josephus Problem". Util. Math. (58): 161–173. CiteSeer^x: 10.1.164.2015.
Woodhouse, David (1973). "The extended Josephus problem". Rev. Mat. Hisp.-Amer. 33 (4): 207–218.

외부 링크

50개^th 중 n개(최대)를 모두 선택할 수 있는 커트 더 크릿(Cut-the-knot)에서의 요셉푸스 플라비우스 게임(Java Applet)이다.
Weisstein, Eric W. "Josephus Problem". MathWorld.
요셉푸스 문제 - 유튜브의 숫자표기

[formulae.org-1] R.Ugalde, Laurence. "Josephus problem in Fōrmulæ programming language". Fōrmulæ. Retrieved July 26, 2021.

[FOOTNOTEDowdyMays1989125-2] Dowdy & Mays 1989, 페이지 125.

[FOOTNOTEBachet1612174-3] 바첼트 1612 페이지 174.

[FOOTNOTEHersteinKaplansky1974121–126-4] 허슈타인 & 카플란스키 1974년 121-126페이지.

[FOOTNOTEZabell197648,_51-5] 자벨 1976, 페이지 48, 51.

[FOOTNOTERouse_Ball190519-6] Rouse Ball 1905 페이지 19.

[FOOTNOTENewman19882403–2405-7] 뉴먼 1988, 페이지 2403–2405.

[FOOTNOTERobinson196047–52-8] 로빈슨 1960, 페이지 47-52.

[github.com-9] "Josephus Problem using Bitwise Operation (Java)". GitHub. January 7, 2018. Retrieved January 7, 2018.

[FOOTNOTEParkTeixeira20181–7-10] Park & Teixeira 2018, 페이지 1-7.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

Search