Держите две классические задачи на поиск оптимального алгоритма: одну попроще и одну посложнее.
Задача попроще
Ночь, улица, мост. На одной стороне моста стоят четыре человека, у них один факел на всех. Вокруг — кромешная тьма, и без факела идти не получится. Мост может выдержать только двоих, поэтому идти всем сразу не вариант, причём пара идёт со скоростью самого медленного из двоих. Как им быстрее всего перейти на ту сторону, если первый может перейти этот мост за 1 минуту, второй за 4, третий за 5, а четвёртый — за 8?
Для начала обозначим буквами всех участников перехода:
А — 1 минута
Б — 4 минуты
В — 5 минут
Г — 8 минут
Так как самый быстрый участник проходит мост за минуту (и быстрее всех), логично сделать так, чтобы он всё время шёл с факелом, переводил всех по очереди через мост и возвращался за следующим. Тогда последовательность переходов будет такая:
А + Б = 4 минуты, потому что идём со скоростью самого медленного в паре. Участник Б остаётся на той стороне, а А отправляется обратно.
А = 1 минута, вернулся к двоим оставшимся. Теперь он берёт в пару участника В.
А + В = 5 минут. Перевёл его, оставил вместе с Б и теперь возвращается с факелом за последним.
А = 1 минута, вернулся к последнему, с которым и проходит мост, делая финальный проход.
А + Г = 8 минут. Все перешли, задача выполнена.
Чтобы узнать общее время, складываем всё вместе:
4 + 1 + 5 + 1 + 8 = 19 минут
Если это было просто, принимайтесь за вторую задачку.
Задача посложнее
Всё то же самое, но скорости уже другие: первый может перейти этот мост за 1 минуту, второй за 2, третий за 5, а четвёртый — за 8. Нужно найти самое быстрое время общего перехода.
Казалось бы, решение будет точно таким же, как и в первом случае, и непонятно, что тут сложного. Вот что получается у нас по времени с тем же алгоритмом:
А — 1 минута
Б — 2 минуты
В — 5 минут
Г — 8 минут
А + Б = 2 минуты. Участник Б остаётся на той стороне, а А — отправляется обратно.
А = 1 минута, вернулся к двоим оставшимся. Теперь он берёт в пару участника В.
А + В = 5 минут. Перевёл его, оставил вместе с Б и теперь возвращается с факелом за последним.
А = 1 минута, вернулся к последнему, с которым и проходит мост, делая финальный проход.
А + Г = 8 минут. Все перешли, задача выполнена.
Чтобы узнать общее время, складываем всё вместе:
4 + 1 + 5 + 1 + 8 = 17 минут
❌ Но это слишком медленно. Есть решение быстрее.
Ошибка была в том, что мы применили шаблонное решение, даже не подумав о том, что могут быть другие варианты, а они есть. Следите за руками.
Обозначаем, как обычно, участников и их скорость:
А — 1 минута
Б — 2 минуты
В — 5 минут
Г — 8 минут
Как и в тот раз, отправляем самых быстрых на тот берег.
А + Б = 2 минуты. Участник Б остаётся на той стороне, а А — отправляется обратно.
А = 1 минута, вернулся к двоим оставшимся.
А теперь неочевидное: участник А передаёт факел паре В и Г, которые вдвоём отправляются переходить мост в самом медленном темпе.
В + Г = 8 минут. Теперь их там трое и нам нужно ускориться. Самых быстрый из них — участник Б, который переходит мост за 2 минуты. Отправим его за первым участником.
Б = 2 минуты, вернулся к участнику А, с которым и проходит мост, делая финальный быстрый проход.
А + Б = 2 минуты. Все перешли, задача выполнена.
Наконец складываем всё время вместе:
2 + 1 + 8 + 2 + 2 = 15 минут
✅ И это — правильный ответ, потому что надо было найти самое короткое время, а не просто перевести всех на ту сторону.
