Министерство образования Республики Беларусь Учреждение образования

«Белорусский государственный университет информатики и радиоэлектроники»

Кафедра вычислительных методов и программирования

А. К. Синицын, А. А. Навроцкий

ОСНОВЫ АЛГОРИТМИЗАЦИИ

И ПРОГРАММИРОВАНИЯ В СРЕДЕ DELPHI. АЛГОРИТМЫ НА СТРУКТУРАХ ДАННЫХ

Лабораторный практикум по курсу «Основы алгоритмизации и программирования»

для студентов 1 – 2-го курсов всех специальностей БГУИР

Минск 2007

УДК 681.3.06 (075.8) ББК 32.973-018 я73

C 38

Рецензент: Минченко Л. И., докт. ф. м. наук, зав. каф. информатики БГУИР

Синицын, А. К.

C35 Основы алгоритмизации и программирование в среде DELPHI. Алгоритмы на структурах данных: лаб. практикум по курсу «Основы алгоритмизации и программирования» для студ. 1 – 2-го курсов всех спец. БГУИР / А. К. Синицын, А. А. Навроцкий. – Минск: БГУИР, 2007.

– 52 с. : ил.

ISBN 985-444-___-_

В лабораторном практикуме приведены краткие теоретические сведения об основных алгоритмах программирования на языке Object Pascal в среде DELPHI. После каждой темы дан набор индивидуальных заданий.

УДК 681.3.06 (075.8) ББК 32.973-018 я 73

© Синицын А. К., Навроцкий А.А., 2007

ISBN 985-444-___-_ © УО «Белорусский государственный университет информатики и радиоэлектроники», 2007

2

СОДЕРЖАНИЕ
СОДЕРЖАНИЕ.....................................................................................................	3
ТЕМА 1. ПРОГРАММИРОВАНИЕ
С ИСПОЛЬЗОВАНИЕМ РЕКУРСИИ................................................................	5
1.1. Понятие рекурсии......................................................................................	5
1.2. Порядок выполнения работы...................................................................	5
1.2.1. Пример решения задачи.....................................................................	6
1.3. Варианты задач..........................................................................................	7
ТЕМА 2. ПРОГРАММИРОВАНИЕ ПЕРЕБОРА ВАРИАНТОВ
С ИСПОЛЬЗОВАНИЕМ ДЕРЕВЬЕВ РЕШЕНИЙ............................................	9
2.1. Задача оптимального выбора и дерево решений ...................................	9
2.2. Рекурсивная процедура метода ветвей и границ...................................	9
2.3. Эвристические методы ...........................................................................	10
2.3.1. Метод максимальной стоимости ....................................................	10
2.3.2. Метод наименьшего веса.................................................................	10
2.3.3. Метод сбалансированной стоимости .............................................	10
2.3.4. Метод случайного поиска................................................................	11
2.4 Порядок выполнения работы..................................................................	11
2.4.1 Пример решения задачи....................................................................	11
2.5. Варианты задач........................................................................................	14
ТЕМА 3. ПОИСК И СОРТИРОВКА МАССИВОВ........................................	15
3.1. Организация работы с базами данных..................................................	15
3.2. Поиск в массиве записей ........................................................................	15
3.2.1. Линейный поиск...............................................................................	15
3.2.2. Поиск делением пополам ................................................................	16
3.3. Сортировка массивов..............................................................................	16
3.4. Порядок выполнения работы.................................................................	17
3.4.1. Пример фрагмента программы.......................................................	17
3.5. Индивидуальные задания.......................................................................	19
ТЕМА 4. РАБОТА СО СПИСКАМИ НА ОСНОВЕ
ДИНАМИЧЕСКИХ МАССИВОВ....................................................................	21
4.1. Работа со списками .................................................................................	21
4.2. Порядок выполнения работы.................................................................	21
4.3. Индивидуальные задания.......................................................................	22
ТЕМА 5. ОРГАНИЗАЦИЯ ОДНОНАПРАВЛЕННОГО
СПИСКА НА ОСНОВЕ РЕКУРСИВНЫХ ТИПОВ ДАННЫХ
В ВИДЕ СТЕКА..................................................................................................	23
5.1. Основные понятия и определения.........................................................	23
5.2. Порядок выполнения работы.................................................................	23
	3

5.3. Индивидуальные задания........................................................................	24
ТЕМА 6. ОРГАНИЗАЦИЯ ОДНОНАПРАВЛЕННОГО.................................	27
И ДВУНАПРАВЛЕННОГО СПИСКОВ В ВИДЕ ОЧЕРЕДИ........................	27
НА ОСНОВЕ РЕКУРСИВНЫХ ДАННЫХ......................................................	27
6.1. Основные понятия и определения..........................................................	27
6.2 Порядок выполнения работы...................................................................	27
6.3. Индивидуальные задания........................................................................	28
ТЕМА 7. ИСПОЛЬЗОВАНИЕ СТЕКА ДЛЯ ПРОГРАММИРОВАНИЯ
АЛГОРИТМА ВЫЧИСЛЕНИЯ АЛГЕБРАИЧЕСКИХ ВЫРАЖЕНИЙ........	30
7.1. Задача вычисления арифметических выражений.................................	30
7.2. Порядок написания программы..............................................................	30
7.3. Индивидуальные задания........................................................................	33
ТЕМА 8. ПРОГРАММИРОВАНИЕ С ИСПОЛЬЗОВАНИЕМ ДЕРЕВЬЕВ
НА ОСНОВЕ РЕКУРСИВНЫХ ТИПОВ ДАННЫХ.......................................	34
8.1. Понятие древовидной структуры...........................................................	34
8.2. Компонент TTreeView .............................................................................	34
8.3. Бинарное дерево поиска..........................................................................	35
8.4. Порядок написания программы..............................................................	35
8.5. Индивидуальные задания........................................................................	40
ТЕМА 9. ПРОГРАММИРОВАНИЕ С ИСПОЛЬЗОВАНИЕМ
ХЕШИРОВАНИЯ................................................................................................	41
9.1. Понятие хеширования .............................................................................	41
9.2. Порядок написания программы..............................................................	42
9.2.1 Фрагмент программы.........................................................................	42
9.3. Индивидуальные задания........................................................................	43
ТЕМА 10. РАБОТА С РАЗРЕЖЕННЫМИ МАТРИЦАМИ...........................	45
10.1. Где применяются разреженные матрицы............................................	45
10.2. Порядок написания программы............................................................	45
10.2.1. Пример оформления класса со стандартным минимальным
набором методов................................................................................................	45
10.3. Индивидуальные задания......................................................................	50
ЛИТЕРАТУРА.....................................................................................................	51

4