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

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

     
 
 

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

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

   Контрольная работа №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

(t

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