Форум программистов, компьютерный форум, киберфорум
Lisp
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.89/9: Рейтинг темы: голосов - 9, средняя оценка - 4.89
0 / 0 / 0
Регистрация: 21.05.2012
Сообщений: 11
1

Дерево задано с использованием вложенных списков Определить максимальный уровень вершины

21.05.2012, 20:01. Показов 1781. Ответов 10
Метки нет (Все метки)

Как лучше реализовать данную задачу
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
21.05.2012, 20:01
Ответы с готовыми решениями:

Дерево задано с помощью вложенных списков, определить число вершин в дереве
1. Определите функцию, которая спрашивает имя пользователя и здоровается с ним. (defun hello ()...

Построить бинарное дерево поиска. Определить уровень узла с максимальным элементом
Из входной последовательности вещественных чисел построить бинарное дерево поиска. Определить...

Задано бинарное дерево. Определить, есть ли в этом дереве хотя бы два одинаковых элемента
Не могу никак придумать сам алгоритм. Есть мысли: сравнивать последовательно каждый элемент с...

Определить количество вхождений вершины с заданным элементом Е в бинарное дерево
Добрый день! Помогите решить задачу: Написать программу, которая определяет количество вхождений...

10
Модератор
Эксперт Python
28783 / 15610 / 3100
Регистрация: 12.02.2012
Сообщений: 25,612
Записей в блоге: 4
21.05.2012, 20:26 2
Если считать, что дерево устроено из списков вида:

(Значение Левый Правый) где Левый и правый, в свою очередь, устроены аналогично,
то:

Lisp
1
2
3
4
5
6
7
8
9
(defun max-level (x) (cond ((null x) 0)
                           (t  (max (+ 1 (max-level (cadr x))) 
                                    (+ 1 (max-level (caddr x)))))))
 
==> max-level
 
(max-level '(1 (-1 nil nil) (2 nil (3 nil nil))))
 
==> 3
Списку (1 (-1 nil nil) (2 nil (3 nil nil))) соответствует дерево на прилагаемой картинке:
1
Изображения
 
0 / 0 / 0
Регистрация: 21.05.2012
Сообщений: 11
26.05.2012, 16:21  [ТС] 3
Lisp
1
2
3
4
5
6
7
8
9
(defun max-level (x) (cond ((null x) 0)
                           (t  (max (+ 1 (max-level (cadr x))) 
                                    (+ 1 (max-level (caddr x)))))))
 
==> max-level
 
(max-level '(1 (-1 nil nil) (2 nil (3 nil nil))))
 
==> error: bad function -1

в чем ошибка?? не понимаю
0
Модератор
Эксперт Python
28783 / 15610 / 3100
Регистрация: 12.02.2012
Сообщений: 25,612
Записей в блоге: 4
26.05.2012, 18:00 4
А в каком Лиспе ты запускаешь это?
В HomeLisp все ОК (см. картинку)

И в LispWorks тоже:

Lisp
1
2
3
4
5
6
7
8
CL-USER 1 > (defun max-level (x) (cond ((null x) 0)
(t (max (+ 1 (max-level (cadr x)))
(+ 1 (max-level (caddr x)))))))
MAX-LEVEL
 
CL-USER 2 > (max-level '(1 (-1 nil nil) (2 nil (3 nil nil))))
3
CL-USER 3 >
И в muLisp тоже нормально (см. картинку). Не пропустила ли ты апостроф?
1
Миниатюры
Дерево задано с использованием вложенных списков Определить максимальный уровень вершины   Дерево задано с использованием вложенных списков Определить максимальный уровень вершины  
0 / 0 / 0
Регистрация: 21.05.2012
Сообщений: 11
28.05.2012, 12:13  [ТС] 5
(defun max-level (x) (cond ((null x) 0)
(t (max (+ 1 (max-level (cadr x)))
(+ 1 (max-level (caddr x)))))))

(max-level '(1 (-2 nil nil) (2 nil (3 nil nil))))

так все работает, но если ввожу
(max-level '(1 (2 3)))
он мне выводит error: bad argument type -3

в чем проблема??
0
Модератор
Эксперт Python
28783 / 15610 / 3100
Регистрация: 12.02.2012
Сообщений: 25,612
Записей в блоге: 4
28.05.2012, 14:01 6
Думаю, проблема в том, что в вызове:

Lisp
1
(max-level '(1 (2 3)))
аргумент - не есть дерево. Корень дерева - 1, а где левый и правый узлы? Запись (1 (2 3)) неверна. Возможный вариант:

(1 (2 nil (3 nil nil))) или (1 (2 (3 nil nil)))
0
Эксперт С++
5817 / 3469 / 357
Регистрация: 08.02.2010
Сообщений: 7,448
28.05.2012, 14:27 7
Вот для произвольного дерева (в задании не было сказано, что дерево бинарное):
Lisp
1
2
3
4
5
6
7
8
(defun tree-depth (tree)
  (if tree
      (1+ (apply #'max 0 (mapcar #'tree-depth (cdr tree))))
      0))
 
CL-USER> (tree-depth '(a (b (c) (d (e))) (f (g)) (h)))
4
CL-USER>
Дерево задается в виде списка. Голова списка — это метка корня, хвост — список поддеревьев (может быть пустым)
0
0 / 0 / 0
Регистрация: 21.05.2012
Сообщений: 11
28.05.2012, 16:08  [ТС] 8
я другим образом решила данную проблему:
(defun max-level (x) (cond ((null x) 0)
((atom x) 0)
(t (max (+ 1 (max-level (cadr x)))
(+ 1 (max-level (caddr x)))))))


теперь все работает
0
Модератор
Эксперт Python
28783 / 15610 / 3100
Регистрация: 12.02.2012
Сообщений: 25,612
Записей в блоге: 4
28.05.2012, 16:09 9
Работать-то работает, но что выдает? Смысл выдачи?
0
0 / 0 / 0
Регистрация: 21.05.2012
Сообщений: 11
28.05.2012, 16:24  [ТС] 10
тоже самое и выдает, только теперь еще с атомами может работать

Добавлено через 47 секунд
тоже самое и выдает, только теперь еще и с атомами работает
0
Модератор
Эксперт Python
28783 / 15610 / 3100
Регистрация: 12.02.2012
Сообщений: 25,612
Записей в блоге: 4
28.05.2012, 16:47 11
А что означает атом на этом месте?
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
28.05.2012, 16:47

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Заданы два дерева с помощью цепных списков. *Определить, является ли второе дерево поддеревом первого
Заданы два дерева с помощью цепных списков. *Определить, является ли второе дерево поддеревом...

Задано вершины треугольника ABC: А (7;2), B (1;9) и С(-8;-11)
Задано вершины треугольника ABC: А (7;2), B (1;9) и С(-8;-11). Найти: величину углов A, B, C;...

Определить функцию, объединяющую атомы двух списков С ИСПОЛЬЗОВАНИЕМ ПАРАЛЛЕЛЬНОЙ РЕКУРСИИ
Помогите определить функцию, объединяющую атомы двух списков в один ассоциативный список...

Обработка двух вложенных списков
Есть два списка: 1. 2. Как вывести индексы второго списка, значения которых отличаются от...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.