Чтение онлайн

(b) Крайние левые цифры D1, D2 и D, а также перенос С2 должны удовлетворять отношению, показанному на рис. 7.1: С2, D1 и D2 складываются, давая в результате D и перенос влево. Это условие в нашей программе формулируется в виде отношения суммацифр.

Переводя это на Пролог, получаем:

сумма1( [D1 | N1], [D2 | N2], [D | N], С1, С, Циф1, Циф) :-

сумма1( Nl, N2, N, С1, С2, Циф1, Циф2),

суммацифр( D1, D2, С2, D, С, Циф2, Циф).

Осталось только описать на Прологе отношение суммацифр. В его определении есть одна тонкая деталь, касающаяся применения металогического предиката nonvar. D1, D2 и D должны быть десятичными цифрами. Если хоть одна из этих переменных еще не конкретизирована, ее нужно конкретизировать какой-нибудь цифрой из списка Циф2. Как только такая конкретизация произошла, эту цифру нужно удалить из множества доступных цифр. Если D1, D2 и D уже конкретизированы, тогда, конечно, ни одна из доступных цифр "потрачена" не будет. В программе эти действия реализуются при помощи недетерминированного вычеркивания элемента списка. Если этот элемент - не переменная, ничего не вычеркивается (конкретизации не было). Вот эта программа:

удалить( Элемент, Список, Список) :-

nonvar( Элемент), !.

удалить( Элемент, [Элемент | Список ], Список).

удалить(Элемент, [А | Список], [А | Список1]) :-

удалить( Элемент, Список, Список1).

Полная программа для решения арифметических ребусов приводится на рис. 7.2. В программу включены также определения двух ребусов. Вопрос к пролог-системе для ребуса про DONALD'a, GERALD'a и ROBERT'a с использованием этой программы выглядит так:

?- ребус1( N1, N2, N), сумма( N1, N2, N).

% Решение числовых ребусов

сумма( N1, N2, N) :-

% Числа представлены в виде списков цифр

сумма1( N1, N2, N,

0, 0,

% Перенос справа и перенос влево равны 0

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9], _ ).

% Все цифры доступны

сумма1( [ ], [ ], [ ], 0, 0, Цифры, Цифры).

сумма1( [D1 | N1], [D2 | N2], [D | N], C1, С, Циф1, Циф) :-

сумма1( Nl, N2, N, C1, C2, Циф1, Циф2),

суммацифр( Dl, D2, C2, С, Циф2, Циф).

суммацифр( Dl, D2, C1, D, С, Циф1, Циф) :-

удалить( D1, Циф1, Циф2),

% Выбор доступной цифры для D1

удалить( D2, Циф2, Циф3),

% Выбор доступной цифры для D2

удалить( D, Циф3, Циф),

% Выбор доступной цифры для D

S is D1 + D2 + C1,

D is S mod 10,

С is S div 10.

удалить( A, L, L) :-

nonvar( A), !.

% Переменная А уже конкретизирована

удалить( А, [А | L], L).

удалить( А, [В | L], [В | L1]) :-

удалить( A, L, L1).

% Примеры ребусов

ребус1( [D, O, N, A, L, D],

[G, E, R, A, L, D],

[R, O, B, E, R, T].

ребус2( [0, S, E, N, D],

[0, M, O, R, E],

[M, O, N, E, Y].

Рис. 7. 2. Программа для арифметических ребусов.

Иногда этот ребус упрощают, сообщая часть решения в виде дополнительного ограничения, например D равно 5. В такой форме ребус можно передать пролог-системе при помощи сумма1:

?
– сумма1( [5, O, N, A, L, 5],

[G, E, R, A, L, 5],

[R, O, B, E, R, T],

0, 0, [0, 1, 2, 3, 4, 6, 7, 8, 9], _ ).

Интересно, что в обоих случаях существует только одно решение, т.е. только один способ заменить буквы цифрами.

Упражнения

7. 1. Напишите процедуру упростить для упрощения алгебраических сумм, в которых участвуют числа и символы (строчные буквы). Пусть эта процедура переупорядочивает слагаемые так, чтобы символы предшествовали числам. Вот примеры ее использования:

?- упростить( 1 + 1 + а, Е).

Е = а + 2

?- упростить( l + a + 4 + 2 + b + с, E).

Е = а + b + с + 7