ElpanovEvgeniy | Рекурсии, урок 9

Рекурсии, урок 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: пусть функция удаления вызывается один раз, со списком удаляемых элементов.

Великому и могучему языку посвящается...

Рекурсии, урок 9