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

    Содержание отчета

  1. Постановка задачи
  2. Описание алгоритма
  3. Описание функций
  4. Оценка сложности алгоритмов
  5. Текст программы
  6. Результаты












1. Постановка задачи

В кольце записано N цифр , составляющих по часовой стрелке три
числа : два слагаемых и сумму .
Необходимо написать программу на языке функционального программиро-
вания Лисп , которая запрашивает список цифр составляющих кольцо и
печатает решение в виде : A+B=C . Если данный список не содержит
описанного разложения то программа должна сообщить об этом .
Все числа положительны , числа входят в число один раз и в порядке
их следования в кольце .
Пример :

Список : 0 1 9 0 2 0 2 1
Решение : 190 + 20 = 210








2. Описание алгоритма
разложения списка на два слагаемых
и сумму

2.1. Основная функция

<Поиск решения>::=
Если входной список пуст ,

то результат ni ;
Если <Поиск разложения списка> удачен ,
то результат T ,
Иначе
результат nil ;











2.2. Функция поиска разложения
списка

<Поиск разложения списка>::=
Если список повторяется после одного из <Поисков разложения списка>,

то результат ni ,
Иначе
Если (список не повторяется) и (нет <Разложения списка>), то
преобразовать список , установить первым слагаемым первый элемент
списка , <Поиск разложения списка> .

Примечание :
под преобразованием списка понимается перемещение головы списка
в конец .








2.3. Функция разложения списка

<Разложение списка>::=
Если длина первого слагаемого больше половины длины списка , то

результат ni ;
Если удачно (<Разложение с фиксированным первым слагаемым> , где
длина второго слагаемого равна 1)
, то
результат T ;
Если нет (<Разложения списка> с длиной первого слагаемого на 1
больше)
, то
результат nil ;








2.4. Функция разложение с фиксированным
первым слагаемым

<Разложение с фиксированным первым слагаемым>::= Если длина второго слагаемого больше половины длины списка , то

результат ni ;
Если сумма первого и второго слагаемого не равна числу из оставшейся
части списка , то
(<Разложение с фиксированным первым слагаемым> где длина второго
слагаемого увеличена на 1)
,
Иначе
результат T ;













3. Описание функций

3.1. Функция main_

Алгоритм функции представлен в п. 2.1.
Синтаксис :
(main_ s)
где:

s - список для которого ищется разложение ;
Описание :
Функция предназначена для поиска разложения списка s , на
два слагаемых и сумму .







3.2. Функция gl

Алгоритм функции представлен в п. 2.2.
Синтаксис :
(gl s kol s1 z m)
где:

s - список для которого надо найти разложение ;
s1 - эталонный список ;
ko - количество первых атомов занимаемых 1-м числом ;
z - флаг повторения списка в обработке ;
m - половина длины списка s ;
Описание :
Данная функция производит преобразование исходного списка если
для данного списка s не найдется прямого разложения.
Преобразование списка состоит в перемещении 1-го элемента
списка в его конец .
Список s1 служит эталоном для проверки окончания вычислений , т. е.
при совпадении списков s и s1 , и z=2 происходит прекращение
выполнения функции , при первоначальном вызове функции следует
флаг z устанавливать в 0. m - показывает половину длины списка s.
kol - показывает сколько первых элементов списка занимает первое
слагаемое .
Если поиск удачен то возвращается T , иначе nil.







3.3. Функция go_cnt

Алгоритм функции представлен в п. 2.3.
Синтаксис :
(go_cnt s kol m)
где:

s - список для которого ищется разложение ;
ko - количество атомов занимаемых 1-м слагаемым ;
m - половина длины списка ;
Описание :
Функция производит рекурсивный поиск разложения в списке s
без какого либо его преобразования , при поиске меняются
длины первых слагаемых , длина первого слагаемого содержится
в kol , m - половина длины списка .
Если поиск удачен то возвращается T , иначе nil.







3.4. Функция add_

Алгоритм функции описан в п. 2.4.
Синтаксис :
(add_ s kol ch kol1 m)
где :

s - список для которого ищется разложение ;
ko - количество атомов занимаемых 1-м слагаемым ;
ch - значение первого слагаемого ;
kol1 - количество атомов занимаемых 2-м слагаемым ;
m - половина длины списка s ;
Описание :
Данная функция производит поиск разложения списка s , при этом
длина первого слагаемого остается постоянной и равной kol ,
поиск происходит за счет изменения длины второго слагаемого ,
его длина указывается в kol1 . ch - значение первого слагаемого ;
m - половина длины списка ;
Если поиск удачен то возвращается T , иначе nil.







3.5. Функция получения
числа из списка perevod_

Синтаксис:
(perevod_ s kol)
где :
s - список из которого выделяется число ;
kol - количество атомов занимаемых числом ;
Описание :
Функция возвращает число которое выделяется из списка s ,
при этом число будет состоять из первых kol атомов списка.

3.6. Функция присоединения
атома в конец списка list_

Синтаксис :
(list_ s a)
где :

s - список к которому присоединяется атом ;
a - присоеденяемый атом ;
Описание :
Функция присоединяет в конец списка s атом a , и выдает
полученный список в качестве возвращаемого значения .







3.7. Функция проверки
на конец вычислений equalient

Синтаксис :
(equalient s kol kol1)
где :

s - список который нужно проверить, есть ли в нем
нужное разложение ;
kol - длина первого слагаемого в списке s ;
kol1 - длина второго слагаемого в списке s ;
Описание :
Функция возвращает T , если в списке s выполняется
условие : 1-е слагаемое + 2-е слагаемое = сумма ;
При этом 1-е слагаемое состоит из первых kol - атомов
списка s , второе из следующих kol1 атомов , а сумма
из оставшейся части списка.
Если условие не выполняется то возвращается nil













4. Оценка сложности алгоритмов

Алгоритмы функций поиска разложения списка получились не сложными по
своей структуре , но потребовалось применить ряд вспомогательных
функций типа : перевод списка в число , сравнение двух списков
на равенство и т. д.
Для решения данной задачи Лисп будет создавать довольно глубокие
списки вложенностей , которые напрямую связаны с длиной списка для
разложения. Чем длинее список тем больше вложенность , даже при
длине слагаемых равных 2 цифрам и прямом расположении чисел (это
исключает возможность вложений за счет преобразований списка )
мы получим вложенность порядка 4. Для длинных списков порядка 10
атомов существует большая вероятность переполнения стека и вследствие
этого неверная работа программ .













5. Текст программы

(defun eq1 (s s1) ;сравнение на эквивалентность списков
(cond ((and (null s) (null s1)) T)
((= (car s) (car s1)) (eq1 (cdr s) (cdr s1)))
(T nil)
)
)

(defun revers (s kol) ;обращение списка
(cond ((= kol 0) nil)
(T (list_ (revers (cdr s) (1- kol)) (car s)))
)
)

(defun perevod (s kol) ;перевод списка в число
(perevod_ (revers s kol) kol)
)

(defun perevod_ (s kol) ;получение числа из списка
(cond ((= kol 0) 0)
(T (+ (* 10 (perevod_ (cdr s) (1- kol)))
(car s))
)
)
)

(defun list_ (s a) ;присоеденение атома в конец списка
(cond ((null s) (cons a ()))
(T (cons (car s) (list_ (cdr s) a))
)
)
)

(defun trunc_ (s kol) ;отсучение списка длиной kol из заданого s
(cond ((= kol 0) s)
(T (trunc_ (cdr s) (1- kol))
)
)
)

(defun cnt (s) ;подсчет длины списка
(cond ((null s) 0)
(T (+ 1 (cnt (cdr s)))
)
)
)

(defun go_cnt (s kol m) ;функция разложения списка
(cond ((or (> ko m) (sld s kol)) nil)
((add_ s kol (perevod s kol) 1 m) T)
((not (go_cnt s (1+ kol) m)) nil)
(T T)
)
)

(defun gl (s kol s1 z m) ;поиск разложения списка
(cond ((and (not (and (eq1 s s1) (= z 2)))
(not (go_cnt s kol m)))
(setq kol 1)
(setq s (list_ (cdr s) (car s)))
(gl s kol s1 2 m))
((and (eq1 s s1)
(= z 2))
(print 'No-solution) T)
(T T)
)
)

(defun add_ (s kol ch kol1 m) ;функция разложение с фиксированным
первым слагаемым
(cond ((< m kol1) nil)
((not (equalient s kol kol1))
(add_ s kol ch (1+ kol1) m))
(T (prin1 (perevod s kol))
(prin1 '+)
(prin1 (perevod (trunc_ s kol) kol1))
(prin1 '=)
(print (perevod (trunc_ s (+ kol kol1))
(- (cnt s)
(+ kol kol1))))T)
)
)

(defun equalient (s kol kol1) ;проверка на конец вычислений
(= (+ (perevod s kol)
(perevod (trunc_ s kol) kol1))
(perevod (trunc_ s (+ kol kol1))
(- (cnt s) (+ kol kol1)))
)
)

(defun sld (s kol) ;проверка на повторы цифр в числе
(setq m1 (car (trunc_ s kol)))
(eque s kol m1)
)

(defun eque (s kol m) ;проверка цифр в числе
(cond ((= kol 0) nil)
((= (car s) m) T)
(T (eque (cdr s) (1- kol) m))
)
)

(defun main_ (s) ;главная функция поиска разложения списка
(cond ((null s) nil)
((gl s 1 s 0 (/ (cnt s) 2)))
(T nil)
)
)















6. Результаты

> (main_ '(0 1 0 2 0 3))
Entering: MAIN_, Argument ist: ((0 1 0 2 0 3))
Entering: GL, Argument list: ((0 1 0 2 0 3) 1 (0 1 0 2 0 3) 0 3)
Entering: GO_CNT, Argument list: ((0 1 0 2 0 3) 1 3)
Entering: GO_CNT, Argument list: ((0 1 0 2 0 3) 2 3)
1+2=3
Exiting: GO_CNT, Value: T
Exiting: GO_CNT, Value: T
Exiting: GL, Value: T
Exiting: MAIN_, Value: T
T

> (main_ '(1 0 5 6 1))
Entering: MAIN_, Argument list: ((1 0 5 6 1))
Entering: GL, Argument list: ((1 0 5 6 1) 1 (1 0 5 6 1) 0 2)
Entering: GO_CNT, Argument list: ((1 0 5 6 1) 1 2)
Entering: GO_CNT, Argument list: ((1 0 5 6 1) 2 2)
Entering: GO_CNT, Argument list: ((1 0 5 6 1) 3 2)
Exiting: GO_CNT, Value: NIL
Exiting: GO_CNT, Value: NIL
Exiting: GO_CNT, Value: NIL
Entering: GL, Argument list: ((0 5 6 1 1) 1 (1 0 5 6 1) 2 2)
Entering: GO_CNT, Argument list: ((0 5 6 1 1) 1 2)
Entering: GO_CNT, Argument list: ((0 5 6 1 1) 2 2)
5+6=11
Exiting: GO_CNT, Value: T
Exiting: GO_CNT, Value: T
Exiting: GL, Value: T
Exiting: GL, Value: T
Exiting: MAIN_, Value: T
T