Существует классическая задача:
Есть 2 емкости: 5 литров и 3 литра. Как отмерить 4 литра жидкости используя только эти 2 емкости?
В этом тексте я решу эту задачу в общем виде при помощи конечного автомата. Также я упомяну про малоизвестный язык программирования Dot. Методика конечного автомата хорошо изучена и поставлена на рельсы. Состоит из 3 фаз.
Фаза 1: перечислить все возможные состояния (комбинаторика)
Состояние определяется количеством жидкости в паре сосудов. Согласно комбинаторике по правилу умножения существует всего 24 состояния. Вот они все перечислены.
Фаза 2 перечислить все возможные входы. (из условий задачи)
Существует всего 5 легальных действий с бутылками. Вот их перечень.
Фаза 3 составить таблицу переходов
Этот пункт я пропущу так как таблица получится циклопических размеров. По правилу умножения 24*5=120 строк
Фаза 4 отрисовать граф состояний
Как гласит английская народная пословица “Картинка стоит тысячи слов” (A picture is worth a thousand words). Также мой универский профессор часто говорил, что инженеры - это про схемы. Поэтому представляю блок схему в виде ориентированного графа состояний для задачи про бутылки.
Я накропал на языке С консольную утилиту, которая прокручивает конечный автомат и сохраняет в файл составленный код на языке dot. Далее бесплатная утилита dot.exe поедает файл *.dot и преобразует его во всем известный *.svg файл. Наконец браузер chrom.exe поедает *.svg и отрисовывает в окне на мониторе.
Глядя на этот ориентированный граф становится очевидным, что чтобы отмерить 4 литра надо выполнить следующую процедуру из 6-ти инструкций:
есть еще одно решение
Easy!
Эта задача может служить отличной иллюстрацией для обучения теории конечных автоматов FSM. Конечные автоматы повсеместно используются в промышленной разработке, например, системного программного обеспечения.
Существует 8 недостижимых состояний: 1/5_1/3 1/5_2/3 2/5_1/3 2/5_2/3 3/5_1/3 3/5_2/3 4/5_1/3 4/5+2/3. В эти состояния никак не попасть как только не переливай содержимое сосудов.
Можно отмерить не только 4 лита, а все значения от 1 до 8 включительно.
вывод
Как видите, язык программирования Dot отлично подходит для автоматической отрисовки сложной векторной графики.
Буду признателен, если пришлете описания подобного рода логических задач в комментариях к тексту.
