ГДЗ по информатике, 8 класс, Босова, номер 2.25: 4. Основные алгоритмические конструкции

Самый простой способ — использовать Аню (1 мин) как универсального носителя фонаря для каждого перехода. В этом случае Аня сопровождает каждого из остальных туристов по очереди.

• Аня и Борис идут: 2 мин. Аня возвращается: 1 мин. Итого: 3 мин.
• Аня и Вася идут: 5 мин. Аня возвращается: 1 мин. Итого: 6 мин.
• Аня и Даша идут: 10 мин. Аня возвращается: 1 мин. Итого: 11 мин.
• Осталась только Аня, она уже на другом берегу? Нет, в этой схеме после последнего перехода Даши все на месте, но Ане нужно было вернуться за последним? Проверим: Аня+Борис (2), Аня назад (1). Аня+Вася (5), Аня назад (1). Аня+Даша (10). Все на месте. Время: 2+1+5+1+10=19 минут.

Это решение занимает 19 минут. Попробуем улучшить его, объединив самых медленных туристов.

Ключевая идея: чтобы сэкономить время, Вася (5 мин) и Даша (10 мин) должны идти вместе. Тогда время их перехода будет определяться только Дашей (10 мин), а не суммой или отдельными выходами. Но для этого им нужен кто-то, кто принесёт фонарь обратно после их ухода, или кто передаст им фонарь.

Рассмотрим оптимальную последовательность действий:

1. Первый этап: Аня (1) и Борис (2) переходят мост.
   Время перехода определяется более медленным участником: max(1,2)=2 минуты.
   На другом берегу: Аня, Борис. На исходном: Вася, Даша.
2. Возврат фонаря: Кто-то должен вернуть фонарь. Возвращается самый быстрый из находящихся на том берегу — Аня.
   Время возврата: 1 минута.
   Итого за первые два действия: 2+1=3 минуты.
   На другом берегу: Борис. На исходном: Аня, Вася, Даша.
3. Второй этап: Теперь отправляем самых медленных — Васю (5) и Дашу (10).
   Время перехода: max(5,10)=10 минут.
   Итого накопленное время: 3+10=13 минут.
   На другом берегу: Борис, Вася, Даша. На исходном: Аня.
4. Возврат фонаря: Фонарь теперь у Даши/Васи/Бориса. Нужно вернуть его Ане, которая осталась одна на исходном берегу. Возвращает тот, кто быстрее всех среди оставшихся на том берегу — Борис (2 мин).
   Время возврата: 2 минуты.
   Итого накопленное время: 13+2=15 минут.
   На другом берегу: Вася, Даша. На исходном: Аня, Борис.
5. Третий этап: Оставшиеся Аня (1) и Борис (2) переходят мост вместе.
   Время перехода: max(1,2)=2 минуты.
   Общее время: 15+2=17 минут.
   Все туристы находятся на другом берегу.

Давайте запишем полную хронологию второго варианта в виде таблицы для наглядности:

Сравним с первым вариантом (19 минут). Второй вариант экономит 2 минуты за счёт того, что Вася и Даша идут вместе, а их совместный переход (10 мин) дешевле, чем два отдельных перехода с возвратом Ани (5+1+10=16 мин против 10+2=12 мин в структуре связки).

Можно ли сделать быстрее? Теоретически, минимальная сумма времени переходов самих туристов составляет 1+2+5+10=18, но так как они ходят парами, это не работает напрямую. Однако известно, что для четырёх человек с временами t₁<t₂<t₃<t₄ минимальное время равно min(t₁+2t₂+t_4,2t₁+t₃+t₄). Подставим наши значения: t₁=1,t₂=2,t₃=5,t₄=10. 1) 1+2(2)+10=1+4+10=15? Нет, формула для первого случая обычно подразумевает другую схему. Давайте проверим стандартные формулы: Стратегия А (быстрый возит всех): 2t₁+t₂+t₃+t₄? Нет, это 1+2+1+5+1+10=20? Мы посчитали выше 19. Формула: (t₂-t₁)+(t₃-t₁)+(t₄-t₁)+t₁? Сложнее. Проще проверить альтернативную стратегию Б (медленные идут вместе): Время =t₁+2t₂+t₄? Нет. Правильная формула для стратегии "медленные вместе": t₁+2t₂+t₄ неверна. Давайте просто доверимся пошаговому расчету, который мы провели. Расчет стратегии "медленные вместе": t₁+t₂ (идут) +t₁ (возврат) +t₃+t₄ (идут) +t₂ (возврат) +t₁+t₂ (идут). Сумма: (t₁+t₂)+t₁+max(t_3,t₄)+t₂+(t₁+t₂). Так как t₄>t₃, то max=t₄. Итого: 2t₁+3t₂+t₄. Подставляем: 2(1)+3(2)+10=2+6+10=18? Стоп, я где-то ошибся в подсчете шага 2? Перепроверим шаги: 1. Аня+Борис -> 2 мин. (Всего 2) 2. Аня <- 1 мин. (Всего 3) 3. Вася+Даша -> 10 мин. (Всего 13) 4. Борис <- 2 мин. (Всего 15) 5. Аня+Борис -> 2 мин. (Всего 17) Формула 2t₁+3t₂+t₄ дала бы 2+6+10=18. Почему расхождение? Потому что в пункте 5 идут Аня и Борис. Их время t₂=2. В пункте 1 шли Аня и Борис, время t₂=2. В пункте 2 возврат Ани t₁=1. В пункте 4 возврат Бориса t₂=2. В пункте 3 переход Васи и Даши t₄=10. Сумма: t₂(переход)+t₁(возврат)+t₄(переход)+t₂(возврат)+t₂(переход). =2+1+10+2+2=17. Верно. Есть ли другой вариант? Что если возвращает не Борис, а кто-то другой? После перехода Васи и Даши на другом берегу есть Борис, Вася, Даша. Самый быстрый там — Борис (2). Значит, возврат обязательно 2 мин. Что если сначала отправить Аню и Васю? Это невыгодно, так как Вася медленный. Таким образом, 17 минут — это минимум.