> 1 <

Автор Сообщение

Елена8_8

Members


Статус

12 сообщений

Где: ---
Род занятий:
Возраст:

#5139   2011-11-29 16:07 GMT+3 часа(ов)      
Напишите программы: Напишите функцию (count t) , считающую количество всех вершин вершин в бинарном дереве t.
Напишите функцию, единственным аргументом которой являлся бы список списков, объединяющую все эти списки в один одноуровневый список.

Ребята выручайте!

VH

Members


Статус

289 сообщений

Где: ---
Род занятий:
Возраст:

#5140   2011-11-29 17:19 GMT+3 часа(ов)      
2.
(defun F (L)
(if L
(let
((elem (car L)))
(cond
((null elem) (F (cdr L)))
((atom elem) (cons elem (F (cdr L))))
(T
(let
((result (F elem)))
(cons (car result) (F (cons (cdr result) (cdr L))))))))))

Елена8_8

Members


Статус

12 сообщений

Где: ---
Род занятий:
Возраст:

#5141   2011-11-29 17:38 GMT+3 часа(ов)      
можно один глупый вопросик?) а что вводить нужно???

VH

Members


Статус

289 сообщений

Где: ---
Род занятий:
Возраст:

#5142   2011-11-29 18:38 GMT+3 часа(ов)      
Вызов
(F '(1 (2 (3 (4 5)) 6) (7 (8) 9)))
возвращает
(1 2 3 4 5 6 7 8 9)

Елена8_8

Members


Статус

12 сообщений

Где: ---
Род занятий:
Возраст:

#5143   2011-11-29 19:03 GMT+3 часа(ов)      
Спасибочки завтра побегу показывать)

VH

Members


Статус

289 сообщений

Где: ---
Род занятий:
Возраст:

#5144   2011-11-29 21:22 GMT+3 часа(ов)      
Если РАЗРЕШЕНО использовать функцию (append):
(defun F (L)
(if L
(let
((elem (car L))
(result (F (cdr L))))
(cond
((null elem) result)
((atom elem) (cons elem result))
(T (append (F elem) result))))))

Елена8_8

Members


Статус

12 сообщений

Где: ---
Род занятий:
Возраст:

#5149   2011-11-30 21:19 GMT+3 часа(ов)      
Спасибо еще раз Сдала сегодня с append!
Не сочтите за наглость но помогите с первой, ПОЖАЛУЙСТА

VH

Members


Статус

289 сообщений

Где: ---
Род занятий:
Возраст:

#5150   2011-11-30 23:45 GMT+3 часа(ов)      
Тогда поясните, что такое «...всех вершин вершин...»

Елена8_8

Members


Статус

12 сообщений

Где: ---
Род занятий:
Возраст:

#5151   2011-12-01 00:16 GMT+3 часа(ов)      
Это описка в задании) Напишите функцию (count t) , считающую количество всех вершин в бинарном дереве t. Так правильно)

VH

Members


Статус

289 сообщений

Где: ---
Род занятий:
Возраст:

#5152   2011-12-01 00:33 GMT+3 часа(ов)      
В каком виде представлено бинарное дерево?

VH

Members


Статус

289 сообщений

Где: ---
Род занятий:
Возраст:

#5153   2011-12-01 00:50 GMT+3 часа(ов)      
«Всех вершин» - это вообще всех узлов или тех узлов, из которых нет ветвей?

Елена8_8

Members


Статус

12 сообщений

Где: ---
Род занятий:
Возраст:

#5154   2011-12-01 01:02 GMT+3 часа(ов)      
Как я поняла произвольное задаем.

VH

Members


Статус

289 сообщений

Где: ---
Род занятий:
Возраст:

#5155   2011-12-01 01:24 GMT+3 часа(ов)      
Можно задать (произвольное, в том числе и бинарное) дерево в виде (идею подарили физтехи) списка пар, что <в нотации LISPа> выглядит как (узел . родитель), при этом корень - это узел, у которого нет родителя (корень).
Например, дерево
     1
/ \
2 3
/ \ / \
4 5 6 7
/ \
8 9

представлено списком
((8 . 7) (9 . 7) (6 . 3) (7 . 3) (4 . 2) (5 . 2) (2 . 1) (3 . 1) (1))

Функция подсчета «листьев» (узлов, из которых не исходят ветви - то есть тех, что не являются родителями):
(defun F (Tree &optional (acc (mapcar 'cdr Tree)))
(if (null Tree) 0
(+ (if (member (caar Tree) acc) 0 1) (F (cdr Tree) acc))))

Функция сбора «листьев»:
(defun F (Tree &optional (acc (mapcar 'cdr Tree)))
(cond
((null Tree) nil)
((member (caar Tree) acc) (F (cdr Tree) acc))
(T (cons (caar Tree) (F (cdr Tree) acc)))))

отредактировал(а) VH: 2011-12-01 01:31 GMT+3 часа(ов)

VH

Members


Статус

289 сообщений

Где: ---
Род занятий:
Возраст:

#5156   2011-12-01 12:23 GMT+3 часа(ов)      
Можно
(defun F (L)
(cond
((null L) nil)
((null (cdr L)) (cons 0 (car L)))
((listp (cdar L))
(let
((result
(F (cons (cons (cdadr L) (car L)) (cddr L)))))
(cons
(+
(if (member (caadr L) (cdr result)) 0 1)
(car result))
(cdr result))))
(T
(let
((result
(F (cons (cons (cdar L) nil) (cdr L)))))
(+
(if (member (cadr L) (cdr result)) 0 1)
(car result))))))

когда по пути «вглубь» накапливается (и передается «вниз») список "родителей", а по пути «наружу» подсчитывается (и передается «наверх») количество узлов, не попавших в список родителей, то есть "листьев".
Примечание. Вариант "корня без ветвей" <пока> корректно не обрабатывается.

Елена8_8

Members


Статус

12 сообщений

Где: ---
Род занятий:
Возраст:

#5184   2011-12-03 15:38 GMT+3 часа(ов)      
«Всех вершин» - это вообще всех узлов или тех узлов, из которых нет ветвей?
на сколько я поняла это узлы у которых есть ветви. т.е. на примере
1

/ \

2 3

/ \ / \

4 5 6 7

/ \

8 9
это будут

отредактировал(а) Елена8_8: 2011-12-03 15:47 GMT+3 часа(ов)

Елена8_8

Members


Статус

12 сообщений

Где: ---
Род занятий:
Возраст:

#5185   2011-12-03 15:38 GMT+3 часа(ов)      
1 2 3 7

VH

Members


Статус

289 сообщений

Где: ---
Род занятий:
Возраст:

#5199   2011-12-04 00:54 GMT+3 часа(ов)      
В случае подсчета узлов с ветвями
Вариант 1:
(defun F (Tree &optional (acc (mapcar 'cdr Tree)))
(if (null Tree) 0
(+ (if (member (caar Tree) acc) 1 0) (F (cdr Tree) acc))))

Вариант 2:
(defun F (L)
(cond
((null L) nil)
((null (cdr L)) (cons 0 (car L)))
((listp (cdar L))
(let
((result
(F (cons (cons (cdadr L) (car L)) (cddr L)))))
(cons
(+
(if (member (caadr L) (cdr result)) 1 0)
(car result))
(cdr result))))
(T
(let
((result
(F (cons (cons (cdar L) nil) (cdr L)))))
(+
(if (member (cadr L) (cdr result)) 1 0)
(car result))))))

Елена8_8

Members


Статус

12 сообщений

Где: ---
Род занятий:
Возраст:

#5272   2011-12-08 01:05 GMT+3 часа(ов)      
Вариант 1:
(defun F (Tree &optional (acc (mapcar 'cdr Tree)))

(if (null Tree) 0

(+ (if (member (caar Tree) acc) 1 0) (F (cdr Tree) acc))))
выдал при (f'((8 . 7) (9 . 7) (6 . 3) (7 . 3) (4 . 2) (5 . 2) (2 . 1) (3 . 1) (1)))
9, то есть количество всех узлов
Вариант 2:
(defun F (L)

(cond

((null L) nil)

((null (cdr L)) (cons 0 (car L)))

((listp (cdar L))

(let

((result

(F (cons (cons (cdadr L) (car L)) (cddr L)))))

(cons

(+

(if (member (caadr L) (cdr result)) 1 0)

(car result))

(cdr result))))

(T

(let

((result

(F (cons (cons (cdar L) nil) (cdr L)))))

(+

(if (member (cadr L) (cdr result)) 1 0)

(car result))))))

выдал при (f'((8 . 7) (9 . 7) (6 . 3) (7 . 3) (4 . 2) (5 . 2) (2 . 1) (3 . 1) (1)))
(8 nil nil nil nil nil nil nil nil 8.7) это вообще непонятно что

VH

Members


Статус

289 сообщений

Где: ---
Род занятий:
Возраст:

#5273   2011-12-08 01:18 GMT+3 часа(ов)      
Оба варианта возвращают 4.
Протокол варианта 1:
XLISP-PLUS version 3.04
Portions Copyright (c) 1988, by David Betz.
Modified by Thomas Almy and others.
> (defun F (Tree &optional (acc (mapcar 'cdr Tree)))
(if (null Tree) 0
(+ (if (member (caar Tree) acc) 1 0) (F (cdr Tree) acc))))
F
>
(f '((8 . 7) (9 . 7) (6 . 3) (7 . 3) (4 . 2) (5 . 2) (2 . 1) (3 . 1) (1)))
4
>

Елена8_8

Members


Статус

12 сообщений

Где: ---
Род занятий:
Возраст:

#5274   2011-12-08 01:42 GMT+3 часа(ов)      
все разобралась) с пробелами напутала

Елена8_8

Members


Статус

12 сообщений

Где: ---
Род занятий:
Возраст:

#5278   2011-12-08 21:11 GMT+3 часа(ов)      
выяснилось что "количество всех вершин" это количество всех элементов в дереве, то есть при вашем примере должно выдать 9

VH

Members


Статус

289 сообщений

Где: ---
Род занятий:
Возраст:

#5281   2011-12-09 00:57 GMT+3 часа(ов)      
Так как наше представление дерева является списком всех узлов дерева (с информацией о "родителе" узла), то функция подсчета количества элементов списка либо может воспользоваться встроенной функцией
(defun F (Tree)
(length Tree))

либо тупо посчитать
(defun F (Tree)
(if Tree (1+ (F (cdr Tree))) 0))

Елена8_8

Members


Статус

12 сообщений

Где: ---
Род занятий:
Возраст:

#5355   2011-12-17 21:44 GMT+3 часа(ов)      
Спасибо все сдала)
> 1 <


Онлайн :

0 пользователь(ей), 43 гость(ей) :