Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > Lisp
Перезагрузить страницу Как понять написанную программу
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
4x10 4x10 вне форума
Member
 
Сообщений: 23
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 07.05.2007
По умолчанию Как понять написанную программу - 10.05.2007, 22:19

Кто нибудь может объяснить эту прогу!

Код:
(defun tree-node (tree)
  (car tree))
(defun tree-left (tree)
  (cadr tree))
(defun tree-right (tree)
  (caddr tree))

(defun tree-find (item tree)
  (if (atom tree)
      (eql item tree)
      (let ((node (tree-node tree)))
        (cond ((eql item node)
               t)
              ((< item node)
               (tree-find item (tree-left tree)))
              (t
               (tree-find item (tree-right tree)))))))
Цитата:
(tree-find 1 '(4 (2 0 3) (6 nil 8))) => NIL
(tree-find 2 '(4 (2 0 3) (6 nil 8))) => T
TREE-FIND
> (tree-find 4 '(4 (2 0 3) (6 nil 8)))
T
> (tree-find nil '(4 (2 0 3) (6 nil 8)))
error: bad argument type - NIL
> (tree-find 8 '(4 (2 0 3) (6 nil 8)))
T
> (tree-find 6 '(4 (2 0 3) (6 nil 8)))
T
> (tree-find 6 '(4 (2 0 3) (6 4 8)))
T
> (tree-find 6 '(4 (2 3) (6 8)))
T
> (tree-find 6 '(4 (2 3) (8 )))
NIL
> (tree-find 4 '(5 (2 3) (4 8)))
NIL
> (tree-find 4 '(1 (2 3) (4 8)))
T
Ответить с цитированием
  (#2 (permalink)) Старый
Alexey Dejneka Alexey Dejneka вне форума
Member
 
Сообщений: 451
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 23.11.2004
По умолчанию 10.05.2007, 22:47

В этой программе считается, что дерево может:
1.Быть пустым - представляется атомом NIL.
2. Содержать одну вершину, помеченную числом - представляется числом.
3. Содержать узел, помеченный числом, и два поддерева - левое и правое. Представляется списком из трех элементов - числа, левого поддерева, правого поддерева. При этом считается, что все элементы (числовые пометки) левого поддерева не превышают пометки узла, а все элементы правого поддерева - не меньше пометки узла.

Алгоритм поиска числа X в дереве: если дерево образовано по п. 1, X в дереве нет. Если дерево образовано по правилу 2, X содержится в дереве <=> оно совпадает с пометкой. Если дерево образовано по правилу 3, то надо сравнить X с пометкой узла: если совпадает - то X найден, если меньше - надо искать в левом поддереве, иначе в правом.

Теперь я еще раз повторяю свой вопрос: как у Вас определяется упорядоченное бинарное дерево в общем случае? Я не понимаю смысла задания "искать в бинарном дереве, содержащем числа от 1 до 6" - можно просто забыть про "... дерево" и проверять, что на вход подано число от 1 до 6.
Ответить с цитированием
  (#3 (permalink)) Старый
4x10 4x10 вне форума
Member
 
Сообщений: 23
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 07.05.2007
По умолчанию 10.05.2007, 23:45

Цитата:
В этой программе считается, что дерево может:
1.Быть пустым - представляется атомом NIL.
2. Содержать одну вершину, помеченную числом - представляется числом.
3. Содержать узел, помеченный числом, и два поддерева - левое и правое. Представляется списком из трех элементов - числа, левого поддерева, правого поддерева. При этом считается, что все элементы (числовые пометки) левого поддерева не превышают пометки узла, а все элементы правого поддерева - не меньше пометки узла.

Алгоритм поиска числа X в дереве: если дерево образовано по п. 1, X в дереве нет. Если дерево образовано по правилу 2, X содержится в дереве <=> оно совпадает с пометкой. Если дерево образовано по правилу 3, то надо сравнить X с пометкой узла: если совпадает - то X найден, если меньше - надо искать в левом поддереве, иначе в правом.

Теперь я еще раз повторяю свой вопрос: как у Вас определяется упорядоченное бинарное дерево в общем случае? Я не понимаю смысла задания "искать в бинарном дереве, содержащем числа от 1 до 6" - можно просто забыть про "... дерево" и проверять, что на вход подано число от 1 до 6.
Спасибо за ответ, я вас понял, вы похоже всё правильно выполнили это я понять не могу, теперь я начал немного понимать, но могли бы вы ёще показать как ваше дерево выглядит.
Ответить с цитированием
  (#4 (permalink)) Старый
Alexey Dejneka Alexey Dejneka вне форума
Member
 
Сообщений: 451
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 23.11.2004
По умолчанию 11.05.2007, 08:34

Цитата:
можно, чтобы дерево задавалось в файле и потом считывалось от туда и происходил поиск.
Код:
(defun read-tree (filename)
  (with-open-file (s filename)
    (read s)))
Если в файле tree.txt записано (5 (2 1 3) (8 nil 9)), то
Код:
CL-USER> (tree-find 3 (read-tree "tree.txt"))
T
CL-USER> (tree-find 6 (read-tree "tree.txt"))
NIL
Данный список соответствует следующему дереву: корень - 5, два поддерева; у левого корень 2 и поддеревья 1 и 3; у правого корень 8, левое поддерево пусто, правое - 9.
Ответить с цитированием
  (#5 (permalink)) Старый
4x10 4x10 вне форума
Member
 
Сообщений: 23
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 07.05.2007
По умолчанию 11.05.2007, 11:19

Цитата:
Код:
(defun read-tree (filename)
  (with-open-file (s filename)
    (read s)))
Если в файле tree.txt записано (5 (2 1 3) (8 nil 9)), то
Код:
CL-USER> (tree-find 3 (read-tree "tree.txt"))
T
CL-USER> (tree-find 6 (read-tree "tree.txt"))
NIL
Данный список соответствует следующему дереву: корень - 5, два поддерева; у левого корень 2 и поддеревья 1 и 3; у правого корень 8, левое поддерево пусто, правое - 9.
CL-USER> я просто не знаю что это такое
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
_sg _sg вне форума
Member
 
Аватар для _sg
 
Сообщений: 525
Сказал(а) спасибо: 5
Поблагодарили 42 раз(а) в 38 сообщениях
Регистрация: 23.01.2007
По умолчанию 11.05.2007, 13:30

Цитата:
CL-USER> я просто не знаю что это такое
CL-USER> это prompt (подсказка, сообщение о готовности), может быть иным, зависит от реализации лиспа

A character or message provided by the computer to indicate that it is ready to accept keyboard input. Usually an on-screen question or instruction that tells the user which data to enter or what action to take; for example, "Enter name:".

http://www.visionsofadonai.com/onrampglossary4.html

P.S. указывает и на имя пакета: cl-user
Ответить с цитированием
  (#7 (permalink)) Старый
4x10 4x10 вне форума
Member
 
Сообщений: 23
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 07.05.2007
По умолчанию 11.05.2007, 13:51

Цитата:
CL-USER> это prompt (подсказка, сообщение о готовности), может быть иным, зависит от реализации лиспа

A character or message provided by the computer to indicate that it is ready to accept keyboard input. Usually an on-screen question or instruction that tells the user which data to enter or what action to take; for example, "Enter name:".

http://www.visionsofadonai.com/onrampglossary4.html

P.S. указывает и на имя пакета: cl-user
Спасибо, а по поводу прохода вы использовали прямой проход по бинарному дереву, так как сначала обрабатывается корневая вершина, потом левую и потом правую вершины.
Ответить с цитированием
  (#8 (permalink)) Старый
ваня1205 ваня1205 вне форума
Member
 
Сообщений: 13
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 13.05.2011
По умолчанию 22.05.2011, 12:14

што такое упорядоченное бинарное дерево? (теория и практика) помогите плиссс, у меня зачет
Ответить с цитированием
  (#9 (permalink)) Старый
korvin korvin вне форума
Member
 
Аватар для korvin
 
Сообщений: 337
Сказал(а) спасибо: 1
Поблагодарили 15 раз(а) в 15 сообщениях
Регистрация: 25.01.2010
По умолчанию 23.05.2011, 08:56

Binary search tree - Wikipedia, the free encyclopedia
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Как переделать написанную программу v.k.l.chr.by Вопросы начинающих программистов 1 17.06.2011 14:03
Как запустить написанную программу Leks100 Visual C++ 2 15.06.2011 22:34
Как исправить написанную программу equilibrion C++ Builder 2 04.06.2011 23:04
Транслировать написанную программу в С++ Banned_by_IP Вопросы начинающих программистов 1 27.04.2007 23:49
Как настроить написанную программу diikar С/С++ 7 02.06.2006 16:19
Как написанную программу передать на С++ tommybolin Assembler 5 11.05.2006 23:13
Загрузка .h .cpp в написанную программу toshkaexe Visual C++ 8 24.04.2006 17:44
Как переделать программу написанную на VP5.2 в VP6.1 allig Prolog 7 19.03.2006 00:33
Как оптимизировать написанную программу вручную progzz Вопросы начинающих программистов 25 16.11.2005 04:28
Оцените написанную программу Алексеев Николай Зацените! 10 11.08.2004 21:34
Требуется оценить написанную программу dollar Perl 1 22.05.2004 19:56
Как запустить написанную программу в Prolog Щасслиффки!!! Prolog 1 05.02.2004 21:52



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов