Лабораторная работа №5. Работа с файлами и алгоритмы сортировки
Постановка задачи
Основная задача.
1. Написать функцию Load для считывания из текстового файла (например, Workers.txt) информации о работниках и заработной плате. В первой строке файла находится количество рабочих дней в месяце. Далее для каждого работника в файле записано по две строки: в первой – фамилия работника, во второй – два числа – количество отработанных дней и месячный оклад. После загрузки файла вывести на экран количество считанных записей.
2. Написать функцию Calc для вычисления зарплаты каждого работника по формуле
с округлением значения до двух десятичных знаков. Функция должна также подсчитать итоговую зарплату.
3. Написать функцию Save для выгрузки в файл ведомости заработной платы в виде следующей таблицы.
+----------------------+---+----------+----------+
| Фамилия |Дни| Оклад | Зарплата |
+----------------------+---+----------+----------+
|Петров | 15| 6300.00| 3937.50|
|Иванов | 24| 5600.00| 5600.00|
| ... |...| ... | ... |
+----------------------+---+----------+----------+
|Итого | 23687.50|
+-------------------------------------+----------+
Ширина колонок: «Фамилия» – 40 символов, «Дни» – 3 символа, «Оклад» и «Зарплата» – по 10 символов. Фамилию необходимо выравнивать по левому краю, цифры – по правому. Зарплату выводить с двумя десятичными знаками.
4. Написать функцию SortByName для сортировки списка работников по алфавиту методом пузырьковой сортировки.
5. В основной программе: загрузить список из файла Workers.dat, рассчитать зарплату, выгрузить ведомость в файл Pay.txt, отсортировать список по алфавиту, выгрузить ведомость в файл ByName.txt.
Дополнительные задачи.
1. Добавить функцию SortByPay для сортировки списка по зарплате. В основной программе отсортировать список еще и по зарплате, выгрузить ведомость в файл ByPay.txt.
2. Добавить в функции сортировки подсчет и вывод на экран количества сравнений. Выполнить программу для трех различных списков с количеством 5, 10 и 15 сотрудников соответственно. Записать для каждого списка максимальное количество сравнений из полученных при сортировке по имени и зарплате. Построить график зависимости количества сравнений от длины списка.
Математическая модель
Формула расчета заработной платы:
.
Для сортировки списка будем применять алгоритм пузырьковой сортировки, который в общем виде записывается так:
1. Повторять:
А. Для всех элементов списка, кроме последнего, повторять:
1. Если текущий элемент больше следующего, то поменять их местами
Б. Конец цикла.
2. Конец цикла при условии, что ни одной замены не произошло.
Описание алгоритма
Алгоритм Load. Вход: имя текстового файла для загрузки списка работников и информации о зарплате.
А. Начать исполнение.
1. Открыть файл для чтения.
2. Считать из файла количество рабочих дней в месяце.
3. Присвоить n значение 0.
4. Пока не конец файла, повторять:
А. Увеличить n на 1.
Б. Считать из файла имя n-го сотрудника.
В. Считать из файла количество отработанных дней и оклад для n‑го сотрудника.
5. Конец цикла.
6. Закрыть файл.
7. Вывести сообщение "Считано записей: ", n.
Б. Закончить исполнение.
Алгоритм Calc.
А. Начать исполнение.
1. Присвоить Total значение 0.
2. Для значений i от 1 до n, повторять:
А. Рассчитать зарплату для n-го сотрудника по формуле с округление до 2-х десятичных знаков.
Б. Добавить зарплату n-го сотрудника к Total.
3. Конец цикла.
Б. Закончить исполнение.
Алгоритм Save. Вход: имя файла для сохранения ведомости.
А. Начать исполнение.
1. Открыть файл для записи.
2. Вывести в файл заголовок таблицы.
3. Для значений i от 1 до n, повторять:
А. Вывести в файл строку таблицы для n-го сотрудника: имя, дни, оклад, зарплату.
4. Конец цикла.
5. Вывести в файл конец таблицы с итоговой зарплатой.
6. Закрыть файл.
Б. Закончить исполнение.
Алгоритм SortByName.
А. Начать исполнение.
1. Присвоить Last значение n.
2. Присвоить Cmp значение 0.
3. Повторять:
А. Присвоить Stop значение "истина".
Б. Уменьшить Last на 1.
В. Для значений i от 1 до Last, повторять:
1. Увеличить Cmp на 1.
2. Если имя i-го сотрудника больше имени (i+1)-го, то:
А. Поменять местами i-й и (i+1)-й элементы списка.
Б. Присвоить Stop значение "ложь".
Г. Конец цикла.
4. Конец цикла при условии, что Stop имеет значение "истина".
5. Вывести на экран "Сравнений при сортировке по имени: ", Cmp.
Б. Закончить исполнение.
Алгоритм Lab5.
А. Начать исполнение.
1. Загрузить список работников из файла "Workers.dat".
2. Рассчитать зарплату.
3. Выгрузить ведомость в файл "Pay.txt".
4. Отсортировать список по алфавиту.
5. Выгрузить ведомость в файл "ByName.txt".
6. Отсортировать список по зарплате.
7. Выгрузить ведомость в файл "ByPay.txt".
Б. Закончить исполнение.
Текст программы
program Lab5;
{$APPTYPE CONSOLE}
uses SysUtils;
type
Worker=record
Name:string;
Days:Integer;
Salary,Pay:Real;
end;
var
Days:Integer;
W:array [0..1000] of Worker;
n:Integer;
Total:Real;
procedure Load(const Name:string);
var
F:Text;
begin
Assign(F,Name);
Reset(F);
Readln(F,Days);
n:=0;
while not Eof(F) do
begin
Inc(n);
Readln(F,W[n].Name);
Readln(F,W[n].Days,W[n].Salary);
end;
Close(F);
Writeln('Считано строк: ',n);
end;
procedure Calc;
var
i:Integer;
begin
Total:=0;
for i:=1 to n do
begin
W[i].Pay:=Round(W[i].Salary*W[i].Days/Days*100)
/100;
Total:=Total+W[i].Pay;
end;
end;
procedure Save(const Name:string);
var
F:Text;
i:Integer;
begin
Assign(F,Name);
Rewrite(F);
Writeln(F,'+-------…-------+---+---…---+---…----+');
Writeln(F,'| Фамилия |Дни| Оклад |Зарплата|');
Writeln(F,'+-------…-------+---+---…---+---…----+');
for i:=1 to n do
Writeln(F,'|',W[i].Name,'':40-Length(W[i].Name),
'|',W[i].Days:3,'|',W[i].Salary:10:2,
'|',W[i].Pay:10:2,'|');
Writeln(F,'+-------…-------+---+---…---+---…----+');
Writeln(F,'|Итого |',
Total:10:2,'|');
Writeln(F,'+-------…-------+---+---…---+---…----+');
Close(F);
end;
procedure SortByName;
var
Stop:Boolean;
Last,Cmp,i:Integer;
Temp:Worker;
begin
Last:=n;
Cmp:=0;
repeat
Stop:=True;
Dec(Last);
for i:=1 to Last do
begin
Inc(Cmp); {Подсчет количества сравнений}
if W[i].Name>W[i+1].Name then
begin
Temp:=W[i];
W[i]:=W[i+1];
W[i+1]:=Temp;
Stop:=False;
end;
end;
until Stop;
Writeln('Сравнений при сортировке по имени: ',Cmp);
end;
procedure SortByPay;
var
Stop:Boolean;
Last,Cmp,i:Integer;
Temp:Worker;
begin
Last:=n;
repeat
Stop:=True;
Dec(Last);
for i:=1 to Last do
begin
Inc(Cmp); {Подсчет количества сравнений}
if W[i].Pay>W[i+1].Pay then
begin
Temp:=W[i];
W[i]:=W[i+1];
W[i+1]:=Temp;
Stop:=False;
end;
end;
until Stop;
Writeln('Сравнений при сортировке по зарплате:',Cmp);
end;
begin
Load('Workers.txt');
Calc;
Save('Pay.txt');
SortByName;
Save('ByName.txt');
SortByPay;
Save('ByPay.txt');
Readln; {Задержка для консольных приложений}
end.
Тест
| Исходный файл со списком работников и информацией о заработной плате Workers.txt: | Петров 15 6300 Иванов 24 5600 Сидоров 19 4350 Николаев 15 4800 Малышев 21 4350 Соколов 12 7800 |
Расчет зарплаты и выгрузка файла «Pay.txt»:
+---------------------------+---+----------+----------+
| Фамилия |Дни| Оклад | Зарплата |
+---------------------------+---+----------+----------+
|Петров | 15| 6300.00| 3937.50|
|Иванов | 24| 5600.00| 5600.00|
|Сидоров | 19| 4350.00| 3443.75|
|Николаев | 15| 4800.00| 3000.00|
|Малышев | 21| 4350.00| 3806.25|
|Соколов | 12| 7800.00| 3900.00|
+---------------------------+---+----------+----------+
|Итого | 23687.50|
+------------------------------------------+----------+
Зарплата рассчитана корректно.
Сортировка списка по алфавиту и выгрузка файла «ByName.txt»:
+---------------------------+---+----------+----------+
| Фамилия |Дни| Оклад | Зарплата |
+---------------------------+---+----------+----------+
|Иванов | 24| 5600.00| 5600.00|
|Малышев | 21| 4350.00| 3806.25|
|Николаев | 15| 4800.00| 3000.00|
|Петров | 15| 6300.00| 3937.50|
|Сидоров | 19| 4350.00| 3443.75|
|Соколов | 12| 7800.00| 3900.00|
+---------------------------+---+----------+----------+
|Итого | 23687.50|
+------------------------------------------+----------+
Сортировка выполнена корректно.
Сортировка списка по зарплате и выгрузка файла «ByPay.txt»:
+---------------------------+---+----------+----------+
| Фамилия |Дни| Оклад | Зарплата |
+---------------------------+---+----------+----------+
|Николаев | 15| 4800.00| 3000.00|
|Сидоров | 19| 4350.00| 3443.75|
|Малышев | 21| 4350.00| 3806.25|
|Соколов | 12| 7800.00| 3900.00|
|Петров | 15| 6300.00| 3937.50|
|Иванов | 24| 5600.00| 5600.00|
+---------------------------+---+----------+----------+
|Итого | 23687.50|
+------------------------------------------+----------+
Сортировка выполнена корректно.
Проверка алгоритма сортировки для списков с различным количеством элементов:
| Количество элементов в списке | Количество сравнений при сортировке по имени | Количество сравнений при сортировке по зарплате | Максимальное количество сравнений |
По графику зависимости количества произведенных при сортировке сравнений от длины списка виден резкий, похожий на квадратичный, характер возрастания количества сравнений, что как раз является характерным для применяемого в работе алгоритма пузырьковой сортировки, имеющего оценку O(n2).