Студопедия

КАТЕГОРИИ:

АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Деревья, как динамические структуры данных

⇐ ПредыдущаяСтр 7 из 9Следующая ⇒

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

 

Домашнее задание:

 

1. Изучить организацию двоичного дерева , как динамической структуры данных.

2. Освоить алгоритмы поиска и включения в идеально сбалансированное двоичное дерево и стандартные алгоритмы обхода таких деревьев.

3. Изучить организацию и алгоритмы поиска и включения элемента в сбалансированное АVL-дерево ;стандартные повороты для балансировки АVL-деревьев , алгоритм исключения элемента из АVL-дерева.

4. Изучить организацию недвоичного сильноветвящегося В-дерева и алгоритмы построения с поиском и включением элемента ; реорганизацию В-дерева при расщеплении страниц : алгоритм исключения элемента из В-дерева .

             

 

Порядок выполнения работы

1. Открыть проект Delphi -  Struct.

2. На главной форме (Main Form) установить компонент, управляющий всем проектом – главное меню, и назвать первый пункт «Лаб. раб. №1» . Организовать вертикальную составляющую к этому пункту «Задача 1».

3. Добавить к проекту модуль с формой TreeStruct, которая должна появляться на экране при выборе пункта меню «Задача 1». Убедитесь в том, что ваша управляющая конструкция в проекте работает. 

4. Установить на форму модуля TreeStruct компоненты, обеспечивающие ввод исходных данных, управляющую командную кнопку, и компоненты для вывода результатов на экране – для реализации программного приложения в соответствии с вариантом задания таблицы 1.1. Для отображения организованной вами древовидной структуры используйте визуальный компонент библиотеки VCL - TreeView ,расположенный на странице Win32 указанной библиотеки .

5. В обработчике события onClick командной кнопки на языке Object Pascal написать фрагмент программы для ввода исходных данных, обработки их по алгоритму , соответствующему варианту вашего задания (таблица 1.1) и вывода результатов в соответствующий объект (TreeView) на форму модуля TreeStruct. Отладить программу и продемонстрировать результаты преподавателю.

6. Составить отчет , в котором должно быть: 

a. а) текст задания;

b. б)распечатка текста модуля TreeView;

c. в)отображение формы с результатами работы модуля;

d. г)блок-схема алгоритма работы модуля.

7. Защитить работу преподавателю.

 

 

Таблица 6.1

№ вар. Текст задания
1. а )Организовать и отладить программу для построения и печати идеально сбалансированного двоичного дерева ( Function Tree , Function PrintTree ) . б )Запрограммировать и отладить алгоритм обхода построенного бинарного дерева слева направо (в качестве примера построить и обойти дерево , отображающее заданное арифметическое выражение с бинарными операциями).
2. а )Организовать программно двоичное дерево с помощью процедуры поиска и включения ключа (Search). б )Написать и отладить программу для поэлементного вывода значений узлов построенного дерева обходом дерева слева направо(Inorder). Замечание: при правильной организации бинарного дерева с целочисленными ключами в результате отображения ключей при обходе в порядке Inorder , должна получиться отсортированная в порядке возрастания последовательность ключей.
3. а )Написать и отладить программу, которая позволит построить идеально сбалансированное двоичное дерево (с целочисленными ключами). б )Организовать процедуру удаления элемента из организованного двоичного дерева( Procedure Delete).
4. Организовать и отладить программу для построения и отображения сбалансированного AVL-дерева(высоты в поддеревьях отличаются не более , чем на 1) с помощью алгоритма поиска и включения элемента; учесть необходимость балансировки AVL-дерева с использованием LL, RR, LR, RL-поворотов.
5. Программно организовать построение дерева Фибоначчи(Ф-дерево), как пример AVL-дерева. Замечание: дерево Фибоначчи определяется следующим образом:                1) пустое дерево есть Ф-дерево высотой 0;                2)единственная вершина есть дерево высотой 1;                3)если Th-1 и Th-2 -Ф-деревья с высотами (h-1) и (h-2), то                  Th =(Th-1,x,Th-2)  также Ф-дерево высотой h;                 4)других деревьев Фибоначчи не существует.
6. Программно построить недвоичное сильноветвящееся В-дерево с помощью алгоритма поиска и включения элемента на страницу(Procedure SearchB). В программе учесть, что при переполнении страницы происходит расщепление страницы и ,соответственно реорганизация структуры В-дерева.
7. Написать и отладить программу исключения элемента из недвоичного сильноветвящегося В-дерева(Procedure UnderFlow). В программе учесть возможность реорганизации структуры В-дерева в результате исключения элемента со страницы.

                                                                                                                                  

Контрольные вопросы

 

1. Определение дерева, как динамической структуры данных.

2. Бинарное дерево, описание структуры узла в таком дереве.

3. Правило идеально сбалансированного двоичного дерева.

4. Три стандартных обхода деревьев( примеры).

5. Правило сбалансированности для AVL-дерева.

6. Стандартные повороты, используемые для балансировки AVL-дерева.

7. Что такое сильноветвящееся дерево и каково правило его роста?

8. Что такое порядок В-дерева?

9. Когда происходит расщепление страницы в В-дереве и на что это влияет?

 

 



Лабораторная работа № 7

(4 часа)

 

Алгоритмы метода перебора
с возвратами - (МПВ), "жадные" алгоритмы

Цель работы: Изучение алгоритмов метода поиска с возвратами на примерах реализации шахматных задач и задачи динамического программирования. Освоение "жадных" алгоритмов- точного и приближенного.

 

Домашнее задание:

1 Изучить алгоритм метода поиска с возвратами.

2 Изучить алгоритм нахождения критического пути в задаче динамического программирования.

3 Освоить принципы построения "жадных" алгоритмов.

 

 

Порядок выполнения работы.

 

1. Открыть проект Delphi Structures.

2. Добавить в управляющее главное меню пункт «Лабораторная работа №7», при выборе которого должно появляться окно модуля «Poisk_with_back» (модуль Poisk_with_back» с формой добавить в проект).

3. Установить на форму модуля Poisk_with_back компоненты, обеспечивающие ввод исходных данных, управляющую кнопку (класса TButton или TBitBtn) и компоненты для вывода результатов на экране в соответствии с вариантом задания таблицы №2.1.

4. В обработчике события onClick управляющей кнопки на языке

5. Object Pascal написать фрагмент программы для реализации алгоритма в соответствии с вариантом.

6. Отладить обработчик на тестовых примерах и продемонстрировать работу приложения преподавателю.

7. произвести анализ запрограммированного алгоритма (по количеству сравнений ).

8. Составить отчет и защитить работу преподавателю. В отчете обязательно представить блок-схему алгоритма решения задачи.

 


Таблица 7.1

№ вар. Текст задачи
1. Написать и отладить программу, реализующую решение задачи о "безопасном" размещении к ферзей (к<=8) на шахматной доске. Найти одно решение и отобразить его графически на форме приложения. Для нахождения " безопасного " размещения ферзей использовать метод поиска с возвратами.
2. Написать и отладить программу, реализующую решение задачи о "безопасном" размещении 8 ферзей на шахматной доске. Найти все возможные решения и отобразить первое решение графически на форме приложения. Все найденные решения сохранить в файле. Для нахождения " безопасного " размещения ферзей использовать метод поиска с возвратами.
3. Используя перечень номиналов ассигнаций: Const Nominal: array[0..5] of currency= (5000, 1000, 500, 100, 50, 10); , запрограммировать "жадный" алгоритм формирования выдачи заданной суммы в банкомате. Организовать сервис- диалог с заказчиком суммы и учесть в программе возможность отсутствия ассигнаций того или иного номинала.
4. Используя перечень номиналов ассигнаций и монет: Const Nominal: array[0..10] of currency= (5000, 1000, 500, 100, 50, 10, 5, 1, 0.5, 0.1); , запрограммировать "жадный" алгоритм формирования заданной сдачи кассиром. Общее число купюр и монет в сдаче должно получиться минимальным. Организовать сервис- диалог с кассиром для выяснения обстоятельств наличия номиналов в кассе и учесть в программе возможность отсутствия ассигнаций того или иного номинала.
5. Используя метод "жадных" алгоритмов, реализовать решение задачи "о рюкзаке ограниченного объема" , если заданы величины: V--ограничение объема рюкзака, N-- количество предметов заданного объема q[i] и стоимости c[i]. Программа должна выбрать подмножество предметов, вмещающихся в рюкзак и имеющих наибольшую общую стоимость.
6. Пусть имеется решетка для описания последовательности работ: узлы в решетке пронумерованы формально:     Рис.1   Длительность каждой работы указана возле направленной дуги. Написать и отладить программу нахождения времени окончания строительства, если решетка моделирует график работы и длительность (вес дуг).
7. Написать и отладить программу нахождения критического пути для заданной модели-решетки (Рис.1).

 

Контрольные вопросы

 

1. Суть алгоритма метода поиска с возвратами.(МПВ).

2. Что такое 'тупик' в МПВ и как выйти из тупиковой ситуации в этом алгоритме?

3. Почему стек является непременным аксессуаром в алгоритме МПВ?

4. Сформулируйте задачу динамического программирования.

5. Опишите модель задачи динамического программирования.

6. Дайте понятие критического пути.

7. Что такое топологический порядок выбора узлов?

8. Каков механизм нахождения критического пути, если найдено время окончания работ(строительства)?

 





Лабораторная работа № 8




⇐ Предыдущая123456789Следующая ⇒






Последнее изменение этой страницы: 2018-05-10; просмотров: 250.

stydopedya.ru не претендует на авторское право материалов, которые вылажены, но предоставляет бесплатный доступ к ним. В случае нарушения авторского права или персональных данных напишите сюда...