Учебник_Final

10.4.1. Постановка задачи и составление программы

Постановка задачи

1. Дан ребус: GERALD + DONALD = ROBERT.

2. В словах GERALD, DONALD и ROBERT вместо букв необходимо поставить цифры таким образом, чтобы получилось математически правильное выражение. Разным буквам должны соответствовать разные цифры.

3. Требуется написать программу решения ребуса.

Алгоритм решения

1. Рассмотрим первые разряды всех трех чисел. Считаем, что первый разряд − это единицы, второй разряд – это десятки, третий – сотни и т.д. Очевидно, что нахождение множества пар (буква–цифра), входящих в решение задачи, должно удовлетворять условию:

(((D + D) mod 10) = Т) & (D ? Т). (10.1)

2. Рассмотрим второй разряд совместно с первым. Необходимо подобрать такие числа L и R, чтобы остаток отделения суммы (L*10 + L*10 + D + D) на 100 был равен (R*10 + Т). При этом следует учесть, что L и R не равны между собой и не равны D и Т.

Таким образом, среди множества пар (буква–цифра), удовлетворяющих первому условию, необходимо найти такие, чтобы:

(((L*10 + L*10 + D + D) mod 100) = (R*10 + T))&(D?T?L?R). (10.2)

3. Продолжая действовать подобным образом, можно выписать конечное условие, которому должны удовлетворять пары (буква–цифра), входящие в решение данной задачи.

Решение задачи

Сформулируем описанный выше подход к решению в терминах CLIPS.

Представим комбинации из одной буквы и одной цифры в виде фактов:

(combination D 0), (combination D 1), (combination A 1) и т.д.

В первую очередь составим правило для нахождения комбинаций (буква- цифра), удовлетворяющих условию (10.1):

(defrule find_solution

(combination D ?d)

(combination T ?t&~?d)

(test (= (mod (+ ?d ?d) 10) ?t))

(printout t "A solution is:" t t)

(printout t " D = " ?d t)

(printout t " T = " ?t t))

Данное правило выполнимо только в том случае, если в списке фактов существуют факты, удовлетворяющие условиям:

(combination D ?d) – все факты, в которых в первой и во второй позициях стоят «combination» и «D» соответственно, а в третьей позиции любое значение, это значение присваивается переменной ?d.
(combination Т ?t&~?d) – все факты, в которых в первой и во второй позициях стоят «combination» и «Т» соответственно, а в третьей позиции − любое значение, только не то, которое было присвоено переменной ?d, это значение присваивается переменной ?t. Знак «&» означает логическое «и» (and), а знак «~» – логическое «не» (not). Выражение «?t&~?d» означает, что переменная ?t может принимать значение, не равное значению переменной ?d.
(test (= (mod (+ ?d ?d) 10) ?t)) – это условие проверяет на равенство два выражения (mod (+ ?d ?d) 10) и (?t)).

Команда (printout t "A solution is:" t t) выводит на экран информацию, которая указывается после команды в полях, разделенных пробелами. Чтобы вывести текст, его необходимо заключить в кавычки, а перед кавычками поставить букву t. Эта буква указывает, что в следующем поле находится текст, взятый в кавычки, и который необходимо напечатать. Если после буквы t нет текста в кавычках, то происходит перевод курсора на новую строку.

Перевести курсор на новую строку можно путем указания комбинации символов «crlf» без кавычек. Для вывода значения переменной необходимо просто указать ее имя.

Пример.

printout t " Т = " ?t t)

Оператор выводит текст Т= и значение переменной ?t, а затем переводит курсор на новую строку.

Рассмотренное правило позволяет найти все комбинации (буква–цифра), удовлетворяющие условию для первых разрядов трех чисел. По аналогии с этим правилом составим конечное правило для нахождения решения:

(defrule find-solution

(combination D ?d)

(combination T ?t'&~?d)

(test (= (mod (+ ?d ?d) 10) ?t))

(combination L ?l&~?d&~?t)

(combination R ?r&~?d&~?t&~?l)

(test (= (mod (+ ?d ?d (* 10 ?1) (* 10 ?l) ?t)) 100)

(combination A ?a&~?d&~?t&~?l&~?r)

(combination E ?e&~?d&~?t&~?l&~?r&

(test (= (mod (+ ?d ?d (* 10 ?1) ((* 100 ?a) (* 100 ?a)) 1000)

(+ (* 100 ?e) (* 10 ?r) ?t)))

(combination N ?n&~?d&~?t&~?i&~?r&~?a&~?&e)

(combination В ?b&~?d&~?t&~?l&~?r&~?a&~?&e~?&n)

(test ( = (mod (+ ?d ?d (* 10 ?1) (* 10 ?l)

(* 100 ?a) (* 100 ?a) (* 1000 ?r) (*1000 ?n)) 10000)

(+ (* 1000 ?b) (* 100 ?e)(* 10 ?r) ?t)

(combination 0 ?o&~?d&~?t&~?l~?r&~?а&~?е&~?n&~?b)

(combination G ?g&~?d&~?t&~?l&~?&~?а&~?е&~?n&~?b~?о)

(test(=(+ ?d ?d

(* 10 ?l)(*10 ?l)

(* 100 ?а) {* 100 ?а)

(* 1000 ?r) (* 1000 ?n)

(10000 ?е) (* 10000 ?о)

(* 100000 ?q) (* 100000 ?d))

(+(*100000 ?r)(* 10000 ?о) (* 1000 ?b)(* 100 ?е)(* 10 ?r) ?t)))

(printout t "A solution is: " t)

(printout t "G = " ?g t)

(printout t "E = " ?e t)

(printout t "R = " ?r t)

(printout t "A = " ?а t)

(printout t "L = " ?l t)

(printout t "D = " ?d t)

(printout t "O = " ?o t)

printout t "N = " ?n t)

(printout t "B = " ?b t)

(printout t "T = " ?t t)

(printout t " " ?g ?e ?r ?a ?l ?d t)

(printout t "+" ?d ?o ?n ?a ?l ?d t)

(printout t " " "---------" t)

(printout t " = " ?r ?o ?b ?e ?r ?t t t)

Теперь для поиска решения остается занести факты, соответствующие комбинациям из одной буквы и одной цифры, в список фактов. Это можно сделать командой assert.

(assert (combination D 0) (combination D 1)

(combination A 1)

(combination L 9)

...)

Однако, т.к. количество фактов равно 100, лучше поступить по-другому. Сопоставим буквам и цифрам следующие факты:

(number 0), (number 1), (number 2), … , (number 9), (letter G), (letter E), (letter R), (Letter A), (letter L), (letter D), (letter O),(Letter N), (letter B), (letter T).

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

(defrule generate_combination

(number ?x)

(letter ?y)

(assert (combination (?y ?x))))

Согласно данному правилу, если в списке фактов присутствуют факты, имеющие вид (number ?x), (letter ?y), где вместо переменных стоят вполне конкретные значения, в список фактов добавляется еще один факт − (combination ?y ?х), в котором вместо переменных стоят значения из фактов.

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

(defrule startup

(printout t t "The problem is" t t)

(printout t " GERALD" t)

(printout t "+ DONALD" t)

(printout t "------------" t)

(printout t " = ROBERT" t t)

(assert

(number 0) (number 1) (number 2) (number 3) (number 4)

(number 5) (number 6) (number 7) (number 8) (number 9)

(letter G) (letter E) (letter R) (letter A) (letter L)

(letter D) (letter O) (letter N) (letter B) (letter T)))

Таким образом, рассмотренная программа состоит из трех правил: startup, generate_combination и find_solution. Первое из них выводит на экран условие задачи и добавляет в список факты, соответствующие отдельным буквам и цифрам. Второе правило, используя факты, введенные в список фактов первым правилом, заносит в список фактов факты, которые представляют собой всевозможные комбинации из десяти цифр и десяти букв. Третье правило позволяет найти среди этих фактов те, которые удовлетворяют условию задачи, и выводит на экран полученное решение.

Перейдем к порядку выполнения разработанной программы в ИО CLIPS.

Содержание