рекурсия

@getshaky98 · Регистрация: 01.03.2017

Author24 — интернет-сервис помощи студентам

Прочитать из стандартного потока ввода двоичное дерево, представленное с помощью списков. Первый элемент в списке является значением узла, второй элемент – левым поддеревом (списком) или значением 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, этот результат и следует вывести в стандартный поток вывода.

@Catstail · 26.03.2017, 08:22

Lisp

(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

@getshaky98 0 / 0 / 0 Регистрация: 01.03.2017 Сообщений: 48
		1
	рекурсия 25.03.2017, 17:51. Показов 1571. Ответов 1 Метки деревья (Все метки) Прочитать из стандартного потока ввода двоичное дерево, представленное с помощью списков. Первый элемент в списке является значением узла, второй элемент – левым поддеревом (списком) или значением 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, этот результат и следует вывести в стандартный поток вывода. 0

	26.03.2017, 08:22