1
우리가 정수 집합을 가지고 있다고 상상해보십시오. 우리는 그것을 모릅니다. 우리가 알고있는 유일한 것은 모든 숫자가 간격 [0, MAX]에 있고, 분명히 숫자가 반복되지 않는다는 것입니다. 그런 다음 세트를 찾아야합니다. 우리는 정수를 명명 할 수 있고, 우리는 우리가 선택한 수보다 작거나 같은 집합의 수를 말하고 그것에 가장 가깝습니다. 우리의 목적은 최소한의 시도로 세트를 찾는 것입니다.우리가 말하는 숫자에 가장 가깝거나 더 낮은 숫자를 말하면 정수 집합을 찾는 효율적인 알고리즘
예를 들어 [0, 7, 8, 1000] 및 MAX == 10000으로 설정하십시오. TRY를 우리가 사용할 수있는 함수로합시다. 그런 다음 TRY (4) == 0, TRY (7) == 7, TRY (8) == 8, TRY (555) == 8 및 TRY (7777) == 1000. 그런 다음 숫자를 놓치지 않도록해야합니다. 그래서 다른 많은 숫자를 시도해야합니다.
질문 : 집합을 찾는 가장 효율적인 알고리즘은 무엇입니까? 간격으로 모든 숫자를 시도하는 것은 분명히 나쁩니다. 어쩌면 우리는 (TRY (7777) == 1000이 아니므로 (1000, 7777)에 숫자가없는) 집합을 제외하는 2 진 검색과 유사한 알고리즘을 시도해야합니다. 최소 시도 횟수의 알고리즘은
를 롤, 그렇게 정말! 이것은 명백한 내가하지에 실패했습니다. 아마도 그 이유를 당신의 대답은 정말 답을 규칙으로 그것을 본다. 내가 가진 문제를 지나치게 단순화했다. (숫자를 직접적으로 시도 할 수는 없지만 복잡하지만 단조로운 함수 TRY를 계산해야 함). 어쨌든,이 용어로 당신의 솔루션은 완벽합니다. – user517893