Задачи на Lisp и Prolog с решениями

Вступление

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

Курс по языку лисп на украинском языке можно найти здесь. Рекомендованный учебник по прологу: Л. Стерлинг, Э. Шапиро “Искусство программирования на языке Пролог”.

Пролог решения выполняются в интерпретаторе GNU Prolog.

Загрузка исходного файла производится следующей командой: consult(['filename']).

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

Лисп решения выполняются в интерпретаторах:

mLisp
xLisp

Загрузка исходного файла производится следующей командой из интерпретатора: (LOAD ‘filename)
Например: (LOAD ‘test.lsp)
Либо производится из коммандной строки (cmd.exe): mulisp file.txt. В таком случае текст программы должен заканчиваться командой (system).

Задачи

Задача (PRLG01): На доске 4х4 расставить 4 слона так, чтобы они все находились не под ударом друг друга.
Решения: Лисп

Задача (PRLG02): Написать программу решения головоломки про Волка, Козу и Капусту.
Решения: Лисп (поиск в ширину)

Задача (PRLG03): Операции со списками. Создать функцию на языке Лисп, которая выполняет следующие действия: перегруппирует элементы заданного списка так, чтобы одинаковые элементы, если они есть в списке, стояли все подряд.
Решения: Лисп, Запустить Запуск: (l8 ‘(1 2 1 3 2 5 7 1))

Задача (PRLG04): Написать функцию, упорядочивающую список, заданный в качестве ее первого аргумента, переставляя его элементы в той последовательности, в какой они встречаются в списке, являющемся значением второго аргумента.
Решения: Лисп

Задача (PRLG05): Написать программу, которая печатает все перестановки чисел от 1 до n.
Решения: Лисп

Задача (PRLG06): Написать программу вычисления значения многочлена в точке по схеме Горнера:

Р₀ = a₀;
P₁ = Р₀ • x + a₁ = a₀ • x + a₁;
P₂ = Р₁ • x + a₂ = a₀ • x + a₁ • x + a₂;
Р_n = (…( ( a₀ • x + a₁) • x + а₂) • x + … + а_n-1) • x + а_n.

Решения: Лисп

Задача (PRLG07): Написать программу обращения списка с подсписками.
Решения: Лисп, Запустить

Задача (PRLG08): Написать программу сортировки списка чисел методом Quick Sort (Быстрой сортировки).
Решения: Лисп

Задача (PRLG09): Написать программу, которая преобразует представление числа из десятичной в двоичную систему.
Решения: Лисп

Задача (PRLG10): Написать программу, которая объединяет два отсортированных списка в один, тоже отсортированный. Например: (2, 3, 6, 8) и (1, 4, 5, 7, 10) -> (1, 2, 3, 4, 5 ,6 ,7, 8, 10).
Решения: Пролог, Лисп

Опpеделите функцию, добавляющую заданное параметром x число в упорядоченный по неубыванию список L таким образом, чтобы сохранилась упорядоченность.

          (defun insert(x l)
           (cond
             ((null l) (cons x))
             ((< x (car l)) (cons x l) )
             (null (cons (car l) (insert x (cdr l)) )  )
           )
          )
          (insert '7 '(0 3 3 6 9))
          (system)

Задача (PRLG11): Написати на Пролозi програму, яка друкує всi пiдмножини заданої множини.
Ідея розв’язку грунтується на спiввiдношеннi:
Boolean(X) = Boolean(X\{y}) U {y} U { (S U {y}) | S множина з Boolean(X\{y})}.
Побудову множини { (S U {y}) | S множина з Boolean(X\{y})} здiйснює функцiя comb. Функцiя обчислює вищенаведене рекурентне спiввiдношення.
Решения: Пролог

Задача (PRLG12): Напишите функцию, которая сортирует список чисел, используя алгоритм простого выбора.
Решения: Лисп

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

Задача (PRLG14): Напишите функцию на Lisp, осуществляющую циклическую перестановку элементов в списке,т.е. (f g h j) -> (g h j f).
Вариант 1 решения: Лисп
Вариант 2 решения: Лисп

Напишите функцию, осуществляющую циклическую перестановку N следующих подряд элементов в списке. Например, при N=3 и исходном списке (a b c d e f g h) должно получиться (f g h a b c d e).
Вариант решения для обратной перестановки: Лисп

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

Задача (PRLG16): Определите функцию (Lisp), зависящую от двух аргументов u и v, являющихся списками, которая вычисляет список всех элементов u, не содержащихся в v.
Решения: Лисп

Задача (PRLG17): Написать программу реализующую игру в “Шашки”
Решения: Пролог

Задача (PRLG18): Определить функцию, которая любой исходный список преобразует в список с одним уровнем скобок, например: (a (b c) a b (c (c)))) -> (a b c a b c c).
Решения: Лисп

Задача (LSP19): Разработать функцию, аргументом которой является список, возвращающую список пар: (<элемент исходного списка> <количество его вхождений в исходный список>).
Решение: Лисп

Задача (PRLG20): Разработать функцию сортировки методом вставки.
Решение: Пролог

Задача (LSP21): Дано натуральное число N. Вычислить s=1/sin₁+1/(sin₁+sin₂)+…+1/(sin₁+…+sin_N).
Решение: Лисп

Задача (LSP22): Найти минимальный элемент списка.
Решение: Лисп

Задача (LSP23): Реализовать функцию перемножения многочленов, если многочлены задаются в виде списков их коэффициентов.
Решение: Лисп

Задача (PRG24): Реализовать предикат поиска пути в графе (depth-first). Найти цикл в графе заданной длины. Найти Гамильтонов цикл (задача коммивояжера).
Решение: Пролог

Задача (LSP25): На вход подается матрица и два списка:

a11 a12 | rgh1

a21 a22 | rgh2

—- —-

btn1 bnt2

Матрица состоит из символов, а списки из чисел. Программа находит такие подстановки чисел вместо символов матрицы, чтобы суммы по вертикали и горизонтали были равны соответсвующим елементам списков.
Пример использования использование
(solve ‘((a b) (b a)) ‘(3 3) ‘(3 3))
(solve ‘((a a b) (b a c) (c b a)) ‘(4 6 6) ‘(6 4 6))

Решение: Лисп

Задача (LSP26): Найти разложение числа на слагаемые.

Решение: Лисп

Задача (LSP27): Определить функцию CDRN такую, что (CDRN N L) будет эквивалентна функции (CDD..DR L), в имени которой имеется N букв D.

Решение: Лисп

Задача (LSP28): Определить предикат (NOSUBS L), который принимает значение Т, если список L не имеет подсписков, и NIL-в противном случае.

Решение: Лисп

Задача (LSP29): Определить функцию, которая удаляет из списка повторяющиеся элементы.

Решение 1: Лисп
Решение 2: Лисп

Задача (LSP30): Определить функцию, которая принимает значение Т если в списке L больше чисел, чем атомов. L – список атомов любого типа.

Решение: Лисп

Задача (LSP31): Определить функцию НОД (X Y), позволяющую найти наибольший общий делитель чисел X и Y.

Решение 1: Лисп
Решение 2: Лисп

Задача (PRO32): Из математического анализа известно, что функция cos(x) представляется в виде ряда Тейлора:
cos(x)=1 − x²/2!+x⁴/4!-x⁶/6!+x⁸/8!-x¹⁰/10!+…
Напишите рекурсивную программу для предиката cos(X, Res), который вычисляет приближенное значение косинуса путем суммирования первых членов ряда до тех пор, пока слагаемые превышают 0,0001.

Решение: Пролог

Пояснение: cos(X,R,S,FN,XN,N), Х – это значение, R – текущий результат, S – знак, F_n = N!, X_n = x^N, N = 2, 4, 6, 8, 10, …

Задача (PRO33): Даны факты для предиката reys(From, To), описывающего существующие рейсы самолетов с указанием пунктов отправления и прибытия. Написать программу для предиката avia2(From, To), который должен быть истинным, только если из города From можно долететь до города To с двумя пересадками, и нельзя с меньшим числом.

Решение: Пролог

Задача (PRO34): Подсчитать количество положительных элементов в списке.

Решение:

          count([],0).
          count([A|X],C):-A>0,!,count(X,C1),C is C1+1.
          count([A|X],C):-count(X,C).

Задача (PRO35): Подсчитать методом рекурсии значение функции: y=cos(x)•2•cos(x)•3•cos(x)•n•cos(x), для данного х.

Решение:

          f(_,0,1).
          f(X,1,R):-!,cos(X,R).
          f(X,N,R):-!,N1 is N-1,f(X,N1,R1),cos(X,R2),R is R1*N*R2.

Для вычисления значения cos(X,R) смотри задачу № PRO32.

Задача (PRO36): Опpеделите на языке лисп функционал, заменяющий все элементы списка, не обладающие определенным свойством, на символ *. Проверьте работу функционала для предикатов:

Число: (mapcar ‘(lambda (x) ((numberp x) x) (‘*) ) ‘(1 a 2 b 3))
Неположительное число: (mapcar ‘(lambda (x) ((>= x 0) x) (‘*) ) ‘(1 -2 3))

Задача (PRO37): Задан список вещественных чисел. Заменить все четные (по номеру) элементы списка, на произвольную константу.
Решение: Запустить. (Числа буду заменены на константу 0). Пролог.

Задача (PRO38): Вычислить сумму ряда:

Решение: Лисп. Запустить.

Задача (PRO39): На одной улице стоят 4 дома. В каждом из них живет один из 4-х людей: Семен, Николай, Артур и Роман. Каждый из них владеет профессией: Врач, Художник, Егерь, Тренер. Определить кто в каком доме живет и кто какой профессией владеет. Известно, что:

Художник живет рядом с тренером
Врач живет рядом с Художником
Егерь левее врача
Тренер не рядом с Егерем
Художник правее Семена
Роман не тренер
Семен рядом с Николаем
Артур не рядом с Романом

Это упрощённый вариант задачи Эйнштейна. (Загрузить пролог решение)

Решение: Запустить. Пролог.

Задача (PRO40): Напишите функцию (range М N X), которая выдает список чисел, больших X и расположенных между М и N включительно.

Решение: Лисп. Запустить.

Задача (PRO41): Фигуры на шахматной доске заданы списком троек (фигура, горизонталь, вертикаль). Определить, находится ли на указанной вертикали указанная фигура.

Решение: Лисп. Запустить.

Задача (PRO42): Написать программу определения количества списков в заданном списке на заданном уровне. Исходный список имеет уровень 0, вложенный в него список имеет уровень 1 и т.д.

Решение: Лисп. Запустить.