Задачи о переправах

Переправа, переправа!
Берег левый, берег правый…

А.Т. Твардовский «Василий Тёркин»

Почему и как, решая задачи о переправах, мы развиваем алгоритмическое мышление?

Читаем учебник и играем в игры!


Дочери и отцы
Священники и дьяволы
Животные и детёныши
Семейство Смит
Японское семейство, полицейский и преступник

Информатика. Алгоритмика. 6 класс. Сергей Ландо, Александр Звонкин | Купить школьный учебник в книжном интернет-магазине OZON.ru | 5-09-014569-5 Информатика. Алгоритмика. 6 класс. Сергей Ландо, Александр Звонкин | Купить школьный учебник в книжном интернет-магазине OZON.ru | 5-09-014569-5

Как облегчить себе программирование

И если мы хотим облегчить себе написание программы и удостовериться в том, что она работает правильно, то нам нужен инструмент для её проверки — шаг за шагом от начала и до конца.

К счастью, ясно, что это за инструмент. Быть может, вы изобрели его самостоятельно до того, как начали читать этот параграф. Нам всего лишь нужно записывать состояния всех объектов до и после выполнения каждой команды.

Команда Крестьянин с лодкой Волк Коза Капуста
0 левый берег левый берег левый берег левый берег
1 перевези козу правый берег левый берег правый берег левый берег
2 переправься левый берегй левый берег правый берег левый берег
3 перевези волка правый берег правый берег правый берег левый берег
4 перевези козу левый берег правый берег левый берег левый берег
5 перевези капусту правый берег правый берег левый берег правый берег
6 переправься левый берег правый берег левый берег правый берег
7 перевези козу правый берег правый берег правый берег правый берег

Упражнение

Проверьте все шаги программы.

Три рыцаря с тремя оруженосцами подошли к реке. Они нашли маленькую лодку, в которой через реку могут переехать только два человека. Каждый оруженосец так предан своему хозяину, что он отказывается оставаться на берегу или в лодке с другими рыцарями в отсутствие хозяина. (Но он готов быть один или с другими оруженосцами.) Как они вшестером могут переправиться через реку?

Придумайте систему команд для Исполнителя в данной задаче. Напишите в этой системе команд программу, решающую поставленную задачу. Нарисуйте таблицу состояний при исполнении программы и заполните её.

Напомним, что надо соблюдать следующие правила:

  • в лодке могут находиться не больше двух человек;
  • в лодке не может оказаться оруженосец с чужим рыцарем;
  • если на берегу вместе с оруженосцем есть чужой рыцарь, то должен быть и его (оруженосца) рыцарь.

Для проверки соблюдения первых двух правил достаточно просмотреть саму программу. Но чтобы убедиться, что не нарушено последнее правило, нужна таблица.

Профессиональные программисты при написании программ вставляют в них утверждения о состоянии программы. Они помогают программисту удостовериться в том, что программа работает как положено, и позволяют доказывать правильность программы.

Иногда это кажется обременительным. (Любая дисциплина обременительна, не правда ли?) Но у программистов очень уважаемая работа. В наши дни компьютеры управляют самолётами и атомными электростанциями, помогают врачам при хирургических операциях, выполняют много других важных дел. Нужно быть твёрдо уверенными в том, что программы работают правильно. И один из самых могущественных способов достижения такой уверенности — дисциплина программирования.