последнем примере как X, так и Y после конкретизации получили значение
а
, и поэтому Nb оказалось равным только 1, однако мы хотели не этого. Нас интересовало количество реальных появлений конкретного атома, а вовсе не число термов, сопоставимых с этим атомом. В соответствии с этим более точным определением отношения
счетчик
мы должны теперь проверять, является ли голова списка атомом. Усовершенствованная программа выглядит так:
счетчик( _, [], 0).
счетчик( А, [В | L], N) :-
atom( В), А = В, !, % B равно атому А?
счетчик( A, L, N1), % Подсчет в хвосте
N is N1 + 1;
счетчик( А, L, N).
% Иначе - подсчитать только в хвосте
В следующем более сложном упражнении по программированию числовых ребусов используется предикат
nonvar
.
7.1.2. Решение числового ребуса с использованием nonvar
Известным примером числового ребуса является
D O N A L D
+
G E R A L D
– ----------
R O B E R T
Задача состоит в том. чтобы заменить буквы D, О, N и т.д. на цифры таким образом, чтобы вышеприведенная сумма была правильной. Разным буквам должны соответствовать разные цифры, иначе возможно тривиальное решение, например, все буквы можно заменить на нули.
Определим отношение
сумма( N1, N2, N)
где N1, N2 и N представляют три числа данного ребуса. Цель
cyммa(N1, N2, N)
достигается, если существует такая замена букв цифрами, что N1+N2 = N.
Первым шагом к решению будет выбор представления чисел N1, N2 и N в программе. Один из способов - представить каждое число в виде списка его цифр. Например, число 255 будет тогда представляться списком [2, 2, 5]. Поскольку значения цифр нам не известны заранее, каждая цифра будет обозначаться соответствующей неинициализированной переменной. Используя это представление, мы можем сформулировать задачу так:
[ D, O, N, A, L, D ]
+ [ G, E, R, A, L, D ]
= [ R, О, B, E, R, T ]
Теперь задача состоит в том. чтобы найти такую конкретизацию переменных D, О, N и т.д., для которой сумма верна. После того, как отношение
сумма
будет запрограммировано,
задание для пролог-системы на решение ребуса будет иметь вид
?- сумма( [D, O, N, A, L, D], [G, E, R, A, L, D],
[R, O, В, E, R, T ).
Рис. 7.1. Поразрядное сложение. Отношения в показанном i-м разряде такие: D3i = (C1 + D1i + D2i) mod 10; C = (C1 + D1i + D2i) div 10 (div — целочисленное деление, mod — остаток от деления).
Для определения отношения
сумма
над списками цифр нам нужно запрограммировать реальные правила суммирования в десятичной системе счисления. Суммирование производится цифра за цифрой, начиная с младших цифр в сторону старших, всякий раз учитывая цифру переноса справа. Необходимо также сохранять множество допустимых цифр, т.е. цифр, которые еще не были использованы для конкретизации уже встретившихся переменных. Поэтому, вообще говоря, кроме трех чисел N1, N2 и N в рассмотрении должна участвовать некоторая дополнительная информация, как показано на рис. 7.1:
• перенос перед сложением
• перенос после сложения
• множество цифр, доступных перед сложением
• оставшиеся цифры, не использованные при сложении
Для формулировки отношения
сумма
мы снова воспользуемся принципом обобщения задачи: введем вспомогательное, более общее отношение
сумма1
. Это отношение будет иметь несколько дополнительных аргументов, соответствующих той дополнительной информации, о которой говорилось выше:
сумма1( N1, N2, N, C1, С, Цифры1, Цифры)
Здесь N1, N2 и N — наши три числа, как и в отношении сумма, C1 — перенос справа (до сложения N1 и N2), а С — перенос влево (после сложения). Пример:
?- сумма1( [H, E], [6, E], [U, S], 1, 1,
[1, 3, 4, 7, 8, 9], Цифры ).
H = 8
E = 3
S = 7
U = 4
Цифры = [1, 9]
Если N1 и N удовлетворяют отношению
сумма
, то, как показано на рис. 7.1, C1 и С должны быть равны 0.
Цифры1
— список цифр, которые не были использованы для конкретизации переменных. Поскольку мы допускаем использование в отношении
Бремя решения задачи переложено теперь на отношение
сумма1
. Но это отношение является уже достаточно общим, чтобы можно было определить его рекурсивно. Без ограничения общности мы предположим, что все три списка, представляющие три числа, имеют одинаковую длину. Наш пример, конечно, удовлетворяет этому условию, но если это не так, то всегда можно приписать слева нужное количество нулей к более "короткому" числу.