6 апреля 2012 г.

Задачи на собеседованиях: оптимизация

Часто встречающаяся задача на оптимизацию.

Есть два шарика и небоскрёб в 100 этажей. Если бросать шарики из окон небоскрёба, то начиная с какого-то этажа они будут разбиваться вдребезги (и после этого разбившийся шарик уже нельзя будет использовать). Нужно предложить алгоритм, который поможет найти этот роковой этаж за оптимальное число итераций. Шарики не обязательно сохранять целыми к концу алгоритма.

4 комментария:

  1. Если шариков бесконечно - бинарный поиск за logn
    Если их 2 - то шагать от нулевого по два этажа и скидывать шарик с 2*i этажа. Если разобъется на 2*i и не разобъется на 2*i-1, то понятно. Если разобъется на 2*i и на 2*i-1, то 2*(i-1).
    Умней пока что не идет ничего.

    ОтветитьУдалить
    Ответы
    1. Итого, если разбиваются на 99-м этаже, то кол-во итераций ~50? Можно быстрее.

      Удалить
    2. Понял.
      Если делать подобными скачками - то так:
      минимизируем функцию f(k)=100/k + k, где k - количество "скачков".
      Получаем k=10, min(f(k))=20.
      Сначала идем большими скачками, после того как разобъется - пробежать последний скачок по одному этажу.

      Удалить
  2. самое простое - использовать методе золотого сечения.

    ОтветитьУдалить