Семинар 3. Рекурсивные отношения в языке Prolog. Отладка программ в Strawberry Prolog СИСТЕМЫ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА

ЦЕЛИ ИСПОЛЬЗОВАНИЯ РЕКУРСИИ Рекурсивные отношения используют самих себя Отношение «предок» определяется следующим образом: X – предок Y, если X является родителем Y. X – предок Y, если X является родителем Z, а Z в свою очередь является предком Y

НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ Алгоритм Евклида Если заданы два целых числа X и Y, то наибольший общий делитель D определяется правилами: 1. Если X и Y равны, то D равен X. 2. Если X > Y, то D равен наибольшему общему делителю разности X–Y и Y. 3. Если X < Y, то формулировка аналогична правилу (2), если X и Y поменять местами.

ПРИМЕР РЕАЛИЗАЦИИ АЛГОРИТМА ЕВКЛИДА Цель (золотое правило: начинайте писать программу с цели!) ?- nod(91,65,D),write(D),nl. Трем «если» соответствуют три реализации правила nod На первое место при определении рекурсивного правила ставится условие выхода (не всегда, но как правило) 1.nod(X,X,X). the Prolog way Основная «рабочая лошадка» 2.nod(X,Y,D) :- X>Y,X1:=X-Y,nod(X1,Y,D). Правило для «всех остальных случаев» 3.nod(Y,X,D) :- nod(X,Y,D). Внимание: решение, получаемое таким способом, не единственное! Для единственности решения необходимо ограничивать перебор (см. исходный код семинара)

ВЫЧИСЛЕНИЕ ФАКТОРИАЛА НЕХВОСТОВАЯ РЕКУРСИЯ На пальцах: факториал числа N – это факториал (N-1), умноженный на N Цель (обратно золотое правило: начинайте с цели!) ?- fact(5,W), write(W), nl. Рекурсивное отношение для вычисления факториала fact(1,1). % условие выхода – обязательно должно быть fact(N,R) :- % голова правила N>1, % проверка аргументов N1 is N-1, % присвоить значение локальной переменной N1 fact(N1,R1), % рекурсивный вызов в середине («не хвостовой») R is R1*N. % присвоить значение произведения переменной R

ВЫЧИСЛЕНИЕ ФАКТОРИАЛА ХВОСТОВАЯ РЕКУРСИЯ Цель (ничем не отличается от предыдущей) ?- fact(5,W), write(W), nl. «Интерфейсное» правило без лишних аргументов fact(N,R) :- factA(N,1,R). % точка входа Рабочее рекурсивное отношение для вычисления факториала factA(N,S,R) :- % голова правила N>1, % проверка аргументов S1 is S*N, % присвоить значение произведения N1 is N-1, % присвоить значение локальной переменной N1 factA(N1,S1,R). % рекурсивный вызов в конце factA(1,R,R). % условие выхода

ЕЩЕ РАЗ ПРО ОТЛАДКУ В STRAWBERRY PROLOG Горячие клавиши: Ctrl+F5 – начало отладки F12 – дерево доказательств F9 – следующий шаг F10 – переступить F11 – выйти на уровень выше