Читать онлайн «Задачи на переправу. Моделирование, Алгоритмы»

Паньгин Андрей Александрович, Паньгин Александр Викторович ЗАДАЧИ НА ПЕРЕПРАВУ. МОДЕЛИРОВАНИЕ. АЛГОРИТМЫ Аннотация Рассматривается широкий класс задач на переправу с учетом различных ограничений на связи между персонажами. С помощью графов представлены алгоритмы решения, реализованные программно на алгоритмическом языке Pascal и в электронных таблицах Excel. Ключевые слова: задачи на переправу, поиск в ширину на графе, моделирование в MS Excel. ПОСТАНОВКА ЗАДАЧИ Задачи данного типа обычно используются для развития алгоритмического стиля мышления школьников (в игровой форме). В коллекции цифровых образовательных ресурсов (ЦОР) [1] в состав информационного источника сложной структуры (ИИСС) «Математика на компьютерах» входит имитационная модель переправы с конструктором задач и заданием различных ограничений на связи между персонажами (рис. 1). Эти ограничения могут быть следующего вида: - задание грузоподъемности или вместимости лодки; - присутствие лодочника; - отдельный персонаж «конфликтует» с другим персонажем или объектом («коза- капуста»); - отдельный персонаж «конфликтует» с другим персонажем без присутствия (или при присутствии) третьего типа персонажа («муж-жена», «рыцарь-оруженосец»); - количество одного типа персонажей больше количества другого типа персонажей («разбойники-купцы»). Примеры задач на переправу, представленные в сборнике [2], демонстрируют отдельные логические приемы для ограниченного количества персонажей. В этой статье сделан подход к формализации данного типа задач и программного получения решения с учетом снятия этих ограничений. В качестве модели переправы рассматривается граф состояний, а за решение задачи принимается кратчайший путь на этом графе из начального состояния, где все персонажи располагаются на одном берегу, в конечное состояние, где все персонажи находятся на противоположном берегу. ОПРЕДЕЛЕНИЯ И ОБОЗНАЧЕНИЯ Персонаж - любой субъект действия или предмет, который может участвовать в переправе с одного берега на другой: например, волк, коза или капуста. Отдельным персонажем, всегда присутствующим в любой задаче на переправу, является лодка. В некоторых © А. А. Паньгин, А. В. Паньгин, 2010 54 Задачи на переправу. Моделирование. Алгоритмы задачах подразумевается, что лодка управляется лодочником. Это означает, что персонаж «лодка» может переплывать реку самостоятельно, без участия других персонажей. Несколько персонажей могут быть однотипными. В этом случае одному наименованию сопоставляется некоторое количество персонажей данного типа, например, два солдата. N - количество различных типов персонажей. В задаче про волка, козу и капусту N = 4 (лодка - еще один тип персонажа, который всегда присутствует в количестве 1 шт. ). Ci - количество персонажей /-го типа. Левый берег - берег реки, на котором находятся все персонажи до начала переправы. Правый берег - противоположный берег, куда необходимо переправить всех персонажей. Состояние - набор V = (Ар А2, ... , AN\ где Ai - количество персонажей /-го типа, находящихся в указанный момент на левом берегу.