Задача 527
Случайный двоичный поиск

Секретное целое число t выбирается случайно в интервале 1 ≤ tn.

Цель - угадать значение t, делая многократные проверки с помощью целого числа g. После проверки догадки есть три возможных ситуации, в которых выяснится, что g < t, g = t или g > t. При необходимости процесс повторяется.

Обычно, необходимое среднее количество попыток может быть минимизированно с помощью двоичного поиска: при данной нижней границе L и верхней границей H (начальные значения L = 1 и H = n), пусть g = $\lfloor (L+H)/2 \rfloor$, где $\lfloor \rfloor$ - функция целого пола числа. Если g = t, процесс завершается. В противном случае, если g < t, задать L = g+1, а если g > t, задать H = g−1. После задания новых границ процесс поиска повторяется, и, в конце концов, завершается, когда t найдена. Даже если t может быть выведена без применения поиска, положим, что поиск все равно будет необходим, чтобы доказать значение.

Ваш друг Боб уверен, что стандартный двоичный поиск не намного лучше его рандомизированного варианта: вместо задания g = $\lfloor (L+H)/2 \rfloor$, g просто задается случайным целым числом между L и H включительно. Остальной алгоритм таков же, как в стандартном двоичном поиске. Этот новый метод поиска назовем случайным двоичным поиском.

Дано, что 1 ≤ tn для случайного t. Пусть B(n) будет ожидаемым количеством попыток, необходимых для нахождения t с помощью стандартного двоичного поиска, и пусть R(n) будет ожидаемым количеством попыток, необходимых для нахождения t с помощью случайного двоичного поиска. Например, B(6) = 2.33333333 и R(6) = 2.71666667 при округлении до 8 знаков после десятичной точки.

Найдите R(1010) − B(1010), округленное до 8 знаков после десятичной точки.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net