Игорь Пашев - Наибольший общий делитель на Прологе (original) (raw)

03:55 pm - Наибольший общий делитель на Прологе

Введение

Со школьных времён я при изучении нового языка пишу на нём алгоритм Евклида для нахождения наибольшего общего делителя (НОД). Здесь — https://github.com/ip1981/GCD — я начал собирать коллекцию программ на разных языках. У них одна идея: программа ищет НОД для чисел, указанных в командной строке. Возможно, я добавлю чтение из файла, так как главная цель — не НОД, а возможности языка. Я знаю про Rosetta Code, но там каша из кода, написанного разными людьми, не доведённого до конца, местами говнокод.

НОД на Прологе

На Прологе описываются факты. Программа на Прологе отвечает на вопросы типа «_верно ли утверждение?_» или «_при каком X верно данное утверждение?_». Поэтому программа вычисления наибольшего общего делителя двух чисел должна работать как-то так:

Верно ли, что НОД(22, 121) = 3?
При каком G верно выражение НОД(22, 121) = G?

В Прологе это записывается соответственно:

gcd2(22, 121, 3).
gcd2(22, 121, G).

Традиционно, НОД ищется по алгоритму Евклида, в котором имеет место верный факт: НОД(a, 0) = a. Этот факт в Прологе записывается так: gcd2(A, 0, A). На вопрос gcd2(11, 0, G) будет дан ответ G=11, а ответ на вопрос gcd2(11, 0, 3) будет отрицательным.

Тот факт, что НОД(a, b) = g, записывается так: gcd2(A, B, G). На вопрос gcd2(22, 121, 11) должен быть дан положительный ответ, на вопрос gcd2(16, 32, 8) — отрицательный, а на вопрос gcd2(22, 121, G) — G=11.

Суть алгоритма Евклида в том, что НОД(a, b) = g, если НОД(b, n) = g, где n — остаток от деления a на b. На Прологе это записывается так:

gcd2(A, B, G) :- N is A mod B, gcd2(B, N, G).

Рано или поздно N будет равно нулю, и проверка факта gcd2(A, B, G), сведётся к проверке факта gcd2(X, 0, X), то есть равенства первого и третьего параметра.

Минимальная программа

Минимальная (неправильная) программа, записана в файл gcd.pl и выглядит так:

gcd2(A, 0, A). gcd2(A, B, G) :- N is A mod B, gcd2(B, N, G).

Эта программа не будет работать, потому что рано или поздно будет деление на ноль. Дело в том, что программа на Прологе ищет все возможные решения, не останавливаясь на первой строке. Чтобы огородиться от этого, надо добавить, как минимум, условие B =\= 0 (B не равно нулю):

gcd2(A, B, G) :- B==0, N is A mod B, gcd2(B, N, G).

А ещё лучше потребовать положительные A и B:

gcd2(A, B, G) :- A>0, B>0, N is A mod B, gcd2(B, N, G).

Для проверки используем GNU Prolog 1.3.1. Расширения файлов: PL и PRO, например hello.pl, gcd.pro. Первый вариант приоритетный (если расширение не указано), но конфликтует с Перлом: если в каталоге есть файлы gcd.pl и gcd.pro, то загружается gcd.pl (с ошибкой, если это Перл :-) Поэтому имя файла лучше указывать полностью, заключая в одинарные кавычки (из-за точки в имени).

gprolog

yes | ?- gcd2(22,33,11).

true ? a

no | ?- gcd2(22,33,D).

D = 11 ?

yes | ?- gcd2(22,121,4).

no | ?- gcd2(22,121,Gcd).

Gcd = 11 ? ;

no | ?-

Полноценная программа

Описание НОД для списка чисел:

gcdn([A|As], G) :- gcdn(A, As, G). gcdn(A, [], A). gcdn(A, [B|Bs], G) :- gcd2(A, B, N), gcdn(N, Bs, G).

Преобразование списка строк в список чисел (или наоборот, это же Пролог):

str2int([], []). str2int([S|St], [N|Nt]) :- number_atom(N, S), str2int(St, Nt).

Читается так: список строк является представление списка чисел, если первая строка является представлением первого числа, и оставшийся список строк является представление оставшегося списка чисел. На вопрос str2int([‘22’, ‘11’], [22, 11]) будет дан положительный ответ, на вопрос str2int([‘22’, ‘11’], X) будет дан ответ X = [22, 11], на вопрос str2int([X, ‘11’], [22, Y]) будет дан ответ X = ‘22’, Y = 11.

Точка входа в программу (факт, который надо проверить сразу после запуска программы):

:- initialization(main). main :- argument_list(Args), str2int(Args, Numbers), gcdn(Numbers, G), write(G), nl.

Функции (предикаты) argument_list, number_atom являются расширениями GNU Prolog. Полностью программа здесь: https://github.com/ip1981/GCD/blob/master/gcd.pro. Её надо компилировать командой gplc --no-top-level gcd.pro, а получившийся исполняемый файл gcd, использовать так: ./gcd 22 33 121 44

P. S. https://docs.google.com/document/pub?id=10vRZ-OykfEUfehlVUjlmBSbDAuOHVNtZmtfnbXD_9QU