- •А. К. Синицын, а. А. Навроцкий
- •Содержание
- •1.2. Порядок выполнения работы
- •1.2.1. Пример решения задачи
- •Interface
- •Implementation
- •1.3 Варианты задач
- •Тема 2. Программирование перебора вариантов с использованием деревьев решений
- •2.1. Задача оптимального выбора и дерево решений
- •2.2. Рекурсивная процедура метода ветвей и границ
- •2.3 Эвристические методы
- •2.3.1 Метод максимальной стоимости
- •2.5. Варианты задач
- •Тема 3. Поиск и сортировка массивов
- •3.1 Организация работы с базами данных
- •3.2 Поиск в массиве записей
- •3.2.1 Линейный поиск
- •3.2.2 Поиск делением пополам
- •3.3. Сортировка массивов
- •3.4 Порядок выполнения работы
- •3.4.1 Пример фрагмента программы
- •Interface
- •Implementation
- •3.5. Индивидуальные задания
- •Тема 4. Работа со списками на основе динамических массивов
- •4.1. Работа со списками
- •4.2 Порядок выполнения работы
- •Interface
- •Implementation
- •4.3. Индивидуальные задания
- •Тема 5 организация однонаправленного списка на основе рекурсивных типов данных в виде стека
- •5.1. Основные понятия и определения
- •5.2 Порядок выполнения работы
- •Interface
- •Implementation
- •5.3 Индивидуальные задания
- •Тема 6. Организация однонаправленного и двунаправленного списков в виде очереди на основе рекурсивных данных
- •6.1. Основные понятия и определения
- •6.2 Порядок выполнения работы
- •Interface
- •Implementation
- •6.3 Индивидуальные задания
- •Тема 7. Использование стека для программирования алгоритма вычисления алгебраических выражений
- •7.1. Задача вычисления арифметических выражений
- •7.2. Порядок написания программы
- •Interface
- •Implementation
- •7.3. Индивидуальные задания
- •Тема 8. Программирование с использованием деревьев на основе рекурсивных типов данных
- •8.1. Понятие древовидной структуры
- •8.2. КомпонентTTreeView
- •8.3. Бинарное дерево поиска
- •8.4. Порядок написания программы
- •Interface
- •Implementation
- •8.5. Индивидуальные задания
- •Тема 9. Программирование с использованием хеширования
- •9.1. Понятие хеширования
- •9.2. Порядок написания программы
- •9.2.1 Фрагмент программы
- •Interface
- •Implementation
- •9.3. Индивидуальные задания
- •Тема 10 Работа с разреженными матрицами
- •10.1. Где применяются разреженные матрицы
- •10.2. Порядок написания программы
- •10.2.1 Пример оформления класса со стандартным минимальным набором методов
- •Interface
- •Implementation
- •10.3. Индивидуальные задания
- •Литература
- •Основы алгоритмизации и программирования в среде delphi. Алгоритмы на структурах данных
- •220013, Минск, п. Бровки, 6
3.4.1 Пример фрагмента программы
Листинг 3.1
UnitUZapSort;
Interface
const Mr=1000; // Максимальная размерность массива
Type
…
Tzp=Record
zp:TInf; // Поле информации
k:Tk;// Поле ключа
end;
Mas=array[1..Mr] of Tzp; // Тип - массив записей
TZad3=class(TObject)
a : mas;
n:Word; // Текущий размер массива Mr
Procedure ReadFromFile;
Procedure WriteTofile;
Procedure WriteToMemo;
Procedure PoiskL;
Procedure PoiskD;
Procedure SortSlip;
ProcedureRemov;
ProcedureQuickSort;
… < Поля и методы которые надо дописать >
End;
Implementation
ProcedureTzad3.QuickSort;
… < Описание других методов >
constM=12;
Var i,j,L,R : Word; x : Tk; w : Tzp;
S : 0..M;
Stak :array[1..M] of Record L,R:word end;
begin
s:=1; stak[1].L:=1; stak[1].R:=n;
Repeat // Выбор из Stak последнего запроса
L:=stak[s].L; R:=stak[s].R; s:=s-1;
Repeat // Разделение a[L] … a[R]
i:=L; j:=R; x:=a[(L+R) div 2].k;
Repeat
While a[i].k<x do i:=i+1;
While x<a[j].k do j:=j-1;
if i<=j then begin
w:=a[i]; a[i]:=a[j]; a[j]:=w;
i:=i+1; j:=j-1 end;
until i>j;
ifj-L<R-i then begin // Какая половина длиннее?
ifi<r then // Запись запроса из правой части
begin s:=s+1; stak[s].L:=i; stak[s].R:=R; end;
R:=j;
end // Теперь L и R ограничивают левую часть
elsebegin
if L<j then // Запись запроса из левой части
begin s:=s+1;stak[s].L:=L;stak[s].R:=j end;
L:=i end;
until L>=R; // Конец разделения очередной части
until s=0; // Stak пуст
end; // Конец метода QuickSort
End.
Листинг 3.2
Unit Unit1;
…
Uses UZapSort;
Var zad3:Tzad3;
…
begin
zad3:=Tzad3.create;
zad3.ReadFromFile; // При чтении определяется n
zad3.QuickSort;
zad3.WriteTofile;
< Вывод сортированного массива >
zad3.free;
end.
3.5. Индивидуальные задания
1. В магазине формируется список лиц, записавшихся на покупку товара. Каждая запись этого списка содержит: порядковый номер, Ф.И.О., домашний адрес покупателя и дату постановки на учет. Ключ: дата постановки на учет.
Удалить из списка все повторные записи, проверяя Ф.И.О.
2. Список товаров, имеющихся на складе, включает в себя наименование товара, количество единиц товара, цену единицы и дату поступления товара на склад. Ключ: наименование товара.
Вывести в алфавитном порядке список товаров, хранящихся больше месяца, стоимость которых превышает 1000000 р.
3. Для получения места в общежитии формируется список студентов, который включает Ф.И.О. студента, группу, средний балл, доход на члена семьи. Ключ: доход на члена семьи.
Общежитие в первую очередь предоставляется тем, у кого доход на члена семьи меньше двух минимальных зарплат, затем остальным в порядке уменьшения среднего балла. Вывести список очередности.
4. В справочной автовокзала хранится расписание движения автобусов. Для каждого рейса указаны его номер, тип автобуса, пункт назначения, время отправления и прибытия. Ключ: время отправления.
Вывести информацию о рейсах, которыми можно воспользоваться для прибытия в пункт назначения раньше заданного времени.
5. На междугородной АТС информация о разговорах содержит дату разговора, код и название города, время разговора, тариф, номер телефона в этом городе и номер телефона абонента. Ключ: время разговоров.
Вывести по каждому городу общее время разговоров с ним и сумму.
6. Информация о сотрудниках фирмы включает: Ф.И.О., табельный номер, количество проработанных часов за месяц, почасовой тариф. Ключ: размер заработной платы.
Рабочее время свыше 144 ч считается сверхурочным и оплачивается в двойном размере. Вывести размер заработной платы каждого сотрудника фирмы за вычетом подоходного налога, который составляет 12% от суммы заработка.
7. Информация об участниках спортивных соревнований содержит: наименование страны, название команды, Ф.И.О. игрока, игровой номер, возраст, рост, вес. Ключ: возраст.
Вывести информацию о самой молодой команде.
8. Для книг, хранящихся в библиотеке, задаются: регистрационный номер книги, автор, название, год издания, издательство. Ключ: автор.
Вывести список книг с фамилиями авторов в алфавитном порядке, изданных после заданного года.
9. Различные цеха завода выпускают продукцию нескольких наименований. Сведения о выпущенной продукции включают: наименование, количество, номер цеха. Ключ: количество выпущенных изделий.
Для заданного цеха необходимо вывести количество выпущенных изделий по каждому наименованию в порядке убывания количества.
10. Информация о сотрудниках предприятия содержит: Ф.И.О., номер отдела, должность, дату начала работы. Ключ: дата начала работы.
Вывести списки сотрудников по отделам в порядке убывания стажа.
11. Ведомость абитуриентов, сдавших вступительные экзамены в университет, содержит: Ф.И.О., адрес, оценки. Ключ: Ф.И.О.
Вывести в алфавитном порядке фамилии абитуриентов, проживающих в г.Минске и сдавших экзамены со средним баллом не ниже 4.5,
12. В справочной аэропорта для каждого рейса указаны: номер рейса, тип самолета, пункт назначения, время вылета. Ключ: пункт назначения.
Вывести все номера рейсов, типы самолетов и времена вылета для заданного пункта назначения в порядке возрастания времени вылета.
13. У администратора железнодорожных касс хранится информация о свободных местах в поездах на ближайшую неделю в следующем виде: дата выезда, пункт назначения, время отправления, число свободных мест. Ключ: число свободных мест.
Оргкомитет конференции обращается к администратору с просьбой зарезервировать mмест до городаNнаk-й день недели с временем отправления поезда не позднееt часов вечера. Вывести время отправления или сообщение о невозможности выполнить заказ в полном объеме.
14. Ведомость абитуриентов, сдавших вступительные экзамены в университет, содержит: Ф.И.О. абитуриента, оценки. Ключ: Ф.И.О.
Определить средний балл по университету и вывести список абитуриентов, средний балл которых выше среднего балла по университету. Первыми в списке должны идти студенты, сдавшие все экзамены на 5.
15. В радиоателье хранятся квитанции о сданной в ремонт радиоаппаратуре. Каждая квитанция содержит следующую информацию: наименование группы изделий(телевизор, радиоприемник и т. п.),марку изделия, дату приемки в ремонт, состояние готовности заказа (выполнен, не выполнен). Ключ: дата приемки в ремонт.
Вывести информацию о состоянии заказов на текущие сутки по группам изделий.