| [ QuizWit ] in KIDS 글 쓴 이(By): Lina (Inverse) 날 짜 (Date): 2007년 12월 7일 금요일 오후 08시 11분 51초 제 목(Title): Re: [Q]어항용적찾기 어항이 4개나 되니 골치아픈데요. 일단 쉬운 걸로 어항 2개, 각각 1하고 1/2 용적인 경우. 1. 하나에 1을 부어본다. 1-1 안깨지면 째수를 외치며 나머지 하나에 1/2을 붓는다. (총합 3/2) 1-2 깨지면 개째수를 외치며 나머지 하나에 1을 붓는다. (총합 1) 확률은 반반이므로 기대값은 5/4 그럼 어항 3개 1,1/2,1/3 의 경우 알고리즘 1 1. 하나에 1을 부어본다. 1-1 안깨지면 (확률 1/3) 나머지중 하나에 1/2을 부어본다. 1-1-1 그래도 안깨지면 (확률 1/2) 나머지 하나에 1/3을 붓는다. (총합 11/6) 1-1-2 그게 깨지면 (확률 1/2) 나머지 하나에 1/2을 붓는다. (총합 3/2) 1-2 1/3 넘자마자 깨지면 (확률 1/3) 위 어항 2개문제가 된다. (이 루트의 기대값은 5/4) 1-3 1/2 넘자마자 깨지면 (확률 1/3) 어항 2개 1하고 1/3 용적문제가 된다. 1-3-1 하나에 1을 부어봐서 안깨지면 (확률 1/2) 나머지 하나에 1/3을 붓는다. (총합 4/3) 1-3-2 1을 부어봐도 깨졌다면 (확률 1/2) 이게 다 노무현 때문이다를 외치며 나머지 하나에 1을 붓는다. (총합 1) 기대값 : 1/6*11/6 + 1/6*3/2 + 1/3 * 5/4 + 1/6 * 4/3 + 1/6 * 1 = 49/36 알고리즘 2 1. 하나에 1/2을 부어본다. 1-1 깨지면 (확률 1/3) 위 어항 2개 문제가 된다. (기대값 5/4) 1-2 안깨지면 (확률 2/3) 나머지중 하나에 1/2을 부어 본다. 1-2-1 만약 깨지면(확률 1/2) 어항 2개문제로 환원 1-2-2 안깨지면 (확률 1/2) 나머지 하나에 1/3을 붓는다. (총합 4/3) 기대값 1/3 * 5/4 + 1/3 * 5/4 + 1/3* 4/3 = 23/18 알고리즘 1보다 안좋다. 아무래도 알고리즘 1이 최선인 듯. 어항 4개는 3개짜리 알고리즘을 적당히 확장하는 게 최선이 아닐까 싶다. 한개에 1을 부어보며 1/4, 1/3, 1/2 넘기면서 깨지는지 확인해서 3개짜리 문제로 환원. 안깨지면 역시 나머지 3개를 놓고 머리굴리는 문제로 환원. 이 알고리즘의 최적이라는 증명은.. 경제살리기도 바쁜데 공들여 증명 따위 할 새가 있나. 일단 물부터 부어보고 깨지지 않는다 싶으면 그냥 배 띄워 운하로 가는 거다. 어둠보다 더 검은 자여 밤보다도 더 깊은 자여 혼돈의 바다여 흔들리는 존재여 금색의 어둠의 왕이여 나 여기서 그대에게 바란다 나 여기서 그대에게 맹세한다 내 앞을 가로막는 모든 어리석은 자들에게 나와 그대의 힘을 합쳐 마땅한 파멸을 가져다 줄 것을! --- Lina Inverse @ Slayers --- |