Методические рекомендации по срсп и срс самостоятельная работа студентов под руководством преподавателя (стр. 3 из 7)

В приведенном выше определении отношения «предок» первая фраза определяет исходный вид этого отношения. Как только она станет истинной, рекурсия прекратится. Вторая фраза – это рекурсивное правило. При каждом вызове данное правило поднимается на одно поколение вверх. Подцель «родитель(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. Выводы по работе.

Методические указания к занятию № 3

Работа со списками

Цель СРСП

Ознакомиться с реализацией структуры данных типа список в языке Пролог и методами их обработки.

Задание для подготовки к работе

Изучить лекции по теме "Списки".

Порядок выполнения работы

1. Выполнить контрольные примеры.

2. Создать программу на языке Пролог, которая решает задачи согласно варианту.

3. Составить отчет о проделанной работе.

Задание и методические рекомендации

Список - это простая структура данных, широко используемая в нечисловом программировании. Список либо пуст, либо состоит из двух частей: головы и хвоста. Голова списка является атомом, а хвост, в свою очередь, сам является списком. Заметим, что список в Прологе – это частный случай двоичного дерева.

Контрольный пример

Создание списка всех натуральных чисел не превосходящих заданного.

create([],0).

create([X|T],X):-X>0, X1=X-1, create(T,X1).

Задание к работе

1. Реализовать набор функций для обработки списков, используя возможности языка:

- Добавление элемента к списку.

- Удаление элемента из списка.

- Конкатенация списков.

- Определение длины списка.

- Выделение подсписка.

2. Решить дополнительные задачи согласно варианту, используя построенные функции.

3. Подобрать тестовые данные и оформить отчет.

Варианты заданий

1. Решить следующие задачи:

а) проверить является ли список палиндромом;

б) упорядочить список методом вставки;

в) добавить к каждому элементу списка 1;

г) выделить из списка подсписки положительных и отрицательных чисел.

2. Решить следующие задачи:

а) добавить элемент в i-ю позицию списка;

б) подсчитать сумму всех элементов списка;

в) инвертировать список;

г) по паре чисел выдать список натуральных чисел, находящихся между числами этой пары на числовой оси.

3. Решить следующие задачи:

а) удалить из списка все повторяющиеся подсписки;

б) подсчитать количество положительных чисел в списке;

в) подсчитать сумму положительных и произведение отрицательных элементов списка;

г) подсчитать число повторяющихся элементов списка.

4. Решить следующие задачи:

а) удвоить элемент списка, если он положительный и утроить, если он отрицательный;

б) упорядочить список по убыванию с помощью сортировки (не вставкой);

в) объединить три списка;

г) выделить подсписки, содержащие букву «а» и объединить их.

5. Решить следующие задачи:

а) добавить элемент в i-ю позицию списка;

б) подсчитать сумму целых чисел в списке;

в) выделить из списка подсписки положительных и отрицательных чисел;

г) упорядочить список по возрастанию.

6. Решить следующие задачи:

а) составить список, состоящий из натуральных чисел, лежащих на числовой оси между двумя заданными;

б) подсчитать количество отрицательных, положительных и нулевых элементов списка;

в) инвертировать список;

г) утроить список.

7. Решить следующие задачи:

а) удалить из списка заданный подсписок;

б) упорядочить список по убыванию;

в) заменить каждый элемент списка, состоящий из символов, на следующий символ алфавита;

г) удалить повторяющиеся элементы в списке.

8. Решить следующие задачи:

а) упорядочить список по возрастанию;

б) подсчитать в списке количество отрицательных, положительных и

нулевых элементов;

в) инвертировать список;

г) отнять от каждого элемента списка 1.

9. Решить следующие задачи:

а) выделить из списка буквы и числа;

б) проверить список на симметричность;

в) определить количество уровней вложенности списка;

г) найти сумму четных элементов списка.

10. Решить следующие задачи:

а) инвертировать список на всех уровнях вложенности;

б) найти суммы всех подряд идущих пар чисел в списке;

в) определить длину списка;

г) найти сумму нечетных элементов списка.

11. Решить следующие задачи:

а) добавить подсписок в указанную позицию;

б) инвертировать список;

в) удвоить значения положительных элементов списка и утроить значения его отрицательных элементов;

г) подсчитать число элементов списка больших 10.

12. Решить следующие задачи:

а) удаление подсписков указанной глубины;

б) выдать подсписок, компоненты которого принадлежат заданному

интервалу;

в) выделить из списка все элементы, которые делятся на 2 и на 3;

г) проверить список на симметричность.

13. Решить следующие задачи:

а) инвертировать список;

б) подсчитать сумму положительных элементов списка;

в) выделить положительные, отрицательные и нулевые элементы списка;

г) объединить 3 списка.

14. Решить следующие задачи:

а) упорядочить список по возрастанию методом простой вставки;

б) определить кратность вхождения подсписка в список;

в) подсчитать среднее значение списка;

г) разбить список, состоящий из натуральных чисел, на два подсписка, включив в первый список числа, принадлежащие указанному интервалу, а во второй – все остальные.