@Memex

Приветствую. На досуге подумал об одной программе. Мои слабые знания не позволяют пока её реализовать. Если кто-нибудь хочет потренировать мозги, милости прошу. Суть такова:

Имеются три барьера, расположенных один за другим в виде массива 3х4.

Третий барьер
((Сегмент-1) (Сегмент-2) (Сегмент-3) (Сегмент-4))
Второй барьер
((Сегмент-1) (Сегмент-2) (Сегмент-3) (Сегмент-4))
Первый барьер
((Сегмент-1) (Сегмент-2) (Сегмент-3) (Сегмент-4))

Программа-взломщик должна проникнуть через все три барьера. Атака начинается с первого барьера. Для проникновения через барьер достаточно взломать один сегмент барьера. Но чтобы взломать сегмент, программа должна ответить на несложный вопрос из области математической логики.

Пример: ? (not (and (or T NIL)
(and T T)
(not (or (and NIL T)
(or T T)))))

Сегмент может иметь либо один фиксированный вопрос, либо выбирать случайным образом вопрос из набора, либо задавать каждый раз новый уникальный вопрос, используя функцию генерации случайных логических вопросов (ещё одна весьма нетривиальная задача).

Сложность вопросов может повышаться от барьера к барьеру, а может и не повышаться.

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

Допустим:

(and (not (or T NIL))
(and T T))

Сперва программа ищет самые "глубокие" логические выражения:

(and T T) и (or T NIL)

Затем программа разбивает выражение на элементы. Программа имеет в своём распоряжении набор правил. Программа знает, что первый элемент выражения всегда есть логический оператор, а второй и опциональный третий элементы есть аргументы. Программа представляет выражения для себя в виде списка. Если первый элемент списка представляет, допустим, атом AND, то выражение вычисляется согласно этому правилу, иначе проводится проверка на другие логические операторы. Представим, что программа вычислила значения двух самых глубоких выражений. Теперь вопрос для неё представляется в таком виде:

(and (not T) T)

Снова вычисляется самое глубоко вложенное выражение:

(and NIL T)

NIL - вопрос решён.

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

Интерфейс программы. Программа сперва выводит начальное состояние массива. Затем она последовательно описывает шаги своей работы и выводит вопрос, который она решила и номер взломанного сегмента. После взлома всех трёх барьеров выводится конечное состояние массива. Если программа по каким-либо причинам не смогла взломать сегмент, то выводится сообщение об ошибке.


По моим представлениям, работа программы должна выглядеть так:

Ух. Вроде всё.

Добавлено через 9 минут
Эх, напортачил с примерами, а форум не даёт сделать правку. Должно выглядеть так:

Пример:

И второе выражение:

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

0

@Catstail

Постарайтесь четче сформулировать проблему. Что, собственно, нужно сделать?

0

@castorsky

Memex, А что собственно требуется от программы? T, nil как константы редко используются, как правило это результат вычисления выражения. Т.е. программа, на основе имеющихся простеньких логических функций, в виде барьеров должна сгенерировать логичесоке выражение? Все представленные Вами операции за исключением инверсии бинарные, следовательно выражений, должно быть "два штука" для подстановки? Но это же элементарные таблицы истинности и двоичные векторы. Присоединяюсь, в чем собственно вопрос?

0

@Memex

Да, извиняюсь, я весьма размыто сформулировал задачу. В общем, программа-взломщик получает логическое выражение, которое связано с определённым значениям массива, а затем решает его. Работает она с этим выражением, как с набором вложенных списков, начиная вычисление с самых глубоко вложенных списков. Дело в том, что программа не должна просто извлекать выражение и вбивать его в интерпретатор для получения ответа, а должна сама распознавать значения логических операторов, используя не заранее заданные в языке правила, а собственный набор вручную написанных правил. Программа также должна уметь оценивать сложность задаваемого ей вопроса.

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

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

Самой сложной задачей для меня является не обозначение правил, а реализация алгоритма вычисления и генератор случайных логических выражений.

0