Определить, является ли второе дерево поддеревом первого - 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
.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д