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

Учреждение образования

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

информатики и радиоэлектроники»

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

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

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

И ПРОГРАММИРОВАНИЯ В СРЕДЕ DELPHI.

АЛГОРИТМЫ НА СТРУКТУРАХ ДАННЫХ

Лабораторный практикум по курсу

«Основы алгоритмизации и программирования»

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

Минск 2007

УДК 681.3.06 (075.8)

ББК 32.973-018 я73

C38

Синицын А. К.

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

Содержание

СОДЕРЖАНИЕ 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

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. Программирование с использованием ХЕШИРОВАНИЯ 42

9.1. Понятие хеширования 42

9.2. Порядок написания программы 43

9.2.1 Фрагмент программы 43

9.3. Индивидуальные задания 44

Тема 10 Работа с разреженными матрицами 46

10.1. Где применяются разреженные матрицы 46

10.2. Порядок написания программы 46

10.2.1 Пример оформления класса со стандартным минимальным набором методов 46

10.3. Индивидуальные задания 51

ТЕМА 1. Программирование с использованием рекурсии

Цель лабораторной работы:изучить способы программирования алгоритмов с использованием рекурсии.

1.1. Понятие рекурсии

рекурсия– это такой способ организации вычислительного процесса, при котором подпрограмма в ходе выполнения составляющих ее операторов обращается сама к себе. Классический пример программирования вычисленияn-го члена (n>0) рекуррентной последовательностиx_n =  (x_n-1)приx₀ = a

Function XR(n:Word):extended;

begin

if n=0 then Result:=a

else Result:=(XR(n-1));

end;

Здесь функция, определяющая закон рекуррентности и определяемая в общем случае как:

FunctionFi(x:extended):extended;

begin Result:=(x+b/x)/2; end;

или явно, например, как

XR:=(XR(n-1)+b/XR(n-1))/2.

Обращение: a:=a0; b:=b0; y:=XR(n0);

При выполнении вышеприведенной рекурсивной подпрограммы осуществляется многократный переход от некоторого текущего уровня организации алгоритма к нижнему уровню последовательно, до тех пор, пока наконец не будет получено тривиальное решение задачи (в вышеприведенном примере n=0).

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

Рекурсивный вызов может быть прямым, как в вышеприведенном примере, и косвенным. В этом случае подпрограмма обращается к себе опосредованно, путем вызова другой подпрограммы, в которой содержится обращение к первой.