Определить, является ли второе дерево поддеревом первого - 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:

  1. (defun F (ls sub) — определение функции F с двумя аргументами ls и sub.
  2. (cond — начало условной конструкции.
  3. (null ls) nil — проверка, является ли список ls пустым. Если это так, то возвращается nil.
  4. (atom (car ls)) — проверка, является ли первый элемент списка ls атомом. Если это так, то функция F вызывается рекурсивно для оставшейся части списка ls и sub.
  5. (t (if (equal (car ls) sub) — если первый элемент спискаlsравенsub, то возвращаетсяt, иначе выполняется рекурсивный вызов функцииFдля оставшейся части спискаlsиsub`.
  6. (or (F (car ls) sub) (F (cdr ls) sub)) — в противном случае возвращается результат рекурсивного вызова функции F для первого элемента списка ls и sub, или результат рекурсивного вызова функции F для оставшейся части списка ls и sub.
  7. ) — конец условной конструкции.
  8. ; — конец функции F.
  9. nil — результат выполнения функции F при пустом списке ls и sub.
  10. t — результат выполнения функции F при не пустом списке ls и sub.
  11. enter — вызов функции F с тремя аргументами '(a (b (c) (d)) (e (f)) (g (h) (i)) и '(a (b (c)).
  12. nil — результат выполнения функции F при первом вызове.
  13. t — результат выполнения функции F при втором вызове.
  14. t — результат выполнения функции F при третьем вызове.
  15. t — результат выполнения функции F при четвёртом вызове.
  16. t — результат выполнения функции F при пятом вызове.
  17. ) — конец условной конструкции.
  18. ; — конец функции F.
  19. nil — результат выполнения функции F при пустом списке ls и sub.
  20. t — результат выполнения функции F при не пустом списке ls и sub.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

11   голосов , оценка 4.182 из 5
Похожие ответы