Определить, является ли второе дерево поддеревом первого - Lisp
Формулировка задачи:
Нужна помощь, задача описана в заголовке. Смотрел похожие задачи, но не получается реализовать. Например у нас есть цепной список
его поддеревьями могут быть списки:
и так далее.
(a(b(c)(d))(e(f))(g(h)(i))),
(a(b)(e)) (a(b(c))) (e(f))
Решение задачи: «Определить, является ли второе дерево поддеревом первого»
textual
Листинг программы
(defun F (ls sub) (cond ((null ls) nil) ((atom (car ls)) (F (cdr ls) sub)) (t (if (equal (car ls) sub) t (or (F (car ls) sub) (F (cdr ls) sub)))))) ;; enter (F '(a (b (c) (d)) (e (f)) (g (h) (i))) '(a (b (c)))) ; nil (F '(a (b (c) (d)) (e (f)) (g (h) (i))) '(b (c) (d))) ; t (F '(a (b (c) (d)) (e (f)) (g (h) (i))) '(e (f))) ; t (F '(a (b (c) (d)) (e (f)) (g (h) (i))) '(b (c) (d))) ; t
Объяснение кода листинга программы
В данном коде определённая функция F проверяет, является ли второе дерево поддеревом первого. Для этого используется рекурсивный подход.
Вот список элементов кода с 1 по 20:
(defun F (ls sub)— определение функцииFс двумя аргументамиlsиsub.(cond— начало условной конструкции.(null ls) nil— проверка, является ли списокlsпустым. Если это так, то возвращаетсяnil.(atom (car ls))— проверка, является ли первый элемент спискаlsатомом. Если это так, то функцияFвызывается рекурсивно для оставшейся части спискаlsиsub.(t (if (equal (car ls) sub) — если первый элемент спискаlsравенsub, то возвращаетсяt, иначе выполняется рекурсивный вызов функцииFдля оставшейся части спискаlsиsub`.(or (F (car ls) sub) (F (cdr ls) sub))— в противном случае возвращается результат рекурсивного вызова функцииFдля первого элемента спискаlsиsub, или результат рекурсивного вызова функцииFдля оставшейся части спискаlsиsub.)— конец условной конструкции.;— конец функцииF.nil— результат выполнения функцииFпри пустом спискеlsиsub.t— результат выполнения функцииFпри не пустом спискеlsиsub.enter— вызов функцииFс тремя аргументами'(a (b (c) (d)) (e (f)) (g (h) (i))и'(a (b (c)).nil— результат выполнения функцииFпри первом вызове.t— результат выполнения функцииFпри втором вызове.t— результат выполнения функцииFпри третьем вызове.t— результат выполнения функцииFпри четвёртом вызове.t— результат выполнения функцииFпри пятом вызове.)— конец условной конструкции.;— конец функцииF.nil— результат выполнения функцииFпри пустом спискеlsиsub.t— результат выполнения функцииFпри не пустом спискеlsиsub.