РекурсияПоиск с возвратом Одной из важнейших особенностей языка Prolog является возможность поиска всех решений. Поиск всех решений достигается использованием механизма поиска с возвратом. Можно сформулировать четыре основных правила поиска с возвратом: - Правило 1: подцели должны быть согласованы по порядку, слева направо; - Правило 2: предложения проверяются в том порядке, в котором они появляются в тексте программы; - Правило 3: когда подцель сопоставляется с заголовком правила, тело этого правила должно быть доказано (тело правила состоит, в свою очередь, из новых подцелей, которые должны быть доказаны); - Правило 4: целевое утверждение считается согласованным, когда соответствующие факты найдены для каждой листьевой вершины дерева целей.
Пример: DOMAINS name, thing=symbol
PREDICATES hobby (name, thing) reads (name) is_inquisitive (name)
CLAUSES hobby (“Ян”, “теннис”). hobby (“Лена”, “лыжи”). hobby (X, “книги”):- reads (X), is_inquisitive (X). hobby (“Лена”, “книги”). reads (“Ян”). is_inquisitive (“Ян”).
Goal: hobby (Y, “теннис”), hobby (Y, “книги”). Y=“Ян”
Для управления поиском решений существует два стандартных предиката: - предикат fail, использующийся для поддержания поиска с возвратом; - предикат! (отсечение), использующийся для предотвращения поиска с возвратом.
Предикат fail всегда дает неудачу в доказательстве и, таким образом, поддерживает поиск с возвратом. Пример. DOMAINS name=symbol
PREDICATES father (name, name) everybody
CLAUSES father (“Павел”, “Петр”). father (“Петр”, “Михаил”). father (“Петр”, “Иван”). everybody:- father (X, Y), write (X, “это отец ”, Y, “а”), nl, fail.
GOAL everybody. Результатом работы будет вывод следующих сообщений, и работа программы завершится с неуспехом: Павел это отец Петра Петр это отец Михаила Петр это отец Ивана Предикат! (отсечение) убирает все точки возврата, то есть через отсечение нельзя совершить поиск с возвратом. Пример. r(1):-!, a, b, c. r(2):-!, d. r(3):-!, e. r(_):- write (“Это предложение-ловушка”).
Практическое задание №2. Рекурсия в Prolog (выбор варианта по последней цифре номера зачетной книжки)
Вариант 0 Подсчитать, сколько раз встречается некоторая буква в строке. Строка и буква должны вводиться с клавиатуры. Для разделения строки на символы использовать стандартный предикат frontchar (String, Char, StringRest), позволяющий разделять строку String на первый символ Char и остаток строки StringRest. Вариант 1 Вычислить значение n-го члена ряда Фибоначчи: f(0)=0, f(1)=1, Вариант 2 Вычислить произведение двух целых положительных чисел (используя суммирование). Вариант 3 Подсчитать, сколько раз встречается некоторое слово в строке. Строка и слово должны вводиться с клавиатуры. Для разделения строки на слова использовать стандартный предикат fronttoken (String, Lexeme, StringRest), позволяющий разделить строку String на первое слово Lexeme и остаток строки StringRest. Вариант 4 Поменять порядок следования букв в слове на противоположный. Для разделения строки на символы использовать стандартный предикат frontchar (String, Char, StringRest), позволяющий разделять строку String на первый символ Char и остаток строки StringRest. Вариант 5 Вычислить сумму ряда целых нечетных чисел от 1 до n. Вариант 6 Поменять порядок следования слов в предложении на противоположный. Для разделения строки на слова использовать стандартный предикат fronttoken (String, Lexeme, StringRest), позволяющий разделить строку String на первое слово Lexeme и остаток строки StringRest.. Вариант 7 Вычислить сумму ряда целых четных чисел от 2 до n. Вариант 8 Организовать ввод целых положительных чисел и их суммирование до тех пор, пока сумма не превысит некоторого порогового значения. Введенные отрицательные целые числа суммироваться не должны. Вариант 9 Организовать ввод букв и их соединение в строку до тех пор, не будет введен символ #. Для присоединения символа к строке использовать стандартный предикат frontchar (String, Char, StringRest), позволяющий присоединять символ Char к строке StringRest и получать строку String. Методические указания: Рекурсия Рекурсивная процедура – это процедура, которая вызывает сама себя. Рекурсия – хороший способ для решения задач, содержащих в себе подзадачу такого же типа. Например, задача нахождения значения факториала n! сводится к нахождению значения факториала (n-1)! и умножения найденного значения на n. PREDICATES factorial (integer, real) CLAUSES factorial (0, 1):-!. %факториал 0! равен 1 (граничное условие, factorial (N, FactN):- M=N-1, factorial (M, FactM), FactN= FactM*N. %факториал n! равен (n-1)!*n (рекурсивное условие) Goal: factorial (3, FactN) FactN=6
Для наглядного представления нахождения решения удобно использовать дерево целей:
У рекурсии есть большой недостаток, она требует памяти. Избежать этого недостатка позволяет хвостовая рекурсия. Рекурсия является хвостовой, если выполняются следующие условия: - рекурсивный вызов является самой последней подцелью выражения; - ранее в предложении не было возвратных точек.
Пример хвостовой рекурсии: PREDICATES count (real) CLAUSES count (N):- write (N), nl, NewN=N+1, count (NewN). GOAL count (1).
Примеры нехвостовой рекурсии: PREDICATES badcount1 (real) badcount2 (real) badcount3 (real) CLAUSES % рекурсивный вызов ‑ не последняя подцель в предложении badcount1 (N):- write (N), NewN=N+1, count (NewN), nl. % перед рекурсивным вызовом в предложении есть точка возврата badcount2 (N):- N>=0, write (N), nl, NewN=N-1, badcount2 (NewN). badcount2 (N):- write (“N – отрицательное число”). % перед рекурсивным вызовом в предложении есть точка возврата badcount3 (N):- write (N), nl, NewN=N+1, check(NewN), badcount3 (NewN). check (M):- M>=0. check (M):- M<0.
Для преобразования рекурсии в хвостовую для предикатов badcount2 и badcount3 достаточно воспользоваться отсечением, которое уберет все точки возврата перед рекурсивным вызовом.
badcount2 (N):- N>=0,!, write (N), nl, NewN=N-1, badcount2 (NewN). badcount2 (N):- write (“N – отрицательное число”). badcount3 (N):- write (N), nl, NewN=N+1, check(NewN),!, badcount3 (NewN). check (M):- M>=0. check (M):- M<0.
Практическое задание №3. Знакомство с основами функционального программирования в Lisp (выбор варианта по последней цифре номера зачетной книжки)
Вариант 0 Определить рекурсивную функцию, возвращающую значение n-го члена ряда Фибоначчи: f(0)=0, f(1)=1, f(n)=f(n-1)+f(n-2). Вариант 1 Определить рекурсивную функцию для удаления последнего элемента списка. Вариант 2 Определить рекурсивную функцию, возвращающую произведение двух целых положительных чисел (использовать суммирование). Вариант 3 Определить рекурсивную функцию, возвращающую последний элемент списка. Вариант 4 Определить рекурсивную функцию, возвращающую значение суммы ряда целых четных чисел от 2 до n. Вариант 5 Определить рекурсивную функцию, возвращающую список, из которого удалены 2-ой, 4-ый и т.д. элементы. Вариант 6 Определить рекурсивную функцию, возвращающую количество элементов в списке без какого-либо указываемого элемента.
Вариант 7 Определить рекурсивную функцию, возвращающую количество определенных элементов в списке. Вариант 8 Определить рекурсивную функцию для циклического сдвига списка вправо на один элемент. Вариант 9 Определить рекурсивную функцию, возвращающую список, из которого удалены 1-ой, 3-ый и т.д. элементы.
Методические указания:
|
