ТУСУР, функциональное и логическое программирование (лабораторная работа)

Выбор варианта лабораторных работ

Выбор варианта лабораторных работ осуществляется по общим правилам с использованием следующей формулы:

V = (N × K) div 100,

где V – искомый номер варианта,

N – общее количество вариантов,

div – целочисленное деление,

при V = 0 выбирается максимальный вариант,

K – код варианта, указанный в личном кабинете студента.

ЛАБОРАТОРНАЯ РАБОТА

«РАЗРАБОТКА ПРОГРАММЫ С ИСПОЛЬЗОВАНИЕМ ЯЗЫКА ЛИСП»

Цель работы – получить практические навыки в решении задач по функциональному программированию с использованием языка Лисп.

Задание

1. Задание состоит из трех задач, в которых необходимо составить программы на Лиспе.

В первой задаче требуется применение простой рекурсии. При составлении программ (если не оговорено противное) можно использовать все встроенные функции Лиспа. Отладку программ можно осуществлять с помощью функции трассировки (trace <имя функции>), для отключения трассировки функции используйте (untrace <имя функции>).

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

В третьей задаче требуется использовать функционалы. При составлении программ (если не оговорено противное) можно использовать все встроенные функции языка Лисп. Тексты всех программ, если вы мыслите в духе функционального программирования, буквально состоят из нескольких строчек.

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

Вариант 1

1. Последовательность чисел Фибоначчи 1, 1, 2, 3, 5, 8, 13… строится по следующему закону: первые два числа – единицы; любое следующее число есть сумма двух предыдущих f(n) = f(n – 1) + f(n – 2). Напишите функцию (f n f1 f2) c накапливающимися параметрами f1 и f2, которая вычисляет n-е число Фибоначчи.

2. Определите функцию, зависящую от двух аргументов u и n, которая по данному списку строит список его элементов, встречающихся в нем не менее n раз. Проверьте работу этой функции на примере (a b a c b c a b d a b) для n = 1,2,5,0.

3. Используя функционалы, напишите функцию, которая из данного списка строит список списков его элементов, например, (a b) -> ((a) (b)).

Вариант 2

1. Определите возведение в целую степень (^ x n) через умножение и деление.

2. Напишите функцию, заменяющую Y на число, равное глубине вложения Y в W, например, Y = a, W = ((a b) a (c (a (a d)))) ->((2 b) 1 (c (3 (4 d)))).

3. Напишите функцию, единственным аргументом которой являлся бы список списков, объединяющую все эти списки в один.

Вариант 3

1. Напишите функцию, вычисляющую последний элемент списка.

2. Напишите функцию, которая делает из списка множество, т. е. удаляет все повторяющиеся элементы.

3. Напишите функцию (exists p x), которая проверяет, существует ли элемент списка x, удовлетворяющий предикату p (p – функция или функциональное имя).

Вариант 4

1. Напишите функцию, которая из данного одноуровнего списка строит список списков его элементов, например, (a b) -> ((a) (b)).

2. Напишите функцию, которая сортирует список чисел, используя алгоритм простой вставки.

3. Напишите функцию (all p x), которая проверяет, для всех ли элементов списка x выполняется предикат p (p – функция или функциональное имя).

Вариант 5

1. Определите функцию, зависящую от аргументов u и v, являющихся списками, которая вычисляет список всех элементов, содержащихся либо в u, либо в v, но не одновременно в u и v.

2. Определите функцию (f s), результатом которой является список, получающийся из списка списков s после удаления всех подсписков, содержащих числа.

3. Напишите функцию (filter p x), которая «фильтрует» (создает список) элементы списка x, удовлетворяющие предикату p (p – функция или функциональное имя).

Вариант 6

1. Напишите функцию, аналогичную встроенной функции замены subst в списке s выражения x на y, но производящую взаимную замену x на y, т. е. x->y, y->x.

2. Определите функцию (f s), которая вычисляет список (m1 m2 m3), состоящий из трех наибольших элементов списка s: m1 >= m2 >= m3. Исходный список содержит не менее трех элементов.

3. Определите функцию (f s n), которая из списка чисел s создает новый список, прибавляя к каждому атому число n. Исходный список не предполагается одноуровневым.

Вариант 7

1. Определите функцию (summa_digits n), результатом которой является сумма цифр натурального числа n.

2. Определите функцию (f s), которая в одноуровневом списке чисел s переставляет все отрицательные элементы в начало списка, например, (f '(4 -8 6 -9 -7)) -> (-8 -9 -7 4 6), меняя знак у каждого атома.

3. Определите функцию (f s), которая из списка чисел s создает новый список, меняя знак у каждого атома. Исходный список не предполагается одноуровневым.

Структура отчета по лабораторной работе:

– титульный лист;

– цели и задачи лабораторной работы;

– основная часть (расчетная часть);

– выводы;

– список использованных источников;

– приложения (при необходимости).