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