На каждые 2 запроса мы сокращаем пространство поиска на 25%. Сколько всего запросов нужно, чтобы исчерпать все пространство поиска

Question

Предположим, что у нас есть область поиска, состоящая из чисел от 1 до 10 ^ 9. На каждые 2 запроса мы сокращаем пространство поиска на 25%. Какое общее количество запросов потребуется, чтобы полностью исчерпать пространство поиска?

Answer 1

Нам нужно решить это уравнение для n:

1 = 10^9 * (3/4)^(n/2)

Здесь go

1 = 10^9 * (3/4)^(n/2)
1/10^9 = (3/4)^(n/2)
10^9 = (4/3)^(n/2)
log_(4/3) 10^9 = n/2
n = 2 * log_(4/3) 10^9

похоже, что n = 144 довольно близко. Мы можем проверить, что: n / 2 = 72 и (3/4) ^ 72 = 1.0102083739526135305448424868787e-9 и 10 ^ 9 * 1.0102083739526135305448424868787e-9 = 1.0102083739526135305448424868787

Теперь это не может быть равно единице, и это обычно игнорирует эффекты округления. Однако заявленная проблема делает то же самое, поскольку пространство поиска не может уменьшаться ровно на 25% больше, чем несколько раз, прежде чем вы начнете получать дробное количество элементов - другими словами, оно не уменьшается ровно на 25% каждый раз. в любом случае время. Если вы хотите быть точными, вы можете сказать, что пространство поиска уменьшается как можно ближе к 25% на каждом шаге, или оно увеличивается как можно больше, но не более чем на 25% на каждом шаге, et c., и тогда метод разрешения будет заключаться в простом подсчете количества требуемых сокращений при выполнении требуемого округления.