[[파일:1477942124-animation-23.gif]] [목차] == 유래 == 유대인 역사가 [[플라비우스 요세푸스]]가 겪은 경험을 바탕으로 만들어진 문제이다. 당시 [[예루살렘]]에서 살았던 요세푸스는 유대-로마 전쟁 때 유대군 장교로 참전했다가 동료 병사들, 자신을 포함해 총 41명과 함께 요타파타[* 갈릴리 근처.]에서 서기 70년에 황제가 될 [[베스파시아누스]]가 지휘하는 로마군에게 포위되었고, 동료들은 로마군의 손에 죽느니 스스로 죽겠다고 집단자살하기로 했다. 그러나 직접 [[자살]]하는 것이 어려웠는지, 그들은 서로 죽이기 위한 알고리즘을 세운다. 요세푸스를 따라온 동료들은 위의 그림과는 다르게 2명 살리고 한 명 죽이는 식으로 자살했다.[* [[http://terms.naver.com/entry.nhn?docId=4396921&cid=59920&categoryId=59920]] ] 그러나 요세푸스는 동료들의 뜻에 반대하고 살고 싶었고, 수학적 논리력을 발휘하여 끝까지 살기 위한 자리를 찾아서 결국 살아남아 베스파시아누스에게 항복했다. == 문제 == [[위키피디아]][[https://en.wikipedia.org/wiki/Josephus_problem|출처]]에 따르면 41개의 숫자 중 하나를 건너뛰는 형태로 없애고 만약 41을 넘어가게 되면 다시 가장 처음번호로 돌아가는 식을 반복해 마지막에 남은 숫자를 구하는 문제이다. 이와는 다르게 보다 일반적인 문제도 있는데, 1~n 까지의 총 n개의 숫자가 있고 처음에는 k를 없애고 그 다음에는 2k를 없애는 식으로 하다가 n을 넘어가게 되면 존재하는 숫자 중 가장 낮은 숫자로 되돌아가 이와 같은 형태를 반복하는 문제이다. 만약 다 세지 못한채 한바퀴를 돌게 되면 그 남은수는 누적된 채 계속 세개 된다. 남은 수를 1개 구하는 경우도 있고, k-1개 구하는 경우도 있으나 두 경우에 있어서 풀이의 차이는 거의 존재하지 않는다. == 방법1. 점화식을 이용한 풀이 == n 명을 원형으로 세워놓고 3번째마다 지울 때 마지막 남은 사람의 자리수 번호를 [math(f(n))] 이라 하자 이제 [math(f(n))] 과 [math(f(n+1))] 사이의 관계를 찾아보자 [math(n+1)] 명을 원형으로 세워놓고 3번째 사람을 지우면 이제 n명만 남게 되고 4번째 사람부터 다시 시작하는 형태가 된다. 즉, 사람의 배열은.. [math(4, 5, 6, 7, 8, 9, \cdots n, n+1, 1, 2)] (3을 지워서 총 n명) 가 되고 처음 [math(f(n))] 기준으로는 [math(1, 2, 3, 4, 5, 6, \cdots n-3, n-2, n-1, n)] 순서와 매핑이 된다. (이 부분이 바로 점화식을 유도하는데 핵심적인 사고이다) 이때 [math(n)]명중에 [math(p)]번째가 가장 마지막까지 남는 자리라고 하면 즉, [math(f(n)=p)] 라 하자 위의 두 배열의 매핑관계를 보면..다음과 같이 점화식을 유도할 수 있다. [math(p = f(n) = n-1)] 일때는 [math(f(n+1) = 1))] [math(\cdots)] ㄱ [math(p = f(n) = n)] 일때는 [math(f(n+1) = 2)] [math(\cdots)]ㄴ [math(p = f(n) = 1, 2, \cdots n-2)] 일때는 [math(f(n+1) = f(n) + 3)] [math(\cdots)]ㄷ [math(f(2)=2)] ㄴ에 의해 [math(f(3)=3)] ㄱ에 의해 [math(f(4)=1)] ㄷ에 의해 [math(f(5)=4)] ㄱ에 의해 [math(f(6)=1)] ㄷ에 의해 [math(f(7)=4)] ㄷ에 의해 [math(f(8)=7)] ㄱ에 의해 [math(f(9)=1)] : ㄷ에 의해 [math(f(41)=31)] 즉, 41명일 때 요세푸스는 31번째 앉아서 마지막까지 살아남을 수 있었다. == 방법2. 이진법을 이용한 풀이 == == 방법3. 프로그래밍을 이용한 풀이 == 다음 방법은 프로그램 언어 '''파이썬'''을 이용한 프로그래밍이다. {{{#!folding 【 파이썬 코드 펼치기 · 접기 】 def 요세푸스_함수(총사람숫자는몇,몇번마다죽일까): 요세푸스={} for 숫자 in range(1,총사람숫자는몇+1): 요세푸스[숫자]=1 네가죽을래=1#돌아가는 숫자, '총사람숫자는몇'을 넘어가면 다시 1로 감 죽은사람수=0#'총사람숫자는몇-몇번마다죽일까+1' 이 되면 while에서 벗어남 몇번돌림수=0#'몇번마다죽일까-1'이 되면 죽음 while True: #print (네가죽을래, 죽은사람수, 몇번돌림수, 요세푸스[네가죽을래]) if 요세푸스[네가죽을래]==1 and 몇번돌림수==몇번마다죽일까-1: 요세푸스[네가죽을래]=0 죽은사람수+=1 몇번돌림수=0 elif 요세푸스[네가죽을래]==0: 네가죽을래+=1 if 네가죽을래>총사람숫자는몇: 네가죽을래-=총사람숫자는몇 else:#네가죽을래==1 and 몇번돌림수!=몇번마다죽일까-1 몇번돌림수+=1 네가죽을래+=1 if 네가죽을래>총사람숫자는몇: 네가죽을래-=총사람숫자는몇 if 죽은사람수==총사람숫자는몇-몇번마다죽일까+1: break x=[] for 숫자 in range(1,총사람숫자는몇+1): if 요세푸스[숫자]==1: x.append(str(숫자)) return ('살아남은 사람:'+str(x)) 이 프로그래밍을 통한 결과는 41명의 사람을 3번째마다 죽인다고 가정하면 16번과 31번이 살아남게 된다고 나온다. 또한 5명이 있을 때부터 45명이 있을 때까지 구해보면 답은 다음과 같이 나온다. 5 번째 살아남은 사람:['2', '4'] 6 번째 살아남은 사람:['1', '5'] 7 번째 살아남은 사람:['1', '4'] 8 번째 살아남은 사람:['4', '7'] 9 번째 살아남은 사람:['1', '7'] 10 번째 살아남은 사람:['4', '10'] 11 번째 살아남은 사람:['2', '7'] 12 번째 살아남은 사람:['5', '10'] 13 번째 살아남은 사람:['8', '13'] 14 번째 살아남은 사람:['2', '11'] 15 번째 살아남은 사람:['5', '14'] 16 번째 살아남은 사람:['1', '8'] 17 번째 살아남은 사람:['4', '11'] 18 번째 살아남은 사람:['7', '14'] 19 번째 살아남은 사람:['10', '17'] 20 번째 살아남은 사람:['13', '20'] 21 번째 살아남은 사람:['2', '16'] 22 번째 살아남은 사람:['5', '19'] 23 번째 살아남은 사람:['8', '22'] 24 번째 살아남은 사람:['1', '11'] 25 번째 살아남은 사람:['4', '14'] 26 번째 살아남은 사람:['7', '17'] 27 번째 살아남은 사람:['10', '20'] 28 번째 살아남은 사람:['13', '23'] 29 번째 살아남은 사람:['16', '26'] 30 번째 살아남은 사람:['19', '29'] 31 번째 살아남은 사람:['1', '22'] 32 번째 살아남은 사람:['4', '25'] 33 번째 살아남은 사람:['7', '28'] 34 번째 살아남은 사람:['10', '31'] 35 번째 살아남은 사람:['13', '34'] 36 번째 살아남은 사람:['1', '16'] 37 번째 살아남은 사람:['4', '19'] 38 번째 살아남은 사람:['7', '22'] 39 번째 살아남은 사람:['10', '25'] 40 번째 살아남은 사람:['13', '28'] 41 번째 살아남은 사람:['16', '31'] 42 번째 살아남은 사람:['19', '34'] 43 번째 살아남은 사람:['22', '37'] 44 번째 살아남은 사람:['25', '40'] }}} 답을 이용해 선험적 추론을 할 수 있다. 답을 구하고자 하는 사람들에게 도움이 되길 바란다. [[분류:토막글/수학]]