Нижегородский государственный технический университет
им.
Системы искусственного интеллекта
Лабораторная работа
Вариант №13
Выполнил студент группы М14-ИВТ-3:
Проверил:
г. Нижний Новгород
2014 г.
Задание:
Сложение двух чисел столбиком. Несколько или все цифры в слагаемых и в сумме зашифрованы символами. Требуется определить каким символом, какая цифра зашифрована. Один и тот же символ не может шифровать разные цифры одновременно. Одна и та же цифра не может быть зашифрована разными символами.
Пример:
DONALD 526485
+ +
GERALD 197485
ROBERT 723970
Ход работы:
В задании требуется определить значения каждого символа, причем одинаковый символ соответствует одинаковой цифре. Следовательно, зная, что цифр всего 10 (0 - 9), можно выставить набор используемых или оставшихся цифр для использования как ограничение. Отсюда же следует, что имеет смысл создать структуру для каждого символа, связывающего его с цифрой. Стоит учесть, что работа со слагаемыми и суммой будет происходить посимвольно, значит, для простоты следует использовать списки символов для слагаемых и суммы.
Входные данные, а это оба слагаемых и сумма в виде набора символов, должны быть переданы программе в определенном виде. Так, например слагаемое DONALD, должно быть передано как [“d”,”o”,”n”,”a”,”l”,”d”].
Основной предикат «симв_сумма» работает поочередно с каждой тройкой символов стоящих в одном столбце, при записи выражения «столбиком», начиная справа, т. е. с младших разрядов. Таким образом, для текущего примера поочередно перебираются сначала символы D, D,T, затем L, L,R и т. д. Вначале выбираются цифры из списка оставшихся возможных цифр для символов слагаемых с использованием предиката «выбор» и списка связей, если уже есть определенная цифра для данного символа. Далее вычисляется сумма разряда и устанавливается переполнение. Следующим шагом выбирается цифра для суммы аналогичным образом, что и для слагаемого.
Так программа выполняется для каждой тройки символов, учитывая правильность или неправильность варианта подстановки цифры, используя символы из суммы и список связей.
Результат работы программы
Для демонстрации работы программы используем пример из задания.
Как видно, найденные числа совпадают с указанными в задании.
Если попробовать ввести другие слагаемые, то, если ответ не будет найден, программа завершит работу.
Листинг.
Использованная при разработке среда - Visual Prolog 5.2
/*Сложение двух чисел столбиком. Несколько или все цифры в слагаемых и в сумме зашифрованы символами.
Требуется определить каким символом, какая цифра зашифрована.
Один и тот же символ не может шифровать разные цифры одновременно.
Одна и та же цифра не может быть зашифрована разными символами.*/
Domains
буква = SYMBOL
цифра = INTEGER
строка = STRING
список_букв = буква* %список введенных символов
связь = св(буква, цифра) %отображает связь между символом и цифрой
список_связей = связь* %список всех связей
список_цифр = цифра* %список возможных цифр(от 0 до 9)
Predicates
nondeterm симв_сумма (
список_букв Число1,
список_букв Число2,
список_букв СуммаЧисел,
цифра Переполнение,
список_связей НеИспользСпСв,
список_связей ИспользСпСв,
список_цифр ВозможныеЦифры,
список_связей ОсталисьНеИспользСпСв,
список_связей ОсталисьИспользСпСв,
список_цифр ОставшиесяВозможныеЦифры
)
determ разр_сумма (
цифра Цифра1,
цифра Цифра2,
цифра Переполнение0,
цифра Сумма,
цифра Переполнение
)
nondeterm выбор (
буква Символ,
список_связей НеИспользСпСв,
список_связей ИспользСпСв,
список_цифр ВозможныеЦифры,
цифра Цифра,
список_связей ОсталисьНеИспользСпСв,
список_связей НовыеИспользСпСв,
список_цифр ОставшиесяВозможныеЦифры
)
nondeterm соединение (
связь Связь,
список_связей СписокСвязей,
список_связей ОсташийсяСписокСвязей
)
nondeterm соединение (
цифра Цифра,
список_цифр ВозможныеЦифры,
список_цифр ОставшиесяВозможныеЦифры
)
nondeterm соединение (
буква Символ,
список_букв СписокСимволов,
список_букв НовыйСписокСимволов
)
nondeterm append (
список_букв СписокСимволов_1,
список_букв СписокСимволов_2,
список_букв НовыйСписокСимволов
)
nondeterm получить_элемент (
список_букв СписокСимволов,
цифра Номер,
буква Элемент
)
nondeterm добавить_элемент_в_конец (
буква Элемент,
список_букв СписокСтарый,
список_букв СписокНовый
)
nondeterm создание_списка_связей (
список_букв СписокСимволов,
список_связей ДополнительныйСписокСвязей,
список_связей НовыйСписокСвязей
)
nondeterm вывод_результата (
список_букв СписокСимволов,
список_связей СписокСвязей
)
Clauses
симв_сумма([Символ1|ОстСимвол1], [Символ2|ОстСимвол2], [СимвольнаяСумма|ОстСимвольнаяСумма], Переполнение, НеИспользСпСв, ИспользСпСв, ВозможныеЦифры, ОсталисьНеИспользСпСв, ОсталисьИспользСпСв, ОставшиесяВозможныеЦифры):-
симв_сумма(ОстСимвол1, ОстСимвол2, ОстСимвольнаяСумма, ОстПереполнение, НеИспользСпСв, ИспользСпСв, ВозможныеЦифры, ОсталисьНеИспользСпСв_1, ОсталисьИспользСпСв_1, ОставшиесяВозможныеЦифры_1),
выбор(Символ1, ОсталисьНеИспользСпСв_1, ОсталисьИспользСпСв_1, ОставшиесяВозможныеЦифры_1, Цифра1, ОсталисьНеИспользСпСв_2, ОсталисьИспользСпСв_2, ОставшиесяВозможныеЦифры_2),
выбор(Символ2, ОсталисьНеИспользСпСв_2, ОсталисьИспользСпСв_2, ОставшиесяВозможныеЦифры_2, Цифра2, ОсталисьНеИспользСпСв_3, ОсталисьИспользСпСв_3, ОставшиесяВозможныеЦифры_3),
разр_сумма (Цифра1, Цифра2, ОстПереполнение, Сумма, Переполнение),
выбор(СимвольнаяСумма, ОсталисьНеИспользСпСв_3, ОсталисьИспользСпСв_3, ОставшиесяВозможныеЦифры_3, Сумма, ОсталисьНеИспользСпСв, ОсталисьИспользСпСв, ОставшиесяВозможныеЦифры).
симв_сумма([], [], [], 0, НеИспользСпСв, ИспользСпСв, ВозможныеЦифры, НеИспользСпСв, ИспользСпСв, ВозможныеЦифры).
разр_сумма(Цифра1, Цифра2, Переполнение, Сумма, 0):-
Сумма = Цифра1 + Цифра2 + Переполнение,
Сумма < 10,!.
разр_сумма(Цифра1, Цифра2, Переполнение, Сумма, 1):-
Сумма = Цифра1 + Цифра2 + Переполнение - 10.
выбор(Символ, НеИспользСпСв, ИспользСпСв, ВозможныеЦифры, Цифра, ОсталисьНеИспользСпСв, [св(Символ, Цифра)|ИспользСпСв], ОставшиесяВозможныеЦифры):-
соединение(св(Символ, Цифра), ОсталисьНеИспользСпСв, НеИспользСпСв),
соединение(Цифра, ОставшиесяВозможныеЦифры, ВозможныеЦифры).
выбор(Символ, НеИспользСпСв, ИспользСпСв, ВозможныеЦифры, Цифра, НеИспользСпСв, ИспользСпСв, ВозможныеЦифры):-
соединение(св(Символ, Цифра), _, ИспользСпСв).
соединение(Элемент, ОставшийсяСписок, [Элемент|ОставшийсяСписок]).
соединение(Элемент, [ПервыйЭлемент|НовыйОставшийсяСписок], [ПервыйЭлемент|ОставшийсяСписок]):-
соединение(Элемент, НовыйОставшийсяСписок, ОставшийсяСписок).
получить_элемент ([Голова|Хвост],1,Голова).
получить_элемент ([Голова|Хвост],Номер, Элемент):-
СледующийНомер=Номер-1,
получить_элемент (Хвост, СледующийНомер, Элемент).
добавить_элемент_в_конец (Элемент,[],[Элемент]).
добавить_элемент_в_конец (Элемент,[Голова|Хвост],[Голова|Хвост_1]):-
добавить_элемент_в_конец(Элемент, Хвост, Хвост_1).
append([], Список, Список).
append([Голова|Список_1], Список_2, [Голова|Список_3]):-
append(Список_1, Список_2, Список_3).
создание_списка_связей([], Отображение, Отображение).
создание_списка_связей([Символ| СимвОстаток], Дополнение, ПолноеОтображение):-
соединение(св(Символ,_), ОстДополнение, Дополнение),!,
создание_списка_связей(СимвОстаток, [св(Символ,_)|ОстДополнение], ПолноеОтображение).
создание_списка_связей([Символ| СимвОстаток], Дополнение, ПолноеОтображение):-
!,НовДополн = [св(Символ,_)|Дополнение],
создание_списка_связей(СимвОстаток, НовДополн, ПолноеОтображение).
вывод_результата([],_).
вывод_результата([Символ| Остаток], Отображение):-
соединение(св(Символ, Значение), _, Отображение),!,
write(Символ,"=",Значение),nl,
вывод_результата(Остаток, Отображение).
Goal
write("Введите первое слагаемое (в формате [\"d\",\"o\",\"n\",\"a\",\"l\",\"d\"]): "),nl,
readterm(список_букв, Слагаемое_1),
write(Слагаемое_1),nl,
write("Введите второе слагаемое (в формате [\"g\",\"e\",\"r\",\"a\",\"l\",\"d\"]): "),nl,
readterm(список_букв, Слагаемое_2),
write(Слагаемое_2),nl,
append(Слагаемое_1,Слагаемое_2,Слагаемые),
write("Введите сумму (в формате [\"r\",\"o\",\"b\",\"e\",\"r\",\"t\"]): "),nl,
readterm(список_букв, СуммаВБуквах),
write(СуммаВБуквах),nl,
append(СуммаВБуквах, Слагаемые, ВсеСимволы),
создание_списка_связей(ВсеСимволы, [], ВсеСвязи),
симв_сумма(Слагаемое_1, Слагаемое_2, СуммаВБуквах, 0, ВсеСвязи,[], [0,1,2,3,4,5,6,7,8,9], [], _, []),
write("Результат"),nl,
вывод_результата(ВсеСимволы, ВсеСвязи),
readchar( _),
readchar( _).
