Здравствуйте.
В продолжение тематики самостоятельного изучения схемотехники предлагаю вашему вниманию статью, связанную с синтезом автоматов на триггерах.
А начинается все так:
“Крестьянину нужно перевезти через реку волка, козу и капусту. Но лодка такова, что в ней может поместиться только крестьянин, а с ним или один волк, или одна коза, или одна капуста. Но если оставить волка с козой, то волк съест козу, а если оставить козу с капустой, то коза съест капусту. Как перевез свой груз крестьянин?”
Немного отвлечёмся от задачи и вспомним то, что мы уже знаем:
Итак. Есть 2 способа решить эту задачу:
Чтобы перейти от словесных описаний к таблицам, графам и схемам я предлагаю закодировать состояния игры следующим образом:
Выделим четыре двоичных разряда. Каждый разряд отвечает за то какие существа на каком береге реки находятся. Если в этом разряде хранится 1, то существо на первом (исходном) берегу, если 0 – на втором. Для наглядности продемонстрирую это на следующем рисунке:
Из условия задачи становится ясно, что без присмотра крестьянина находиться вместе не могут:
Значит, следующие четыре комбинации являются проигрышными:
Теперь, как мы все помним, нужно от словесного описания перейти к графичесому описанию — графу. Это должно быть не сложно.
Отметим начальное состояние Сст – с него наша игра будет начинаться и им же оканчиваться. Задумывается, что некая кнопка «СТАРТ» переводит автомат из состояния «0000» в состояние «1111». Обратите внимание на то, что так я кодирую выходные слова, а вот состояния придётся закодировать другим образом. Значит, придётся ввести комбинационную схему, которая будет заниматься формированием выходных слов.
Для управления крестьянином и остальными сущностями понадобятся четыре входных слова:
Итак. Входные и выходные слова названы, состояния обозначены. Граф автомата Мура. Приступим к рисованию:
Отразим эти два факта на графе:
Рассуждаем дальше:
Добавим это к нашему рисунку:
Пока всё нормально.
Теперь надо выбрать, кого везти на второй берег: капусту или волка. Неплохо было бы рассмотреть оба варианта (приведу рисунок частично, чтобы легче воспринималось):
То есть видно, что на первом берегу после этого перемещения останется либо капуста, либо волк.
Ну вот! Я же говорил, что это не сложно! Если продолжить рассуждения в том же ключе, то можно прийти вот к такой нехитрой схеме:
Обратите внимание: при попытке в 3, 4, 5 и 8 состояниях крестьянина уехать на другой берег, коза остаётся без присмотра рядом с волком или капустой, что чревато и ведёт к концу игры. Ну или просто посмотрите в таблицу недопустимых состояний выше. При попытке перейти на них игра оканчивается.
Теперь вспомним, как строятся таблицы переходов/выходов. Рекомендую открыть вот эту статью и посмотреть, если Вы вдруг забыли, а я просто приведу таблицу:
Ну вот. Теперь почти все готово к синтезу автомата на триггерах. Совсем скоро мы сможем поиграть в эту игрушку на эмуляторе, а затем и на собранной модели.
Вторую часть статьи намереваюсь опубликовать 14-15 июня.
В продолжение тематики самостоятельного изучения схемотехники предлагаю вашему вниманию статью, связанную с синтезом автоматов на триггерах.
А начинается все так:
“Крестьянину нужно перевезти через реку волка, козу и капусту. Но лодка такова, что в ней может поместиться только крестьянин, а с ним или один волк, или одна коза, или одна капуста. Но если оставить волка с козой, то волк съест козу, а если оставить козу с капустой, то коза съест капусту. Как перевез свой груз крестьянин?”
Немного отвлечёмся от задачи и вспомним то, что мы уже знаем:
Итак. Есть 2 способа решить эту задачу:
- Приходится начать с козы. Крестьянин, перевезши козу, возвращается и берет волка, которого перевозит на другой берег, где его и оставляет, но зато берет и везет обратно на первый берег козу. Здесь он оставляет ее и перевозит к волку капусту. Вслед затем, возвратившись, он перевозит козу, и переправа оканчивается благополучно.
- Вначале крестьянин опять-таки перевозит козу. Потом можно взять капусту, отвезти ее на другой берег, оставить там и вернуть на первый берег козу. Затем перевезти на другой берег волка, вернуться за козой и снова отвести ее на другой берег. В этом случае количество рейсов (7) точно такое же, как и в первом варианте.
Чтобы перейти от словесных описаний к таблицам, графам и схемам я предлагаю закодировать состояния игры следующим образом:
Выделим четыре двоичных разряда. Каждый разряд отвечает за то какие существа на каком береге реки находятся. Если в этом разряде хранится 1, то существо на первом (исходном) берегу, если 0 – на втором. Для наглядности продемонстрирую это на следующем рисунке:
Из условия задачи становится ясно, что без присмотра крестьянина находиться вместе не могут:
- Коза и капуста;
- Коза и волк.
Значит, следующие четыре комбинации являются проигрышными:
Теперь, как мы все помним, нужно от словесного описания перейти к графичесому описанию — графу. Это должно быть не сложно.
Отметим начальное состояние Сст – с него наша игра будет начинаться и им же оканчиваться. Задумывается, что некая кнопка «СТАРТ» переводит автомат из состояния «0000» в состояние «1111». Обратите внимание на то, что так я кодирую выходные слова, а вот состояния придётся закодировать другим образом. Значит, придётся ввести комбинационную схему, которая будет заниматься формированием выходных слов.
Для управления крестьянином и остальными сущностями понадобятся четыре входных слова:
Итак. Входные и выходные слова названы, состояния обозначены. Граф автомата Мура. Приступим к рисованию:
- Из нулевого состояния игра переводится в начальную позицию по приходу любого слова.
- Очевидно, что только тогда, когда крестьянин отвезёт козу первой (а1) игра может быть продолжена, иначе (а2, а3, а4) придётся начать всё с начала.
Отразим эти два факта на графе:
Рассуждаем дальше:
- Если сейчас подать на вход слова а2 или а3, то ясно, что крестьянин не сможет переправить волка или капусту, поэтому состояние игры не изменится. Однако он может отвезти козу обратно и игра вернётся в начальное состояние.
- Значит единственным не тупиковым действием будет возвращение крестьянина на первый берег.
Добавим это к нашему рисунку:
Пока всё нормально.
Теперь надо выбрать, кого везти на второй берег: капусту или волка. Неплохо было бы рассмотреть оба варианта (приведу рисунок частично, чтобы легче воспринималось):
То есть видно, что на первом берегу после этого перемещения останется либо капуста, либо волк.
Ну вот! Я же говорил, что это не сложно! Если продолжить рассуждения в том же ключе, то можно прийти вот к такой нехитрой схеме:
Обратите внимание: при попытке в 3, 4, 5 и 8 состояниях крестьянина уехать на другой берег, коза остаётся без присмотра рядом с волком или капустой, что чревато и ведёт к концу игры. Ну или просто посмотрите в таблицу недопустимых состояний выше. При попытке перейти на них игра оканчивается.
Теперь вспомним, как строятся таблицы переходов/выходов. Рекомендую открыть вот эту статью и посмотреть, если Вы вдруг забыли, а я просто приведу таблицу:
Ну вот. Теперь почти все готово к синтезу автомата на триггерах. Совсем скоро мы сможем поиграть в эту игрушку на эмуляторе, а затем и на собранной модели.
Вторую часть статьи намереваюсь опубликовать 14-15 июня.
