courses:knowledge_base_and_expert_system:lab4
Differences
This shows you the differences between two versions of the page.
|
courses:knowledge_base_and_expert_system:lab4 [2019/10/02 09:42] andrey.suchkov [Лабораторная работа №4: Рекурсивные структуры данных. Деревья] |
courses:knowledge_base_and_expert_system:lab4 [2022/12/10 09:08] |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | ====== Лабораторная работа №4: Рекурсивные структуры данных (деревья) ====== | ||
| - | ===== Цель работы ===== | ||
| - | ===== Основные теоретические положения ===== | ||
| - | Деревья, также как и списки, являются рекурсивным типом данных. Дерево -- это структура данных, которая может быть разделена на корень дерева, левое и правое поддеревья. Так как левое и правое поддеревья в свою очередь являются деревьями, структура рекурсивна. Кроме того, дерево является еще и составным объектом данных. | ||
| - | Дерево, которое имеет только два поддерева, называется двоичным или бинарным. В том случае, если для каждого корня дерева выполняется условие, при котором значение, находящееся в корне дерева меньше значения, находящегося в корне левого поддерева и больше значения, находящегося в корне правого поддерева, двоичное дерево называется упорядоченным. | ||
| - | |||
| - | В Visual Prolog можно определить дерево следующим образом: | ||
| - | <code prolog> | ||
| - | DOMAINS | ||
| - | treetype=tree(integer, treetype, treetype); empty() | ||
| - | </code> | ||
| - | Такое определение говорит о том, что дерево является составным объектом, состоящим из трех составных частей: корня, принадлежащего домену ''integer'' и двух поддеревьев, принадлежащих домену ''treetype'', так как именно этот домен и описывает структуру данных типа дерево. Так как дерево является составным объектом, его составные части объединяет функтор ''tree''. Кроме того, дерево может находиться в двух состояниях: быть непустым (иметь хотя бы один корень) или пустым (не иметь ни одного корня). Пустое дерево описывается функтором ''empty'' без параметров. Если у функтора нет параметров, пустые скобки можно не указывать и записывать только имя функтора. Имена функторов ''tree'' и ''empty'', домена ''treetype'' выбраны произвольно. | ||
| - | Такое определение позволяет записать следующую структуру данных: | ||
| - | <code prolog> | ||
| - | tree(5, | ||
| - | tree(3, | ||
| - | tree(6, empty, empty), | ||
| - | tree(4, empty, empty)), | ||
| - | tree(10, | ||
| - | tree(2, empty, empty), | ||
| - | tree(8, empty, empty))) | ||
| - | </code> | ||
| - | Одной из наиболее частых операций с деревом является обход узлов дерева и выполнение некоторых действий с ними. Например, вывод значений всех корней дерева. Способ решения этой задачи можно описать следующим образом: | ||
| - | - если дерево пустое, корня в дереве нет, нет и значения корня для вывода, не выполнять никаких действий; | ||
| - | - если дерево непустое, то разделить дерево на корень, левое и правое поддеревья, выполнить вывод значения, находящегося в корне дерева, затем обработать левое и правое поддеревья. | ||
| - | Каждое из условий в описании задачи соответствует предложению в программе Visual Prolog. | ||
| - | <code prolog> | ||
| - | DOMAINS | ||
| - | treetype =tree(integer, treetype, treetype); empty() | ||
| - | |||
| - | PREDICATES | ||
| - | print_tree(treetype) | ||
| - | |||
| - | CLAUSES | ||
| - | % дерево пусто, поэтому никакие действия не выполняются | ||
| - | print_tree(empty): -!. | ||
| - | % дерево непусто, поэтому дерево разбивается на три составные части, | ||
| - | % сначала выводится корень, затем обрабатываются левое и правое | ||
| - | % поддеревья | ||
| - | print_tree(tree(Root, Left, Right)) :- write(Root), nl, | ||
| - | print_tree(Left), | ||
| - | print_tree(Right). | ||
| - | |||
| - | OAL | ||
| - | print_tree(tree(5, | ||
| - | tree(3, | ||
| - | tree(6, empty, empty), | ||
| - | tree(4, empty, empty)), | ||
| - | tree(10, | ||
| - | tree(2, empty, empty), | ||
| - | tree(8, empty, empty)))). | ||
| - | </code> | ||
| - | Следует отметить, что в большинстве случает рекурсия, используемая при работе с деревьями, хвостовой не является, так приходится обрабатывать левое и правое поддеревья, что дает две рекурсивные цели в одном предложении и, соответственно, не выполняется первое правило хвостовой рекурсии - рекурсивный вызов должен быть последней целью в хвостовой части правила вывода. | ||
| - | ===== Постановка задачи ===== | ||
| - | Реализовать на языке Visual Prolog программу, выполняющую заданные операции над деревьями в соответствии с индивидуальным вариантом задания. | ||
| - | ===== Порядок выполнения работы ===== | ||
| - | - Напишите на языке Visual Prolog программу, реализующую заданные операции над списками в соответствии с индивидуальным вариантом задания. | ||
| - | - Произведите отладку программы в системе Visual Prolog для запросов на решение прямой и обратной задачи и задачи на перебор вариантов. | ||
| - | - Постройте трассу программы при выполнении каждого запроса. | ||
| - | ===== Варианты заданий ===== | ||
| - | [[.lab4:lab4_vars]] | ||
| - | ===== Содержание отчёта ===== | ||
| - | * Цель работы. | ||
| - | * Краткое изложение основных теоретических понятий. | ||
| - | * Постановка задачи с кратким описанием порядка выполнения работы. | ||
| - | * Трассы выполнения запросов и объяснение результатов их выполнения. | ||
| - | * Общий вывод по проделанной работе. | ||
| - | * Код программы. | ||
courses/knowledge_base_and_expert_system/lab4.txt · Last modified: 2022/12/10 09:08 (external edit)
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 4.0 International
