[일반] aa

[익명(59.22)]

Simon bar Kokhba thinks of an integer between 1 and 1,000,000 (or so he claims). You aretrying to determine his number by asking as few yes/no questions as possible. How manyyes/no questions are required to determine Simon’s number in the worst case? Give bothan upper bound (supported by an algorithm) and a lower bound

[0xrgb(0xrgb)]

일단 최소한의 성의를 보이도록합시다. 긁어오면서 사라진 띄어쓰기나 문장부호는 수정을 하셔야죠

[0xrgb(0xrgb)]

두번째로 되게 유명한 binary search 문제입니다. 일단 한번에 맞출수있으니 lower는 1, upper는 ceil(log2(1000000))

[0xrgb(0xrgb)]

세번째로 이게 최적임을 증명하기 위해서는 decision tree를 그려서 비둘기집의 정리를 쓰던가, adversary를 가정하는 증명 방법이 있습니다

[0xrgb(0xrgb)]

네번째로 윗글같이 이해하기 어려운 글은 자제해 주시길 바랍니다.