XII Международная студенческая научная конференция Студенческий научный форум - 2020

Актуальность и проблема исследования

Многие реальные объекты имеют иерархическую структуру. Для представления таких объектов и обработки связанной с ними информации удобна организация данных, отражающая структуру объектов. Если абстрагироваться от конкретного содержания элементов, то получится математический объект, называемый деревом.

Введение

Деревья – одни из наиболее широко распространенных структур данных в информатике и программировании, которые представляют собой иерархические структуры в виде набора связанных узлов.

Корневой узел — самый верхний узел дерева (А)

Узел — одна из любых вершин дерева (А, B, C, D, E, F, G)

Лист — узел, не имеющий дочерних элементов (D, E, F, G)

Рисунок 1. – Дерево и его основные элементы

Проектирование

Для того чтобы реализовать поставленную задачу, мы должны иметь полное представление того, что хотим получить. Для этого, первым делом, визуализируем необходимое дерево, при помощи моделирования:

Рисунок 2. – Дерево принятия решения “Порода собаки”

Всем узлам данного дерева за исключением листьев присвоено значение и ключ, который необходим для формирования двоичного дерева поиска, то есть такого дерева у которого:

Каждый узел имеет не более двух потомков

Дочерний узел со значение больше родительского соответствует правому поддереву, а со значением меньше – левому

Таким образом, в случае отрицательного ответа на вопрос пользователь будет перемещаться по левому поддереву, иначе по правому.

Постановка задачи

Реализуем тестовое дерево решений (вопросник «да» - «нет) для определения необходимой породы собаки. Для того, чтобы лучше усвоить исследуемую тему, немного усложним реализацию – необходимо выводить:

Цепочку вопрос-ответ, пройденную пользователем

Самый короткий и самый длинный путь от корня до листа

Путь к заданному решению (листу) от корня

Выводить тот вопрос, ответ на который «сбил» правильную цепочку, и пользователь получил решение, которое не ожидал

Решение

Формирование дерева:

происходит статически, дерево принимает два параметра – вопрос и его идентификатор: t.Insert("У собаки короткие уши?", 60);

Формирование вопроса:

основывается кнопках (3.2.1 и 3.2.2), в зависимости от которых в дереве ищется вопрос по нужному идентификатору, после чего найденный вопрос выводится в поле отображения информации (1).

Короткие и длинные пути:

Совершается проход по дереву в процессе которого все возможные пути заносятся в коллекцию List<string> list = new List<string>(), в дальнейшем эта коллекция анализируется по количеству идентификаторов в ней String[] words = list[i].Split(newchar[] {' '}, определяется глобальный минимум или максимум, после чего из листа выводятся все пути, соответствующие требования глобальной длинны list[i].Length == min/max, и по окончанию процесса информация выводится в поле (2).

Поиск пути:

Задается значение поиска в поле (7), после чего осуществляется поиск этого элемента в листьях дерева, в нашем случае – последний элемент list. Если путь не найдется, программа предупредит пользователя об этом.

Место ошибки в вопросе:

Задается значение ожидаемого решения в поле (7), в дальнейшем оно сравнивается со значением поля (1), в котором хранится решение, которое пользователь не ожидал. На основании этих двух значений производится их поиск в листьях дерева – последний элемент list, чтобы определить пути. Далее происходит сопоставления полученный путей по идентификаторам, до тех по пока идентификаторы перестанут совпадать.

received = path.Split(newchar[] { ' ' }); // Полученноерешение

expected = path.Split(newchar[] { ' ' }); // Ожидаемоерешение

while (received[i] == expected[i])

увеличиваем индекс идентификатора;

В итоге в поле (11) выведется ключ вопроса с ошибочным ответом.

Описание интерфейса программы:

Поле вывода для вопросов и конечного решения (3.2.1, 3.2.2);

2) Поле для вывода пути до полученного решения;

3.1) Инициализация первого вопроса и перерисовка формы;

3.2.1) Положительный ответ на вопрос;

3.2.2) Отрицательный ответ на вопрос;

3.3) Пройти опрос сначала;

4) Графическая интерпретация решения;

5) Инициализация короткого пути;

6) Отображение короткого или длинного маршрута (5, 10);

7) Поле для поиска пути к решению и существующих ошибок;

8) Инициализация пути до решения из поля (7);

9) Отображение пути до решения из поля (7);

10) Инициализация длинного пути;

11) Отображение место ошибочного ответа (7);

12) Инициализация вопроса с ошибочным ответом (7);

Заключение

Подводя итоги, хочется отметить преимущества данной разработки:

Деревья двоичного поиска эффективны с точки зрения памяти, так как они не резервируют места больше, чем нужно.

Жестко структурирование данных, что дает преимущество в скорости поиска и удобстве работы с ними.

Но к сожалению, часто программисты просто-напросто не придают должного значения использованию деревьев, используя не самые рациональные способы решения тех или иных задач, что приводит к повышению уровня трудоемкости разработки и понижению производительности программных средств.

Библиографические ссылки

Лясин, Д.Н. Объектно-ориентированный анализ и проектирование программных систем: учеб. пособ.(гриф) . Доп. УМО вузов по университетскому политехническому образованию / Д.Н. Лясин, О.Ф. Абрамова; ВПИ (филиал) ВолгГТУ. - Волгоград, 2015. - 99 с.

Абрамова, О.Ф. К вопросу о визуальном моделировании с использованием BOUML [Электронный ресурс] / О.Ф. Абрамова // NovaInfo.Ru : электрон. журнал. - 2016. - № 45, ч. 2. – Режим доступа : http://novainfo.ru/article/5873.

Лясин, Д.Н. Практикум по алгоритмизации решения задач. Основы программирования на языках Си и Си++ [Электронный ресурс]: учеб. пособие / Д.Н. Лясин, М.В. Фадеева; ВПИ (филиал) ВолгГТУ. - 1 электрон. опт. диск (CD-ROM). - Волжский, 2016. - 110 с.

Гагарина, Л.Г. Алгоритмы и структуры данных / Л.Г. Гагарина. - М.: Финансы и статистика, 2009. - 426 c.

Подбельский, В. В. Язык С#. Базовый курс / В.В. Подбельский. - М.: Финансы и статистика, 2013. - 408 c.

Код для цитирования: Скопировать