ГДЗ по информатике, 6 класс, Босова, номер 17.10: Типы алгоритмов

У нас есть:

• 40 солдат;
• 2 мальчика;
• Лодка вмещает либо 1 солдата, либо 2 мальчиков.

Важно: если в лодке едет один солдат, он не может вернуться обратно сам, так как ему нужно оставить лодку на том берегу или привезти её назад? Нет, задача классическая: лодка должна быть возвращена к исходному берегу для следующего пассажира. Солдат не может управлять лодкой в одиночку при возврате, если только он не единственный пассажир туда-обратно, но тогда он просто вернётся. Однако условие говорит: «Лодка вмещает либо одного солдата, либо двух мальчиков». Это означает, что комбинация «солдат + мальчик» невозможна из-за веса или вместимости. Значит, чтобы переправить солдата, лодка должна прийти к нему пустой (или с мальчиками?), а после того как солдат сядет, лодка уйдёт. Но кто приведёт лодку обратно?

Разберём цикл переправки одного солдата:

1. Два мальчика плывут на другой берег (2 чел.).
2. Один мальчик остаётся там, второй возвращается с лодкой (1 чел.).
3. Теперь на первом берегу есть лодка и 39 солдат (плюс тот, кого будем переправлять). На втором берегу — 1 мальчик.
4. Солдат садится в лодку и плывёт на другой берег (1 чел.).
5. На другом берегу теперь: 1 мальчик (который ждал) + 1 солдат. Лодка у солдата. Солдат выходит на берег. Кто заберёт лодку обратно? Тот мальчик, который был на другом берегу!
6. Мальчик садится в лодку и возвращается на первый берег (1 чел.).

Итого, после этого цикла: солдат переправлен, лодка снова на первом берегу, оба мальчика снова на первом берегу (один вернулся, второй был там всё время? Нет, давайте проверим позиции).

Давайте проследим за мальчиками точнее:

• Начало: Оба мальчика на берегу А.
• 1. Мальчики плывут А -> Б. (Берег А: 0 мальчиков, Берег Б: 2 мальчика)
• 2. Один мальчик плывёт Б -> А. (Берег А: 1 мальчик, Берег Б: 1 мальчик)
• 3. Солдат плывёт А -> Б. (Берег А: 1 мальчик, Берег Б: 1 мальчик + 1 солдат)
• 4. Мальчик с берега Б плывёт Б -> А. (Берег А: 2 мальчика, Берег Б: 1 солдат)

Результат цикла: 1 солдат на берегу Б, 2 мальчика на берегу А, лодка на берегу А. Состояние системы аналогично начальному, минус один солдат. Этот цикл можно повторять.

Группа действий (цикл):

1. Два мальчика переплывают реку.
2. Один мальчик возвращается.
3. Один солдат переплывает реку.
4. Мальчик (находящийся на противоположном берегу) возвращается.

Количество повторений:

Так как всего нужно переправить 40 солдат, и каждый цикл переправляет ровно 1 солдата, то этот алгоритм необходимо выполнить 40 раз.

После того как 40 циклов будут выполнены:

• Все 40 солдат находятся на берегу Б.
• Оба мальчика находятся на берегу А.
• Лодка находится на берегу А.

Чтобы все оказались на одном берегу (обычно подразумевается, что задача решена, когда все переправились, включая детей, или же дети остаются помогать, но стандартная формулировка «Как переправиться всем?» подразумевает, что и мальчики тоже должны оказаться на другом берегу, либо это финальное состояние считается успешным для солдат, а мальчики свободны. Однако, чаще всего в таких задачах требуется, чтобы все участники оказались на другом берегу. Если мальчики должны тоже переправиться, то после 40 циклов они на берегу А. Им нужно просто вместе переплыть на берег Б.

Но давайте посмотрим на вопрос: «Определить группу действий и количество повторений». Обычно под «повторениями» понимается основной цикл работы с солдатами. Переправа мальчиков в конце — это завершающее действие, не входящее в повторяющийся цикл переправки солдат.

Если считать, что «всем» включает и мальчиков, то алгоритм таков:

1. Выполнить цикл переправки одного солдата 40 раз.
2. Два мальчика переплывают реку в последний раз.

Однако, ключевая часть задачи — именно механизм переправки солдат. Группа действий для каждого солдата состоит из 4 шагов. Количество повторений этой группы — 40.