Рекурсии в AutoLISP урок 9
На прошлом уроке, мы рассмотрели программу сортировки списка методом выбора или "Selection sort". Очевидно, что его можно улучшить, выбирая не только минимальные значения из списка, но и максимальные. Т.е. мы будем выбирать из списка минимальное и максимальное значения и добавлять их в результирующий список в начало и конец, а оставшийся после удаления первых вхождений этих элементов список будем снова обрабатывать с целью поиска минимального и максимального значений. Этот алгоритм аналогичен предыдущему. Для реализации потребуется три подпрограммы:
1 — поиск самого минимального и максимального значения списка
2 — удаление первого вхождения элемента, заданного аргументом, из списка
3 — запуск в нужной последовательности, первых двух программ и формирование результирующего списка...
(defun rec-min-max (lst mi ma f) ; Вычисляем минимальное и максимальные ; значения списка применяя тестовую функцию (cond ((not lst) (list mi ma)) (((eval f) (car lst) mi) (rec-min-max (cdr lst) (car lst) ma f) ) (((eval f) ma (car lst)) (rec-min-max (cdr lst) mi (car lst) f) ) (t (rec-min-max (cdr lst) mi ma f)) ) ;_ cond ) ;_ defun (defun rec-remove-singl (i lst) ; Удаляем первое вхождение элемента из списка (if lst (if (equal i (car lst)) (cdr lst) (cons (car lst) (rec-remove-singl i (cdr lst))) ) ;_ if ) ;_ if ) ;_ defun (defun rec-sort-min-max (lst f) ;(rec-sort-min-max lst f) (cond ((not lst) nil) ((not(cdr lst)) lst) (t ((lambda (x) (cons (car x) (append (rec-sort-min-max (rec-remove-singl (car x) (rec-remove-singl (cadr x) lst ) ;_ rec-remove-singl ) ;_ rec-remove-singl f ) ;_ rec-sort-lists (cdr x) ) ;_ append ) ;_ cons ) ;_ lambda (rec-min-max (cdr lst) (car lst) (car lst) f) ) ) ) ;_ cond ) ;_ defun ; Проверим: (setq lst '(7 3 4 6 9 6 7 2 5 3 2 3 6 4 6 3 1) f (function <) ) ;_ setq (rec-sort-min-max lst f) ; Возвращает ; '(1 2 2 3 3 3 3 4 4 5 6 6 6 6 7 7 9)
Т.к. работа рекурсии очень похожа на рассмотренную на восьмом уроке, я собираюсь более коротко рассматривать работу функций, делая акцент на изменениях. Рассмотрим работу рекурсии, которая ищет минимальное и максимальные значения.
(defun rec-min-max (lst mi ma f) ; Вычисляем минимальное и максимальные ; значения списка применяя тестовую функцию (cond ((not lst) (list mi ma)) (((eval f) (car lst) mi) (rec-min-max (cdr lst) (car lst) ma f) ) (((eval f) ma (car lst)) (rec-min-max (cdr lst) mi (car lst) f) ) (t (rec-min-max (cdr lst) mi ma f)) ) ;_ cond ) ;_ defun ; Проверим: (setq lst '(7 3 4 6 9 6 7 2 5 3 2 3 6 4 6 3 1) f (function <) ) ;_ setq (rec-min-max (cddr lst) (car lst)(car lst) f) ; Возвращает ; '(1 9)
Как видно из кода — программа отличается от rec-min дополнительным аргументом и дополнительной проверкой... Дополнительный аргумент — переменная, в которой будем сохранять максимальное значение, а дополнительная проверка, для его поиска.
(defun rec-min-max (lst mi ma f) (cond ((not lst) ; Если кончился список (list mi ma) ; Возвращаем список из минимального и максимального значения ) (((eval f) ; Активируем функцию (car lst) ; Первый элемент списка mi ; Текущее минимальное значение ) ; Если Т переходим на следующую строку и меняем минимальное значение (rec-min-max ; Самовызов рекурсии (cdr lst) ; Укороченный список (car lst) ; Новое минимальное значение ma ; Старое максимальное значение f ; Тестовая функция ) ;_ rec-min-max ) (((eval f) ; Активируем функцию ma ; Текущее максимальное значение (car lst) ; Первый элемент списка ) ; Если Т переходим на следующую строку и меняем максимальное значение (rec-min-max ; Самовызов рекурсии (cdr lst) ; Укороченный список mi ; Старое минимальное значение (car lst) ; Новое максимальное значение f ; Тестовая функция ) ;_ rec-min-max ) (t ; Если дошли, всегда правда (rec-min-max ; Самовызов рекурсии (cdr lst) ; Укороченный список mi ; Старое минимальное значение ma ; Старое максимальное значение f ; Тестовая функция ) ;_ rec-min-max ) ) ;_ cond ) ;_ defun ; Проверим: (setq lst '(10 7 3 4 6 9 6 7 2 5 3 2 3 1 6 4 6 3) f (function <) ) ;_ setq (rec-min-max (cddr lst) (car lst)(car lst) f) ; Возвращает ; '(1 10)
Функция удаления первого вхождения элемента не изменилась, поэтому я ее не рассматриваю. Изменение основной функцией интереснее. Нужна еще одна проверка на длину списка, т.е. перед поиском минимального и максимального значений, нужно проверить, что список имеет более одного элемента и если список состоит из одного элемента искать минимальное и максимальное значения бессмысленно. Для этой проверки будем пользоваться выражением:
(not(cdr lst)) ;Если список без первого элемента не пустой.
Такой подход быстрее, чем:
(> (length lst) 1)
Далее все по аналогии с предыдущей функцией rec-sort-min. Два раза вызываем функцию удаления первого вхождения элемента, первый раз для минимального, второй для максимального значения. Потом формируем окончательный список, минимальное значение ставим в начало функцией cons а максимальное append ...
(defun rec-sort-min-max (lst f) (cond ((not lst) ; Если кончился список nil ) ((not (cdr lst)) ;Если список без первого элемента не пустой. lst ; Список с одним элементом ) (t ((lambda (x) ;; Пользовательская функция ;; С аргументом — список из минимального ;; и максимального значения (cons ; Формируем начало списка (car x) ; Минимальное значение списка (append ; Формируем конец списка (rec-sort-min-max (rec-remove-singl (car x) (rec-remove-singl (cadr x) lst ) ;_ заканчиваем удаление максимального значения ) ;_ заканчиваем удаление минимального значения f ; Тестовая функция ) ;_ заканчиваем рекурсию для дочерней рекурсии с укороченным списком (cdr x) ; Максимальное значение списка ) ;_ append ) ;_ cons ) ;_ lambda (rec-min-max (cdr lst) (car lst) (car lst) f) ; Поиск минимального и максимального значения ) ) ) ;_ cond ) ;_ defun ; Проверим: (setq lst '(7 3 4 6 9 6 7 2 5 3 2 3 6 4 6 3 1) f (function <) ) ;_ setq (rec-sort-min-max lst f) ; Возвращает ; '(1 2 2 3 3 3 3 4 4 5 6 6 6 6 7 7 9)
Хотелось бы добавить, что этот вариант сортировки быстрее предыдущего не значительно. Его можно еще улучшить, например, изменив функцию удаления, чтоб она брала в качестве аргумента список...
Задание для самостоятельной работы:
Измените программу из урока 9: пусть функция удаления вызывается один раз, со списком удаляемых элементов.
Старая версия сайта, доступна здесь.