Версия для печати темы

Автор: Hardcore 8.8.2014, 13:56

Дал ответ 2014-08-07 11:08:33. Я не понимаю почему модератору моего ответа не достаточно.

Автор: idler_ 8.8.2014, 18:23

Добрый день!

В задаче требуется найти минимальное число взвешиваний, за которое можно определить фальшивку, и доказать, что за меньшее число взвешиваний сделать это нельзя.
Доказывать оптимальность требуется во всех задачах на поиск оптимального варианта, где явно не сказано, что делать этого не нужно.
Вы привели алгоритм, позволяющий за N взвешиваний определить фальшивку. Теперь вам нужно доказать, что за меньшее число взвешиваний это сделать нельзя. Не исключено, что во время поиска доказательства вы найдёте более оптимальный вариант, тогда доказывать минимальность придётся уже для него.

Автор: idler_ 15.8.2014, 18:57

Закрыто.