Рекурсия - Lisp (229104)

Формулировка задачи:

Прочитать из стандартного потока ввода двоичное дерево, представленное с помощью списков. Первый элемент в списке является значением узла, второй элемент – левым поддеревом (списком) или значением nil, если у данного узла нет левого потомка, третий элемент – правым поддеревом (списком) или значением nil, если у данного узла нет правого потомка. В качестве значения в узле могут храниться любые данные, в том числе целые числа. Найти сумму кратных 5 целых чисел, хранящихся в узлах дерева, расположенных на уровнях с четными номерами. Уровень корня принимается равным 1. Если в дереве нет удовлетворяющих условиям задачи узлов, считать сумму равной 0. Пример: Дано дерево (1 (10 (15 nil nil) (7 nil nil)) (5 (2 nil nil) (8 nil nil))). На первом уровне здесь находится узел со значением 1 (это корень), на втором – узлы со значениями 3 и 5, на третьем – узлы со значениями 15 и 7 (потомки узла 3) и узлы со значениями 2 и 8 (потомки узла 5). Обходя это дерево (в любом порядке, но учитывая номер уровня) находим, что на четных уровнях (в данном случае четный уровень только один) находятся узлы со значениями 10 и 5. Оба числа кратны 5, их сумма равна 15, этот результат и следует вывести в стандартный поток вывода.

Решение задачи: «Рекурсия»

Листинг программы

(defun task-4 (tree &optional (lv 1))
  (cond ((null tree) 0)
        ((and (evenp lv) (numberp (car tree)) (zerop (rem (car tree) 5))) 
         (+ (car tree) (task-4 (cadr tree) (+ lv 1)) (task-4 (caddr tree) (+ lv 1))))
        (t (+ (task-4 (cadr tree) (+ lv 1)) (task-4 (caddr tree) (+ lv 1))))))
 
==> TASK-4
 
(task-4 ' (1 (10 (15 nil nil) (7 nil nil)) (5 (2 nil nil) (8 nil nil))))
 
==> 15

Объяснение кода листинга программы

Объяснение действий в коде:

defun определяет функцию с именем task-4.
Аргументы функции: tree и опциональный аргумент lv, который по умолчанию равен 1.
Условие cond проверяет, является ли tree пустым. Если это так, то функция возвращает 0.
Если tree не пуст, то проверяется, является ли текущий уровень lv четным и является ли первый элемент car tree числом, которое делится на 5 без остатка. Если все условия выполняются, то функция рекурсивно вызывается для оставшейся части tree, увеличивая lv на 1.
Если условия не выполняются, то функция рекурсивно вызывается для cadr tree и caddr tree, также увеличивая lv на 1.
Если ни одно из условий не выполняется, то функция рекурсивно вызывается только для cadr tree и caddr tree, увеличивая lv на 1.
В итоге, функция возвращает сумму значений всех чисел в tree, которые делятся на 5 без остатка. Пример вызова функции: (task-4 ' (1 (10 (15 nil nil) (7 nil nil)) (5 (2 nil nil) (8 nil nil)))) В этом примере функция вызывается с аргументом tree, который представляет собой список вложенных списков. Функция рекурсивно обрабатывает каждый элемент списка и возвращает 15 в качестве результата.