VPF::[Lisp] Нужна помощь в решении задачи

Tielvar

Дата 5.12.2008, 14:04 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 13
Регистрация: 5.12.2008

Репутация: нет
Всего: нет

Всем привет 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)))
)

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

Это сообщение отредактировал(а) Tielvar - 5.12.2008, 14:10

adejneka

Дата 6.12.2008, 10:23 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 105
Регистрация: 8.7.2005
Где: Москва, Россия

Репутация: 9
Всего: 11

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

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 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 13
Регистрация: 5.12.2008

Репутация: нет
Всего: нет

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

Код


(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)))

Это сообщение отредактировал(а) Tielvar - 22.12.2008, 18:00

FlashSk

Дата 1.2.2010, 17:41 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 2
Регистрация: 1.2.2010

Репутация: нет
Всего: нет

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

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

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

k0rvin

Дата 4.2.2010, 00:35 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 442
Регистрация: 24.1.2010

Репутация: нет
Всего: 5

Код


;;; 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) '- '+)))

Это сообщение отредактировал(а) k0rvin - 14.2.2010, 02:47

--------------------

“Object-oriented design is the roman numerals of computing.” — Rob Pike
All software sucks

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| LISP \| Следующая тема »