Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

Контрольная работа по "Функциональное и логическое программирование"

Федеральное Агентство Образования

Брянский Государственный Технический Университет

Кафедра «Информатика и программное обеспечение

Контрольная работа №1 и №2

По предмету: «Функциональное и логическое программирование»

Студент группы З06-ПО1:

Хохлова Н.

Проверил:

Шалимов П. Ю.

Брянск 2008 г.

Контрольной работы №1

Задание №1. Разработать рекурсивный вариант программы в функциональном стиле для решения предложенной ниже задачи.

Текст задания. Объединять два упорядоченных в порядке возрастания чисел списка в один упорядоченный

Пример:

> (name '(1 3 5 7) '(2 4 6))

(1 2 3 4 5 6 7)

Введение. Разрабатываемая функция выполняет селективное слияние списков. Аналогом является стандартная функция слияния списков append. Функция от двух аргументов, являющихся списками. Значением функции также является список. Поскольку требуется чисто функциональное решение, то в программе не допускается использование статических связей переменных (псевдофункции set, setq), форм организации циклических вычислений (do, do*), структуроразрушаюшего присваивания (rplaca, rplacd?, nconc, и т. д.). Функция должна поэлементно копировать элементы исходных списков в новую структуру, проверяя соблюдение условия упорядочения. Допускаются к использованию селекторы car, cdr и конструктор cons.

Декларативное описание решения. Решение обладает следующими свойствами:

• функция упорядоченного слияния name(list,list) -> list;

• если первый список пустой, то результат слияния – второй список (начальные условия рекурсии);

• если голова второго списка меньше головы первого, то результат – список, состоящий из головы второго и результата слияния хвоста второго списка с первым;

• иначе результирующий список состоит из головы первого и результата слияния хвоста первого списка со вторым.

Комментированный текст программы:

(defun name (list1 list2)

(cond ( (null list1) list2) ; НАЧАЛЬНЫЕ УСЛОВИЯ РЕКУРСИИ

;-Если первый список пустой, то результат-второй список

( (< (car list2) (car list1))

; если голова второго списка меньше головы первого, то результат

( cons (car list2)

; список, состоящий из головы второго

(name (cdr list2) list1)))

; и результата слияния хвоста второго списка с первым списком

( t

; иначе

( cons (car list1)

; Искомый список состоит из головы первого списка

(name (cdr list1) list2)))

; и результата слияния хвоста первого со вторым списком

))

Комментированное тестирование программы

>(trace name)

Запускаем трассировку функции name

> (name '(1 3 5 7 9) '(2 4 6 8))

при каждом обращении к функции будет выдаваться список

аргументов

Entering: NAME, Argument list: ((1 3 5 7 9) (2 4 6 8))

Entering: NAME, Argument list: ((3 5 7 9) (2 4 6 8))

Entering: NAME, Argument list: ((4 6 8) (3 5 7 9))

Entering: NAME, Argument list: ((5 7 9) (4 6 8))

Entering: NAME, Argument list: ((6 8) (5 7 9))

Entering: NAME, Argument list: ((7 9) (6 8))

Entering: NAME, Argument list: ((8) (7 9))

Entering: NAME, Argument list: ((9) (8))

Выполнение начальных условий – первый список пустой

Entering: NAME, Argument list: (NIL (9))

Формирование результата

Exiting: NAME, Value: (9)

Exiting: NAME, Value: (8 9)

Exiting: NAME, Value: (7 8 9)

Exiting: NAME, Value: (6 7 8 9)

Exiting: NAME, Value: (5 6 7 8 9)

Exiting: NAME, Value: (4 5 6 7 8 9)

Exiting: NAME, Value: (3 4 5 6 7 8 9)

Exiting: NAME, Value: (2 3 4 5 6 7 8 9)

Exiting: NAME, Value: (1 2 3 4 5 6 7 8 9)

(1 2 3 4 5 6 7 8 9)

Частный случай применения: функция, определенная выше, может использоваться и для внедрения в упорядоченный список числа. При этом число должно подаваться как элемент списка, являющегося аргументом функции.

> (name '(1 2 3 4 5 6) '(3))

Entering: NAME, Argument list: ((1 2 3 4 5 6) (3))

Entering: NAME, Argument list: ((2 3 4 5 6) (3))

Entering: NAME, Argument list: ((3 4 5 6) (3))

Entering: NAME, Argument list: ((4 5 6) (3))

Entering: NAME, Argument list: (NIL (4 5 6))

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

Exiting: NAME, Value: (4 5 6)

Exiting: NAME, Value: (3 4 5 6)

Exiting: NAME, Value: (3 3 4 5 6)

Exiting: NAME, Value: (2 3 3 4 5 6)

Exiting: NAME, Value: (1 2 3 3 4 5 6)

(1 2 3 3 4 5 6)

> (name '(4) '(1 2 3 5 6))

Entering: NAME, Argument list: ((4) (1 2 3 5 6))

Entering: NAME, Argument list: ((2 3 5 6) (4))

Entering: NAME, Argument list: ((3 5 6) (4))

Entering: NAME, Argument list: ((5 6) (4))

Entering: NAME, Argument list: (NIL (5 6))

Exiting: NAME, Value: (5 6)

Exiting: NAME, Value: (4 5 6)

Exiting: NAME, Value: (3 4 5 6)

Exiting: NAME, Value: (2 3 4 5 6)

Exiting: NAME, Value: (1 2 3 4 5 6)

(1 2 3 4 5 6)

Задание №2. Разработать итерационный вариант программы в императивном стиле для решения предложенной задачи.

Текст задания: Объединять два упорядоченных в порядке возрастания чисел списка в один упорядоченный

Пример:

> (name '(1 3 5 7) '(2 4 6))

(1 2 3 4 5 6 7)

Введение. Функция должна выполнять селективное объединение. В отличие задания №1 она должна быть выполнена в императивном стиле. Это означает следующее: вместо рекурсии для организации повторяющихся вычислений можно использовать конструкции организации повторяющихся вычислений (do, do*); допустимо использование разрушающего присваивания (set, nconc). Вместо декларативного описания свойств решения – словесное описание алгоритма.

Словесное описание алгоритма решения задачи.

• Функция двух формальных параметров list1и list2.

• Организуется цикл по локальной переменной list3 с начальным значением nil. Условие выхода из цикла – равенство nil переменных list1и list2. При этом возвращается значение переменной list3.

• Условное предложение.

Первое условие – если переменная list1 равна nil, то выполнить последовательность вычислений:

• выполнить слияние значений переменных list3 и list2;

• присвоить полученное значение переменной list3;

• присвоить переменной list2 значение nil.

Второе условие – если переменная list2 равна nil, то выполнить последовательность вычислений:

• выполнить слияние значений переменных list3 и list1;

• присвоить полученное значение переменной list3;

• присвоить переменной list1 значение nil.

Третье условие – если значение (car list1) меньше или равно значению (car list2), то выполнить последовательность вычислений:

• создать список из головы списка, представленного переменной list1;

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

• присвоить полученное значение переменной list3;

• присвоить переменной list1 значение cdr list1.

Четвертое условие – во всех остальных случаях выполнить последовательность вычислений:

• создать список из головы списка, представленного переменной list2;

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

• присвоить полученное значение переменной list3;

• присвоить переменной list2 значение cdr list2.

Комментированный текст программы

(defun name(list1 list2)

; Функция con двух формальных параметров list1и list2.

(do ((list3 nil))

; цикл по локальной переменной list3 с начальным значением nil.

( (and (null list1) (null list2)) list3) ;УСЛОВИЕ ВЫХОДА ИЗ

ЦИКЛА

; условие выхода из цикла – равенство nil переменных list1и list2

; возвращается значение переменной list3 – результат всей программы

( cond

; условное предложение

( (null list1)

; Первое условие – если переменная list1 равна nil

(progn

; выполнить последовательность вычислений:

(setq list3 (append list3 list2))

; выполнить слияние значений переменных list3 и list2

; присвоить полученное значение переменной list3

(setq list2 nil)))

; присвоить переменной list2 значение nil

( (null list2)

; Второе условие – если переменная list2 равна nil

(progn (setq list3 (append list3 list1))

; выполнить слияние значений переменных list3 и list1

; присвоить полученное значение переменной list3

(setq list1 nil)))

; присвоить переменной list1 значение nil

( (<= (car list1) (car list2))

; Третье условие – если значение (car list1) меньше или равно

; значения (car list2),

(progn

; то выполнить последовательность вычислений

(setq list3 ( append list3 (cons (car list1) nil) ))

; создать список из головы списка, представленного переменной

list1

; выполнить слияние списка, представленного переменной list3, и

; значения, полученного в предыдущем пункте

; присвоить полученное значение переменной list3

(setq list1 (cdr list1))))

; присвоить переменной list1 значение cdr list1

; Четвертое условие – во всех остальных случаях

(progn

; последовательность вычислений

(setq list3 ( append list3 (cons (car list2) nil) ))

; создать список из головы списка, представленного переменной

list2

; выполнить слияние списка, представленного переменной list3, и

; значения, полученного в предыдущем пункте

; присвоить полученное значение переменной list3

(setq list2 (cdr list2))

; присвоить переменной list2 значение cdr list2

)))

))

Комментированное тестирование программы

> (trace name)

(NAME)

> (name '(1 3 5 7) '(2 4 6))

Entering: NAME, Argument list: ((1 3 5 7) (2 4 6))

Exiting: NAME, Value: (1 2 3 4 5 6 7)

(1 2 3 4 5 6 7)

Контрольной работы № 2

Задание №1. Разработать рекурсивный вариант программы для решения предложенной ниже задачи.

Текст задания:

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

Пример:

?-proc([1,2,3,4,2,5],

[3,77,4,23,2],Res).

L = [23,[3],[[4]],[[[6]]]] ;

Введение. Разрабатываемая процедура должна иметь арность 3. Все параметры процедуры – списки. Первый и второй параметры предназначены для передачи исходных списков, третий соответствует формируемому списку.

Декларативное описание решения. Решение обладает следующими свойствами:

• результирующий список - объединение общих элементов двух исходных списков;

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

• уровень каждого подсписка соответствует его месту в результирующем списке;

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

Комментированный текст программы

/* Разрабатываемая процедура */

proc(List,List1,Result):-

/* искомый список Result как слияние списков List и List1, если

concatх(List,List1,R_prom),

/* R_prom – слияние общих элементов списков List,List1 и */

spi(R_prom,Result).

/* Result – список подуровней списка R_prom */

/* Вспомогательные процедуры */

concatx([],Z,[]). /* НАЧАЛЬНЫЕ УСЛОВИЯ РЕКУРСИИ */

/* Результат слияния пустого списка со списком Z – пустой спи-

сок*/

concatx([X1|Y1],X2,Z1):-

/* первый список состоит из головы X1 и хвоста X2, а результи-

рующий - Z1* если */

nomemb(X1,X2),

/* элемент X1 не встречается в списке X2 и */

concatx(Y1,X2,Z1);

/* Z1- объединение списков Y1 и X2 или */

concatx(Y1,X2,Z),

/* Z – объединение списков Y1 и X2 и */

add(X1,Z,Z1).

/* Z1 состоит из головы X и хвоста Z*/

add(X,T,[X|T]).

/* добавление элемента X в голову списка T */

nomemb(N,X):-

/* элемент N не встречается в списке X если */

not memb(N,X).

/* нет принадлежности элемента N списку X */

memb(N,[N|X]). /* НАЧАЛЬНЫЕ УСЛОВИЯ РЕКУРСИИ */

/* элемент N совпадает с головой списка */

memb(N,[Y|T]):-

/* элемент N не совпадает с головой Y, следовательно*/

memb(N,T).

/* проверить принадлежность элемента N хвосту T */

spo([],[]). /* НАЧАЛЬНЫЕ УСЛОВИЯ РЕКУРСИИ */

/* для пустого исходного списка и список уровней тоже пустой */

spo([X1|Y1],[X1|Y3]):-

/* голова исходного списка X1 становится головой результирующего если */

udal(X1,Y1,T),

/* удалить повторы X1 в хвосте Y1 и */

spo([X1|T],[X1|Y3]);

/* перенести элемент X1 в результирующий список или */

spisok([X1|Y1],[_|Y2]),

/* сформировать подсписок уровня из элемента и */

spo(Y2,Y3).

/* сформировать список уровней */

spisok([],[]). /* НАЧАЛЬНЫЕ УСЛОВИЯ РЕКУРСИИ */

/* для пустого исходного и список уровней пустой */

spisok([X|Y],[[X]|Z]):-

/* голова исходного списка становится подсписком [X] в результирующем списке если */

spisok(Y,Z).

/* списки уровней хвост Y и Z */

udal(X,[X|T],T). /* НАЧАЛЬНЫЕ УСЛОВИЯ РЕКУРСИИ */

/* если элемент совпадает с головой, то результат удаления хвост */

udal(X,[Y|T],[Y|T1]):-udal(X,T,T1).

/* в противном случае удалить элемент из хвоста */

Комментированное тестирование программы

Основная процедура

?- proc([1,2,3,4,2],[3,7,4,2],Res).

Res = [2,[3],[[4]]] ;

Res = [2,[3],[[4]],[[[2]]]] ;

Res = [1,[2],[[3]],[[[4]]]] ;

Res = [1,[2],[[3]],[[[4]]],[[[[2]]]]] ;

Вспомогательные процедуры

?- concatx([1,2,3,4],[2,6,4],Res).

Res = [2,4] ;

Искомое решение

Res = [2,3,4] ;

Res = [1,2,4] ;

Res = [1,2,3,4] ;

После обнаружения требуемого решения процедура может генерировать другие

?- nomemb(3,[1,2,4,5]).

yes

?- memb(3,[1,2,4,5]).

?- add(1,[2,3,4],Res).

Res = [1,2,3,4] ;

?- spisok([[2]],Res).

Res = [[[2]]] ;

?- spo([1,2,3,4,2,5,4],Res).

Res = [1,[2],[[3]],[[[4]]],[[[[5]]]]] ;

Искомое решение

Res = [1,[2],[[3]],[[[4]]],[[[[5]]]],[[[[[4]]]]]] ;

Res = [1,[2],[[3]],[[[4]]],[[[[2]]]],[[[[[5]]]]]] ;

Res = [1,[2],[[3]],[[[4]]],[[[[2]]]],[[[[[5]]]]],[[[[[[4]]]]]]] ;

После обнаружения требуемого решения процедура может генерировать другие

?- udal(2,[3,2,1,4,2,5],Res).

Res = [3,1,4,2,5] ;

Искомое решение

Res = [3,2,1,4,5] ;

После обнаружения требуемого решения процедура может генерировать другие

Задание №2. Разработать вариант программы с использованием средств управления в Прологе.

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

Пример:

?-proc([1,2,3,4,2,5],

[3,77,4,23,2],Res).

L= [23,[3],[[4]],[[[6]]]] ;

Введение. Под средствами управления в Пролог – программе понимается отсечение. Отсечение позволяет прекратить перебор, когда искомое решение найдено и дальнейший поиск не нужен или исключить варианты, которые не приведут к требуемому решению. В решении варианта №2 требуется применить механизм отсечения в процедурах с целью повышения эффективности решения. Разрабатываемая процедура должна иметь арность 3. Все параметры процедуры – списки. Первый и второй параметры предназначены для передачи исходных списков, третий соответствует формируемому списку.

Декларативное описание решения. Аналогично предыдущему варианту. В ряде вспомогательных процедур, которые были разработаны в задании №1, можно использовать отсечение для предотвращения ненужного поиска. Такие процедуры после нахождения требуемого решения продолжали генерировать новые варианты.

Комментированный текст программы. Комментарий записывается после соответствующего утверждения программы.

/* Разрабатываемая процедура */

proc(List,List1,Result):-

/* искомый список Result как слияние списков List и List1 если */

concatх(List,List1,R_prom),

/* R_prom – слияние общих элементов списков List,List1 и */

spi(R_prom,Result).

/* Result – список подуровней списка R_prom */

/* Вспомогательные процедуры */

concatx([],Z,[]). /* НАЧАЛЬНЫЕ УСЛОВИЯ РЕКУРСИИ */

/* Результат слияния пустого списка со списком Z – пустой список*/

concatx([X1|Y1],X2,Z1):-

/* первый список состоит из головы X1 и хвоста X2, а результирующий - Z1* если */

nomemb(X1,X2),

/* элемент X1 не встречается в списке X2 и */

concatx(Y1,X2,Z1);

/* Z1- объединение списков Y1 и X2 или */

concatx(Y1,X2,Z),

/* Z – объединение списков Y1 и X2 и */

add(X1,Z,Z1).

/* Z1 состоит из головы X и хвоста Z*/

add(X,T,[X|T]).

/* добавление элемента X в голову списка T */

nomemb(N,X):-

/* элемент N не встречается в списке X если */

not memb(N,X).

/* нет принадлежности элемента N списку X */

memb(N,[N|X]). /* НАЧАЛЬНЫЕ УСЛОВИЯ РЕКУРСИИ */

/* элемент N совпадает с головой списка */

memb(N,[Y|T]):-

/* элемент N не совпадает с головой Y следовательно*/

memb(N,T).

/* проверить принадлежность элемента N хвосту T */

spo([],[]). /* НАЧАЛЬНЫЕ УСЛОВИЯ РЕКУРСИИ */

/* для пустого исходного списка и список уровней тоже пустой */

spo([X1|Y1],[X1|Y3]):-

/* голова исходного списка X1 становится головой результирующего если */

udal(X1,Y1,T),!,

/* удалить повторы X1 в хвосте Y1 и прекратить перебор*/

Контрольная работа по Функциональное и логическое программирование 📙 Контрольная → 🆔 76000