По какой формуле вычислить минимальное количество раз для установки шага диапазона для вычисления?

Question

[Torento20345]

Как узнать рекомендуемый шаг диапазона для вычисления?
Например, у нас есть число 128, которое мы не знаем и при проверке мы получим значение, что результат больше или меньше 128, ну или мы отгадали.

Максимальная длинна массива 256.

Как нам узнать рекомендуемый шаг, чтобы сделать поиск по шагу до момента, пока не получим результат, что число было больше, а после к предыдущему шагу будем уже добавлять запрос +1, пока не получим 128.

Answer 1

[Wataru]

Звучит, как бинарный поиск. Изначальный шаг - половина длины массива (128).
Следующий, половина от этого и так далее. Так будет максимум 8 проверок всего.

Если же надо делать обязательно +1 вторым шагом, то можно вычислить максимальное количество проверок, если первый шаг - X, а длина массива - N.

Первых проверок будет максимум - floor(N/X), вторых (с шагом +1) - X-1.

Можно примерно подсчитать в вещественных числах и попытаться минимизировать f(x) = N/X+X.

Можно найти производную f'(x) = 1-n/x^2. Ноль у этой производной при x=sqrt(n).

Отсюда получается, что примерно sqrt(256)=16 - искомая длина. Максимальное число проверок - 32.

Comments

[Torento20345]

Спасибо

[Torento20345]

А что, если квадрат числа получается не целое число?
Например 500.
Мы получаем 22.36.
Как нам здесь быть?
Если брать шаг по 22, то мало, а если по 23, то получим перебор.

[Wataru]

Torento20345, Производная функции f(x) - пересекает 0 только в одной точке. До этого она отрицательная, а потом положительная. Значит f(x) - имеет один минимум. Если мы ограничены условием, что x - целое, то минимум - одна из ближайших к оптимальному x значений.

Или 22, или 23 в вашем примере. Нужно подсчитать сколько ходов там будет в итоге и выбрать минимум из двух вариантов.

При x=22, n = 500 будет. floor(n/x) + x = floor(500/22) + 22 = 22 + 22 = 44

При x=23, n = 500 будет. floor(n/x) + x = floor(500/23) + 23 = 21 + 23 = 44

Тут без разницы, сколько брать 22 или 23. Всегда ли это так - мне лень думать. Преберите 2 варинта в вашей программе и найдите лучший.