@Torento20345

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

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

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

Как нам узнать рекомендуемый шаг, чтобы сделать поиск по шагу до момента, пока не получим результат, что число было больше, а после к предыдущему шагу будем уже добавлять запрос +1, пока не получим 128.
  • Вопрос задан
  • 24 просмотра
Решения вопроса 1
wataru
@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.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы