Часто встречающаяся задача на оптимизацию.
Есть два шарика и небоскрёб в 100 этажей. Если бросать шарики из окон небоскрёба, то начиная с какого-то этажа они будут разбиваться вдребезги (и после этого разбившийся шарик уже нельзя будет использовать). Нужно предложить алгоритм, который поможет найти этот роковой этаж за оптимальное число итераций. Шарики не обязательно сохранять целыми к концу алгоритма.
Если шариков бесконечно - бинарный поиск за logn
ОтветитьУдалитьЕсли их 2 - то шагать от нулевого по два этажа и скидывать шарик с 2*i этажа. Если разобъется на 2*i и не разобъется на 2*i-1, то понятно. Если разобъется на 2*i и на 2*i-1, то 2*(i-1).
Умней пока что не идет ничего.
Итого, если разбиваются на 99-м этаже, то кол-во итераций ~50? Можно быстрее.
УдалитьПонял.
УдалитьЕсли делать подобными скачками - то так:
минимизируем функцию f(k)=100/k + k, где k - количество "скачков".
Получаем k=10, min(f(k))=20.
Сначала идем большими скачками, после того как разобъется - пробежать последний скачок по одному этажу.
самое простое - использовать методе золотого сечения.
ОтветитьУдалить