Использование рекурсивных правил и структурированных данных
Цель СРСП
Научиться использовать структурированные типы данных и рекурсивные правила при решении задач.
Задание для подготовки к работе
Изучить темы «Рекурсивные правила», «Структурированные данные».
Порядок выполнения работы
1. Выполнить контрольные примеры.
2. Создать в системе программу, которая решает задачи согласно варианту.
3. Модифицировать программу CH06EX03.pro и подобрать цели иллюстрирующие структуру данных.
4. Составить отчет о проделанной работе.
Задание и методические рекомендации
Определения отношений, в которых используется само отношение, называется рекурсивным. Рекурсия – один из фундаментальных механизмов программирования на Прологе. Рекурсию можно применять для достижения такого же эффекта, какой реализуется при употреблении итеративных управляющих конструкций (циклов) в процедурных языках. Примером использования рекурсии может служить определение отношения «предок» [1, 2]. Данное отношение можно выразить с помощью двух правил. Первое правило будет определять непосредственных предков, а второе – отдаленных. Первое правило легко сформулировать через отношение «родитель»:
|
|
предок(X, Z):- родитель(X, Z).
Аналогичным образом можно попытаться сформулировать второе правило:
предок(X, Z):- родитель(X, Z).
предок(X, Z):- родитель(X, Y), родитель(Y, Z).
предок(X, Z):- родитель(X, Y1), родитель(Y1, Y2), родитель(Y2, Z).
Подобное описание отношения будет работать только в определенных пределах, то есть обнаруживать предков лишь до определенной глубины, поскольку длина цепочки людей между предком и потомком ограничена длиной предложений в определении отношения.
Подобные отношения целесообразно описывать с помощью рекурсии. Правило будет выглядеть следующим образом:
Для всех X и Z,
X – предок Z, если
существует Y, такой, что
X – родитель Y и
Y – предок Z.
или на языке Пролог:
предок(X, Z):- родитель(X, Y), предок(Y, Z).
Таким образом, определение отношения «предок» будет выглядеть следующим образом:
предок(X, Z):- родитель(X, Z).
предок(X, Z):- родитель(X, Y), предок(Y, Z).
При описании рекурсивных правил следует соблюдать осторожность во избежание зацикливания рекурсии. Для этого любое рекурсивное определение отношения должно включать по крайней мере два правила:
1) нерекурсивное правило, определяющее исходный вид отношения, т.е. вид отношения в момент прекращения рекурсии;
2) рекурсивное правило – первая подцель, располагающаяся в теле этого правила, вырабатывает новые значения аргументов. Далее размещается рекурсивная подцель, в которой используются новые значения аргументов
|
|
В приведенном выше определении отношения «предок» первая фраза определяет исходный вид этого отношения. Как только она станет истинной, рекурсия прекратится. Вторая фраза – это рекурсивное правило. При каждом вызове данное правило поднимается на одно поколение вверх. Подцель «родитель(X, Y)» вырабатывает значение переменной Y, а в рекурсивной подцели «предок(Y, Z)» используется этот новый аргумент.
Структурные объекты (или структуры) – это объекты, которые состоят из нескольких компонент, которые, в свою очередь, также могут быть структурами. Структуры в языке Пролог аналогичны записям в Паскале или структурам в Си. Структурные объекты в Прологе определяются функтором и аргументами. Например, для представления даты, состоящей из трех компонент (день, месяц, год), можно воспользоваться определением функтора «дата» с тремя аргументами:
date (11, january, 1978).
Произвольный день января 1978 года можно представить структурой, содержащей переменную:
date (Day, january, 1978).
Использование вложенных структур иллюстрирует следующий пример:
human(sergei, ivanov, date(10, may, 1975)).
human(ivan, petrov, date(15, october, 1969)).
Для удобства взаимодействия с такой базой данных можно описать запросы, например:
human(FirstName, LastName, _). % запрос, перечисляющий всех людей из базы данных
human (FirstName, LastName, date(_, _, 1975). % все люди, родившиеся в 1975 году
birthday(human(_, _, Date), Date). % запрос, позволяющий найти человека по указанной дате рождения.
Контрольные примеры
Пример 1. Вычисление факториала
factorial(X, _):- X<0,!,fail.
factorial (0, 1):-!.
factorial(N, Fact):- N1=N-1, factorial(N1, Fact1), Fact=N*Fact1.
Пример 2. Числа Фибоначчи:
F(1,1):-!.
F(2,1):-!.
F(I,R):- I>2, I1=I-1, I2=I-2, F(I1,M), F(I2,N), R=N+M.
Задание к работе
1. Выполнить задачи согласно варианту.
2. Подобрать тестовые данные и оформить отчет.
Варианты заданий
1. Возведение в степень как повторяющееся умножение.
2. Возведение в степень как повторяющееся сложение.
3. Рекурсивное определение остатка от деления (mod).
4. Рекурсивное определение деления нацело (div).
5. Алгоритм Евклида.
6. Функция Аккермана
Ak(0,N) = N + 1
Ak(M,0) = Ak(M-1,1)
Ak(M,N) = Ak(M-1),Ak(M,N-1)
7. Наибольший общий делитель двух чисел.
8. Наибольший общий делитель последовательности чисел.
9. Наименьшее общее кратное двух чисел.
10. Наименьшее общее кратное последовательности чисел.
11. Сложение и вычитание через сложение/вычитание единицы.
12. Нахождение всех простых чисел, не превышающих заданное число.
13. .
14. .
15. .
16. Определить, является ли заданное число числом Фибоначчи.
17. Нахождение чисел Фибоначчи, не превышающих заданное число.
18. Вычисление факториала (ускоренный алгоритм).
19. Вычисление n -го члена арифметической прогрессии, у которой первый член равен 1, а разность 2.
20. Вычисление n -го члена геометрической прогрессии, у которой первый член равен 2, а знаменатель равен 4
21. Сумма натуральных чисел от 1 до n.
22. Сумма всех двузначных чисел, кратных трем.
23. Сумма всех трехзначных чисел, не делящихся ни на 5, ни на 7.
24. Вычислить сумму n первых членов ряда:
1 + 1/2 + 1/3 +...
25. Вычислить сумму n первых членов ряда:
4 - 4/3 + 4/5 - 4/7 + 4/9 -... + (-1)^(n-1) × 4 / (2×n - 1) +...
26. Построить рекурсивную функцию для вычисления n -го члена последовательности, в которой каждый следующий член равен сумме n -2 -го и n -3 -го. Первые 3 члена равны соответственно 1, 2, 3.
1 2 3 3 5 6 8 11
27. Построить рекурсивную функция для вычисления n -го члена последовательности, в которой каждый четный член равен сумме двух предыдущих четных, а нечетный равен сумме двух предыдущих нечетных. Первые четыре члена равны соответственно 1, 2, 3, 4.
1 2 3 4 4 6 7 10 11 16 18...
28. Построить рекурсивную функцию для вычисления n -го члена последовательности, в которой каждый следующий
|
|
29. четный член равен произведению двух предыдущих, а каждый следующий нечетный член равен сумме двух предыдущих, а первые 2 члена равны соответственно 1 и 2.
1 2 3 6 9 54 63...
30. Построить рекурсивную функцию для вычисления n -го члена последовательности, в которой каждый следующий член равен произведению двух предыдущих, а первые 2 члена равны соответственно 1 и 2.
1 2 2 4 8 32...
31. Построить рекурсивную функцию для вычисления n -го члена последовательности, в которой первый член равен 0, второй 1, третий 2, а каждый следующий равен сумме трех предыдущих.
0 1 2 3 6 11....
Содержание отчета
1. Исходные тексты программ на языке Пролог.
2. Наборы тестовых данных и результаты работы программ.
3. Перечень и анализ ошибок.
4. Выводы по работе.