Сборник задач разного уровня сложности по математике, информатике, физике, химии, программированию, экономике etc. Логические задачи, SQL задачи, решение задач. Задачи с ответами, а также нерешённые задачи.
Переходить мост можно только с фонариком, потому что темно и мост без перил.
Одновременно на мосту мосту могут находиться не более двух человек, потому что мост старый и не выдержит больше.
У каждого человека своя скорость прохождения через мост: первый проходит мост за 1 минуту, второй — за 2 минуты, третий — за 5, четвёртый — за 10 минут.
Когда два человека переходят мост вместе, они идут со скоростью наиболее медленного из них.
Какое минимальное время понадобится этой четвёрке, чтобы перейти мост, и в какой последовательности им надо его переходить?
Обозначим людей 1,2,5,10 по времени, затрачиваемому на переход через мост.
Вот последовательность переходов, гарантирующая минимальное время (время на каждый переход указано в скобках
0. Все на исходной позиции: 1, 2, 5, 10 ⇔ — (0 мин.)
1. 1 и 2 идут на другой берег: 5, 10 ⇔ 1, 2 (2 мин.)
2. 1 возвращается: 1, 5, 10 ⇔ 2 (1 мин.)
3. 5 и 10 идут на другой берег: 1 ⇔ 2, 5, 10 (10 мин.)
4. 2 возвращается: 1, 2 ⇔ 5, 10 (2 мин.)
5. 1 и 2 идут на другой берег: — ⇔ 1, 2, 5, 10 (2 мин.)
Итого: 2 + 1 + 10 + 2 + 2 = 17 минут.
Формальное доказательство можно провести с использованием графа, вершинами в котором являются положения людей и фонарика на разных концах моста; две вершины соединены ребром тогда и только тогда, когда из одного положения можно перейти в другое по условиям задачи (фонарик, не более двух человек за переход etc); вес ребра — время, затрачиваемое на такой переход.
Для решения этой задачи надо найти на этом графе минимальный путь из начального положения в конечное.
Есть на сайте:
Онлайн кроссвордыЗадачиОнлайн игрыБлог
Все работы, опубликованные на сайте — авторские, если не указано иное.
Перепечатка возможна только с письменного разрешения владельцев ресурса, с обязательной ссылкой на сайт petruchek.info.
Пишите нам: .
Сайт должен работать в IE, FF, Opera, Safari.