Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > LISP > [Lisp] Нужна помощь в решении задачи

Автор: Tielvar 5.12.2008, 14:04

Всем привет smile

Оговорюсь сразу - я с лиспом знаком оччень поверхостно, строго не судите smile

Сабж: Надо посчитать среднее арифметическое листьевых вершин бинарного дерева. Узел хранит целое число и два поддерева. Я так прикинул, прийдётся задачу решат ьв два захода - сначала узнать сумму значений в листьевых вершинах, затем узнать их количество, и поделить результаты. То есть имеем три функции.
Первая, считает сумму значений в листьях:

Код


(defun val (tree)
    (cond
        ((null (cdr tree)) (first tree))  ;; лист, потомков нет, возвращает значение
        ((null (second tree)) (val (third tree)))  ;; нет левого потомка, значит есть правый, рекурсия
        ((null (third tree)) (val (second tree)))  ;; нет правого потомка, значит есть левый, рекурсия
        (t (+ (val (second tree)) (third tree)))   ;; оба потомка есть, сумма двух рекурсивных вызовов
    )
)

Вторая - количество листьев:

Код


(defun num (tree)
    (cond  ;; всё идентично первому коду, за исключением
        ((null (cdr tree)) 1)  ;; этого места - если лист, возвращает единицу
        ((null (second tree)) (num (third tree))) 
        ((null (third tree)) (num (second tree)))
        (t (+ (num (second tree)) (num (third tree))))
    )
)

Третья, типа мейн:

Код


;; получает сумму значений в листьях, количество листьев и делит сумму на количество слагаемых.
(defun res (a)
    (progn (setq x (val a)) (setq y (num a) (/ x y)))
)

Причем ни одна функция не работает :((( Помогите пожалуйста.

Автор: adejneka 6.12.2008, 10:23

Проблема состоит в том, что бы четко определиться с представлением дерева. Одно правило есть:

2. Дерево-узел - это список ``(VAL LEFT RIGHT)'', где VAL - число ("значение узла"), LEFT и RIGHT - деревья.

Нужно еще основание рекурсии. Я предлагаю такое:

1. Пустое дерево - это символ NIL (= пустой список).

Можно определить вспомогательные функции для проверки на пустоту, лист.

Код


(defun tree-node-value (tree)
  (first tree))

(defun tree-left-child (tree)
  (second tree))

(defun tree-right-child (tree)
  (third tree))

(defun tree-empty-p (tree)
  (eq tree 'nil))

(defun tree-leave-p (tree)
  (and (not (tree-empty-p tree))
       (tree-empty-p (tree-left-child tree))
       (tree-empty-p (tree-right-child tree))))

Код


(defun sum-leaves (tree)
  (cond
    ((tree-empty-p tree) 0)
    ((tree-leave-p tree) (tree-node-value tree))
    (t (+ (sum-leaves (tree-left-child tree))
          (sum-leaves (tree-right-child tree))))))

CL-USER> (sum-leaves '(4 (3 () ()) ()))
3
CL-USER> (sum-leaves '(4 (3 () ()) (2 () ())))
5

Автор: Tielvar 22.12.2008, 17:59

Спасибо за помощь. Вот что в результате у меня вышло:

Код


(defun node (tree)
  (first tree))

(defun left (tree)
  (second tree))

(defun right (tree)
  (third tree))

(defun empty (tree)
  (eq tree 'nil))

(defun leaf (tree)
  (and (not (empty tree))
       (empty (left tree))
       (empty (right tree))))
(defun sum-leaves (tree)
  (cond
    ((empty tree) 0)
    ((leaf tree) (node tree))
    (t (+ (sum-leaves (left tree))
          (sum-leaves (right tree))))))
(defun number (tree)
  (cond
    ((empty tree) 0)
    ((leaf tree) 1)
    (t (+ (number (left tree))
          (number (right tree))))))
(defun res (tree)
  (/ (sum-leaves tree)
     (number tree)))

Автор: FlashSk 1.2.2010, 17:41

Помогите решить задачи:
1)
Написать функцию, которая по заданому целому числу формирует список двох елементов. Первый елемент списка - ето символьный атом, что обозначает знак числа, второй елемент – остаток от деления числа на 2.

2)
Написать функцию, которая для заданних списков lst1 і lst2 возвращает список, который содержит их первые и последние елементи. Порядок прохождения елементов в результуючем списке опредиляется вторым елементом lst2: если ето число, то сначала идуть первый и последний елементи lst1, иначе – первый и последний елементи lst2.

3)
Написаьи функцию, которая по двох числах формирует список с трех елементов. Первый елемент – ето результат целочисельнного распредиления чисел, другой єсть результат множения чисел, третий елемент єсть символьный атом, что обозначает знак числа. Функция должна иметь проверку деления на ноль!

Автор: k0rvin 4.2.2010, 00:35

Код


;;; 1
(defun task1 (x)
  (list (if (< x 0) '- '+) (rem x 2)))

;;; 2
(defun task2 (lst1 lst2)
  (labels ((f&l (xs) (list (first xs) (car (last xs)))))
    (if (numberp (second lst2))
        (append (f&l lst1) (f&l lst2))
        (append (f&l lst2) (f&l lst1)))))

;;; 3
(defun task3 (x y)
  (when (zerop y) (error "Division by zero."))
  (let ((m (* x y)))
    (list (floor x y) m (if (< m 0) '- '+)))