Каннибал мен миссионерлер
жүктеу/скачать 38,44 Kb.
|
Каннибал мен миссионерлер
|
Каннибал мен миссионерлер РЕФАЛ является таким языком, который ориентирован на конструирование определенных объектов , представленных РЕФАЛ-выражениями, и на манипулирование ими. Структура управления РЕФАЛ-программы весьма проста и незамысловата: сопоставление в образцом и подстановка. Именно структура объектов, которыми манипулирует программа, несет бремя хранения всей полезной информации. Удачное программирование на РЕФАЛе - это прежде всего удачный выбор основных структур данных. Представление проблемы, которая должна быть решена, в терминах РЕФАЛ-выражений является первой и важнейшей частью программирования на РЕФАЛе. Это представление должно, во-первых, быть наглядным для человека, во-вторых, допускать выражение основных операций над данными в терминах трансформации объектов в соответствии с некоторыми простыми образцами. Если эти два требования удовлетворяются, у вас достаточно хорошие шансы написать РЕФАЛ-программу, которая будет компактной, читаемой, и в то же время легко отлаживаемой. Рассмотрим хорошо известную задачу "Миссионеры и каннибалы''. Три миссионера и три каннибала приходят на берег реки и видят лодку. Они хотят переплыть реку. Лодка, однако, не может вместить более двух человек. Дальнейшим ограничением является следующее. Ни в один момент времени число каннибалов на любом берегу реки (включая причалившую лодку) не должно превосходить число миссионеров (так как в этом случае миссионеров одолеют и съедят). Каким образом можно переплыть реку (если это вообще возможно ) ? Общий метод решения задачи таков: Определим множество возможных ситуаций, или состояний, подразумеваемых в задаче ( пространство состояний). Одно из состояний должно быть определено как заключительное. И должен существовать критерий, согласно которому состояние является допустимым решением задачи (достижение цели). Определим множество допустимых перемещений, которые можно совершать в направлении решения проблемы. Перемещение является операцией, которая трансформирует одно (текущее) состояние в другое (следующее) состояние. Как правило, не всякое перемещение допустимо в каждом состоянии, но для каждого состояния будет определено подмножество допустимых перемещений. Эти два множества определяют дерево достижимых состояний, корнем которого является начальное состояние. Теперь следует произвести поиск по этому графу, чтобы отыскать путь, который ведет к решению (если он вообще существует). Как будут представлены ситуации в нашей задаче? Подвыражения в РЕФАЛе представляют подсистемы в полной системе. Наша система очевидным образом включает две подсистемы людей: находящихся на левом и на правом берегу реки. Таким образом, можно использовать образец: жүктеу/скачать 38,44 Kb. Достарыңызбен бөлісу:
|