| [ QuizWit ] in KIDS 글 쓴 이(By): Convex (4ever 0~) 날 짜 (Date): 1997년06월23일(월) 12시25분47초 KDT 제 목(Title): 숫자 고르기 옵티말 전략 [ QuizWit ] in KIDS 글 쓴 이(By): pomp (위풍당당) 날 짜 (Date): 1997년06월21일(토) 00시18분27초 KDT 제 목(Title): [문제] Optimal Search Procedure 상대가 1, 2, ..., 9 가운데 한 숫자를 고르면, 몇 번의 질문으로 그 숫자를 맞추어야 합니다. 상대방은 "예", "아니오"로만 대답합니다. 그런데, 어떤 특별한 이유로, 숫자가 클수록 상대가 그 숫자를 고를 확률이 크다는 것이 알려져 있습니다. 상대가 고른 숫자를 맞추기 위한 최선의 전략은 무엇일까요? ... & circumstance ******************** 문제에서 몇 번의 질문이라고 했는데 ^^^^ 몇번인지 알려져 있나요? 알려지지 않았다면 질문횟수의 기대값이 최소인 것을 구하면 될터이고.. 숫자크기가 크면 선택될 확률이 크다는 것 밖에 모르니 호프만 코드식은 안될듯 하네요. 그런데 몇번 선택인지 알려져 있다면 기대값이 문제가 아니라 몇번 안에 답을 고르지 못할 활률을 최소화 해야 합니다. (활률=>확률) 1) 한번 선택일 때. 당연히 9를 고름. 최소한 0.11의 확률. 2) 두번 선택일 때. 9를 고르고 아니라고 하면 8을 고름. 최소한 0.22 3) 세번 선택일 때. a) 6 이상(>=)인지 물어봄. =Y=> 8이상인지 물어봄 =Y=> 9 선택 =N=> 7선택 =N=> 4이상인지 물어봄 =Y=> 5 선택 =N=> 3 선택 그러면 0.5 - (1의 확률) <== 요게 답 구할 확률의 lower bound 최소한 0.39는 되겠지요. 4) 네번 선택일 때는 1 - (1의 확률) 만큼으로 구할 수 있고. 최소한 0.89의 확률로 구할 수 있습니다. 5번 선택으론 다 구할 수 있죠. 1의 확률. 6이상이냐 부터 물어보는 바이너리 서취가 최적일 것 같습니다. --,--`-<@ 매일 그대와 아침햇살 받으며 매일 그대와 눈을 뜨고파.. 잠이 들고파.. Till the rivers flow up stream | Love is real \|||/ @@@ Till lovers cease to dream | Love is touch @|~j~|@ @^j^@ Till then, I'm yours, be mine | Love is free | ~ | @@ ~ @@ |