- •Часть 1.
- •Оглавление
- •Введение
- •1.Стандартные типы данных
- •1.1.Структура программы
- •1.2.Описание стандартных типов данных
- •Целый тип
- •Вещественный тип
- •Символьный тип
- •Булевский тип
- •Описание используемых стандартных функций.
- •Программы № 15.А
- •Программы № 15.Б
- •Варианты заданий
- •2. Операторы языка.
- •2.1. Составной и пустой операторы.
- •2.2.Условный оператор.
- •2.3.Операторы повторений. Счетный оператор цикла (вариант 1):
- •Счетный оператор цикла (вариант 2):
- •Оператор цикла с предусловием:
- •Оператор цикла с постусловием:
- •2.4.Оператор выбора
- •2.5.Практические задания.
- •Распечатка исходных данных и результатов выполнения программы.
- •Варианты заданий
- •Лабораторная работа № 4. Организация циклов в программе.
- •Цель задания:
- •Образец выполнения задания.
- •3.Численные методы.
- •3.1.Метод итераций
- •3.2.Метод Ньютона
- •3.3. Метод половинного деления.
- •Теорема математического анализа метода половинного деления.
- •Лабораторная работа № 5
- •Описание и блок-схема метода решения: Описание метода итераций:
- •Текст программы.
- •Распечатка результатов работы программы в следующем виде:
- •Лабораторная работа № 5, вариант № 3. Решение нелинейных уравнений методом Ньютона. Постановка задачи для конкретного варианта и исходные данные:
- •Описание и блок-схема метода решения: Описание метода Ньютона:
- •Блок-схема метода Ньютона:
- •Текст программы.
- •Распечатка результатов работы программы в следующем виде:
- •Лабораторная работа № 5, вариант № 3. Решение нелинейных уравнений методом половинного деления. Постановка задачи для конкретного варианта и исходные данные:
- •Описание и блок-схема метода решения: Описание метода половинного деления:
- •Блок-схема метода половинного деления:
- •Текст программы.
- •Распечатка результатов работы программы в следующем виде:
- •Варианты заданий.
- •Случайные числа.
- •Метод Монте-Карло (метод статистических испытаний)
- •Результаты выполнения программы:
- •5. Массивы.
- •5.1. Процедуры и функции.
- •5.2. Одномерные массивы.
- •5.2.1. Описание массивов.
- •5.2.2. Классы задач по обработке массивов.
- •5.2.2.1. Однотипная обработка всех или указанных элементов массивов.
- •5.2.2.2. Задачи, в результате решения которых изменяется структура массива.
- •5.2.2.3. Обработка нескольких массивов одновременно.
- •5.2.2.4. Поисковые задачи для массивов.
- •5.2.2.5. Сортировка массивов.
- •5.2.2.5.1.Сортировка вставкой
- •Результат работы :
- •5.2.2.5.2. Сортировка выбором
- •Результат работы :
- •5.2.2.5.3. Сортировка обменом («пузырьковая сортировка»)
- •Результат работы:
- •5.2.2.5.4. Сортировка фон Неймана (слиянием)
- •Результаты работы:
- •5.2.2.5.5. Шейкер-сортировка
- •Результаты выполнения программы:
- •5.3. Двумерные массивы.
- •5.3.1. Описание двумерных массивов.
- •5.3.2. Сортировка двумерных массивов
- •Результаты работы:
- •Результаты работы:
- •Результаты работы:
- •Результаты работы:
- •Результаты работы:
- •Варианты заданий.
- •6. Обработка строк.
- •Var st1,st2:string[10];
- •6.1. Функции обработки строк.
- •6.2. Процедуры обработки строк.
- •Лабораторная работа № 7.
- •Результаты выполнения программы:
- •Варианты заданий.
- •7. Комбинированные типы. Оператор присоединения
- •7.1. Записи
- •7.2. Оператор присоединения
- •Лабораторная работа № 8. Работа с комбинированными типами данных. Цель задания:
- •Постановка задачи:
- •Содержание отчета:
- •Исходные данные:
- •Текст программы:
- •Результаты выполнения программы:
- •Варианты заданий.
- •8. Множественные типы данных.
- •8.1. Множества.
- •Лабораторная работа № 9.
- •Результаты работы:
- •Методические указания:
- •Варианты заданий.
- •Лабораторная работа № 10. Операции над множествами. Цель задания:
- •Постановка задачи:
- •Содержание отчета:
- •Варианты задания:
- •Текст программы:
- •Результаты программы:
- •Варианты заданий.
- •Часть 2.
- •Оглавление
- •9. Файловые типы данных
- •9.1. Инициализация файла
- •9.2. Файлы и работа с ними
- •Лабораторная работа №11. Работа с внешними файлами
- •Образец выполнения задания. Лабораторная работа №11, вариант № 5. Работа с внешними файлами
- •Анкетные данные на абитуриентов в конце методического пособия.
- •Варианты заданий.
- •9.3. Сортировка файлов.
- •9.3.1. Слияние упорядоченных последовательностей.
- •9.3.2. Сортировка сбалансированным слиянием
- •Результат работы:
- •9.3.3. Сортировка простым слиянием
- •Результат работы:
- •9.3.4. Сортировка естественным слиянием.
- •Результат работы:
- •Результат работы:
- •9.3.5. Сортировка многофазным слиянием.
- •Результат работы:
- •Лабораторная работа №12. Сортировка файлов.
- •Образец выполнения задания.
- •Лабораторная работа №12.
- •Сортировка файлов.
- •Постановка задачи:
- •Анкетные данные на абитуриентов в конце методического пособия. Текст программы:
- •Результат выполнения программы:
- •Варианты заданий.
- •10. Динамическая память.
- •10.1. Указатели.
- •10.2. Списки.
- •Лабораторная работа № 13.
- •Результат работы программы:
- •Варианты задания.
- •Лабораторная работа № 14. Работа со списками. Цель работы:
- •Постановка задачи:
- •Содержание отчета:
- •Вариант задания:
- •Текст программы:
- •Результат работы программы:
- •Результат работы программы:
- •Результат работы программы:
- •Варианты задания.
- •Лабораторная работа № 15.
- •Результат работы программы:
- •Варианты заданий.
- •10.3. Деревья.
- •10.4. Стеки, очереди.
- •Образец выполнения работы.
- •Результат работы программы:
- •Часть II
- •Текст программы t854b:
- •Результат работы программы:
- •Лабораторная работа № 16. Работа со стеками и очередями. Варианты заданий.
- •11. Организация меню с использованием средств среды Turbo Pascal
- •Лабораторная работа №17. Составления меню.
- •Образец выполнения работы.
- •Распечатка результатов работы программы после выполнения пунктов меню 4,5,6 и 8:
- •Варианты заданий.
- •Анкетные данные абитуриентов:
Результат работы:
0 3 86 20 27 67 32 16 37 43 8 47 7 84 6 29 92 37 77 33 70 84 72 31 16 33 47 25 83 28 48 15 87 29 77 98 49 89 83 2 14 1 4 50 2 59 1 77 65 77 71 56 21 68 59 96 64 100 24 68 30 9 77 50 88 51 57 95 68 34 1 71 99 77 75 20 14 91 78 59 86 69 29 9 63 28 88 16 27 54 96 17 16 27 18 58 50 29 16 61 74 Нажмите Enter для продолжения !
0 1 1 2 2 3 6 7 8 9 9 14 14 14 15 16 16 16 16 16 17 18 20 20 21 24 25 27 27 27 28 28 29 29 29 29 30 31 32 33 33 34 37 37 43 47 47 48 49 50 50 50 51 54 56 57 58 59 59 59 61 63 64 65 67 68 68 68 69 70 71 71 72 74 75 77 77 77 77 77 77 78 83 83 84 84 86 86 87 88 88 89 91 92 95 96 96 98 99 100 Нажмите Enter для продолжения ! |
9.3.5. Сортировка многофазным слиянием.
Рассмотренные выше методы сортировки простым и естественным слиянием достаточно просты, однако не эффективны, так как сортировка выполняется за значительное число проходов. Например, при сортировке М записей простым слиянием требуется:
К -проходов.
Естественный путь повышения эффективности сортировки заключается в предварительной внутренней сортировке записей, формирование из них серий возможно большей длинны и распределение этих серий по нескольким файлам. При Р-путевом сбалансированным слияний число проходов
Где R-начальное число серий. Поскольку на каждом проходе обрабатывается N записей, то эффективность всего процесса сортировки будет пропорциональна
Ас учётом внутренней сортировки
Из этой формулы виден второй путь повышения эффективности сортировки, а именно увеличивать число файлов P. Однако при сбалансированном многофазном слиянии одновременно используются лишь чуть больше половины имеющихся файлов, а остальные простаивают. Возникает вопрос, можно ли ещё лучше использовать имеющиеся файлы? Да, это возможно, если распределить начальные серии не поровну между всеми файлами, а более хитрым способом, так чтобы на каждой фазе слияния, кроме самой последней, только один файл оказывался пустым. Такой метод называется многофазным слиянием.
Вернёмся к предыдущему примеру сортировки 1700 записей, предварительно отсортированных в серии по 100 записей. Однако на первом этапе распределим эти серии на 3 файла следующим образом: в файл 1-7 серий, в файл 2-6 серий, в файл 3-4 серии.
Далее будем сливать эти серии в файл 4. В результате в файле 4 мы получим 4 серии длиною 300 записей, в файле 1 останется 3 серии, в файле 2 будет 2 серии, а файл 3 станет пустой. Далее сливаем серии в файл 3 и так далее, пока не получим отсортированный файл, состоящий из одной серии длиною 1700 записей. Процесс сортировки показан на рисунке.
1
F4
Внутренняя сортировка и
распределение
F2 F3 F4 F1
7(100) 6(100) 4(100)
Слияние 1
F1 F2 F3 F4
3(100) 2(100) 4(300)
Слияние 1
F1 F2 F3 F4
1(100) 2(500) 2(300)
Слияние 1
F1 F2 F3 F4
1(900) 1(500) 1(300)
Слияние 1
F1 F2 F3 F4
1(1700)
Рисунок. Сортировка 1700 записей с использованием 4 файлов методом многофазного слияния.
Например, для 4 файлов имели следующую последовательность Фибоначчи 2-го порядка
0 , 0 , 1 , 1 , 2 , 4 , 7 , 13 , 24 , 44 , 81.
Возможные начальные распределения серий показаны в таблице.
Таблица.
Начальное распределение серий для 4 лент.
F1 |
4 |
7 |
13 |
24 |
44 |
F2 |
6 |
11 |
20 |
37 |
68 |
F3 |
7 |
13 |
24 |
44 |
81 |
Количество серий в исходном файле |
17 |
31 |
57 |
105 |
193 |
Из сказанного выше следует, что алгоритм многофазного слияния применим только к таким входным данным, в которых число начальных серий имеет волне определённое значение. А что же делать, если число начальных серий отличается от требуемого? В этом случае поступают следующим образом: вводится соответствующее число фиктивных пустых серий, так, чтобы сумма реальных и фиктивных серий давала нужное значение. Однако возникает сразу следующий вопрос: как распределить фиктивные серии между файлами? Давайте посмотрим, как сливаются реальные и фиктивные серии. Понятно, что выбор фиктивной серии с i-ый файла означает, что i-ый файл не участвует в слиянии; в результате слияние происходит с менее чем N-1 файлами. Слияние фиктивных серий со всех N-1 входных файлов не предполагает никакой действительной операции слияния, а означает просто запись фиктивных серий на входной файл. Из этого можно сделать вывод, что фиктивные серии нужно распределить на N-1 файлов как можно более равномерно, так как мы заинтересованы в слиянии с возможно большего числа файлов. Можно также показать, что фиктивные серии лучше располагать в начале файлов.
Пример программы Сортировка многофазным слиянием:
Программа использует уже готовый файл содержащий не отсортированные данные и не распечатывает отсортированный файл (программа только сортирует файл file0).
program Многофазное слияние;
uses crt;
const n=10;
type item=record
key:integer;
{описания других полей}
end;
filetype=file of item;
var f0,f1,f2,f3,a,b,c,d:filetype;
ser0,ser1,ser2,ser3,kolser,disk0,disk1,disk2,disk3,z,l,all,zero0,zero1,zero2,zero3:integer;
eora,eorb,eorc,per,eor:boolean;
mas:array[1..n]of integer;
data:item;
procedure fibonachi;
procedure fib;
begin
disk0:=disk1+disk2+disk3;
while disk0<kolser do
begin
disk3:=disk2;disk2:=disk1;disk1:=disk0;disk0:=disk1+disk2+disk3;
end;
end;
begin
disk1:=1;disk2:=1;disk3:=1;fib;kolser:=disk0;
disk1:=0;disk2:=0;disk3:=1;fib;disk1:=disk2;disk2:=kolser-(disk1+disk3);
end;
procedure readfile;
begin
l:=0;
while not eof(f0)and not(l=n) do
begin l:=l+1;read(f0,data);mas[l]:=data.key;end;
all:=l;
end;
procedure massort;
var buf,units:integer;
m:boolean;
begin
units:=all;
repeat
m:=true;;
units:=units-1;
for l:=1 to units do
begin
if mas[l]>mas[l+1]
then begin buf:=mas[l];mas[l]:=mas[l+1];mas[l+1]:=buf;m:=false;end;
end;
until m or (units=1);
end;
procedure sort(var x:filetype);
begin
readfile;massort;
for l:=1 to all do begin data.key:=mas[l];write(x,data);end;
end;
procedure sortrun;
begin
reset(f0);rewrite(f1);rewrite(f2);rewrite(f3);
kolser:=1;zero0:=0;zero1:=0;zero2:=0;zero3:=0;ser0:=0;ser1:=0;ser2:=0;ser3:=0;
repeat
fibonachi;
if disk1<>ser1 then begin
if not eof(f0) then sort(f1)
else zero1:=zero1+1;
ser1:=ser1+1;
end;
if disk2<>ser2 then begin
if not eof(f0) then sort(f2)
else zero2:=zero2+1;
ser2:=ser2+1;
end;
if disk3<>ser3 then begin
if not eof(f0) then sort(f3)
else zero3:=zero3+1;
ser3:=ser3+1;
end;
if (not eof(f0))and(kolser=(ser1+ser2+ser3)) then kolser:=kolser+1;
until eof(f0)and(kolser=(ser1+ser2+ser3));
close(f0);close(f1);close(f2);close(f3);
end;
procedure copy(var x,y:filetype);
var buf,buf1:item;
begin
read(x,buf);write(y,buf);
if eof(x) then eor:=true
else begin
{заглядываем вперед}
read(x,buf1);
{возвращаемся на исходную запись}
seek(x,filepos(x)-1);
eor:=buf1.key<buf.key
end;
end;
procedure mergerun(var d,a,b,c:filetype;var serd,sera,serb,serc,zerod,zeroa,zerob,zeroc:integer);
{слияние серий из А и В и С в D}
var bufa,bufb,bufc:item;
zapis:boolean;
begin
repeat
eora:=true;eorb:=true;eorc:=true;
serd:=serd+1;sera:=sera-1;serb:=serb-1;serc:=serc-1;
if zeroa<>0 then begin eora:=false;zeroa:=zeroa-1;end;
if zerob<>0 then begin eorb:=false;zerob:=zerob-1;end;
if zeroc<>0 then begin eorc:=false;zeroc:=zeroc-1;end;
if (not eora)and(not eorb)and(not eorc) then zerod:=zerod+1;
while (eora or eorb or eorc) do
begin
bufa.key:=1999;bufb.key:=1999;bufc.key:=1999;
if eora then begin read(a,bufa);seek(a,filepos(a)-1);end;
if eorb then begin read(b,bufb);seek(b,filepos(b)-1);end;
if eorc then begin read(c,bufc);seek(c,filepos(c)-1);end;
if bufa.key<bufb.key then
if bufa.key<bufc.key then
begin
copy(a,d);
if eor then eora:=false;
end
else
begin
copy(c,d);
if eor then eorc:=false;
end
else
if bufb.key<bufc.key then
begin
copy(b,d);
if eor then eorb:=false;
end
else
begin
copy(c,d);
if eor then eorc:=false;
end;
end;
until (sera=0)or(serb=0)or(serc=0);
end;
procedure merge;
begin
reset(f0);reset(f1);reset(f2);reset(f3);
while (ser0+ser1+ser2+ser3)<>1 do
begin
if (ser0=0) then begin rewrite(f0);mergerun(f0,f1,f2,f3,ser0,ser1,ser2,ser3,zero0,zero1,zero2,zero3);reset(f0);end;
if (ser1=0)and((ser0+ser1+ser2+ser3)<>1) then
begin
rewrite(f1);mergerun(f1,f2,f3,f0,ser1,ser2,ser3,ser0,zero1,zero2,zero3,zero0);reset(f1);
end;
if (ser2=0)and((ser0+ser1+ser2+ser3)<>1) then
begin
rewrite(f2);mergerun(f2,f3,f0,f1,ser2,ser3,ser0,ser1,zero2,zero3,zero0,zero1);reset(f2);
end;
if (ser3=0)and((ser0+ser1+ser2+ser3)<>1) then
begin
rewrite(f3);mergerun(f3,f0,f1,f2,ser3,ser0,ser1,ser2,zero3,zero0,zero1,zero2);reset(f3);
end;
end;
close(f0);close(f1);close(f2);close(f3);
end;
begin
clrscr;
assign(f0,'c:\tp\file0');
assign(f1,'c:\tp\file1');
assign(f2,'c:\tp\file2');
assign(f3,'c:\tp\file3');
sortrun;
merge;
end.