Скачали: 17 раз
Форма отчета о лабораторной работе
1. ТИТУЛЬНЫЙ ЛИСТ. "Лабораторная работа ученика... по теме..."
2. ПОСТАНОВКА ЗАДАЧИ. Описание решаемой задачи на естественном
языке.
3. АЛГОРИТМ (метод решения). Описание применяемого алгоритма
на естественном языке, примерно в стиле, примененном в книге
"Программирование: теоремы и задачи" для объяснения
сортировок.
4. ВНУТРЕННЯЯ СПЕЦИФИКАЦИЯ ПРОГРАММЫ. Описание структуры
программы - ее относительно независимых кусков (процедур,
функций, модулей...) и интерфейса между ними (например, какие
параметры они друг другу передают и каков их содержательный
смысл - в терминах, использованных в п.3). Использованный язык
программирования.
5. КОММЕНТИРОВАННЫЙ ТЕКСТ ПРОГРАММЫ. Пункт может быть
объединен с 4.
6. ВНЕШНЯЯ СПЕЦИФИКАЦИЯ. Требования программы к машине.
Обязательно: ОС, использованная память (можно написать
"работает под ДОС, используя только 640K"), место на диске.
7. РУКОВОДСТВО ПОЛЬЗОВАТЕЛЯ. Как запустить программу, что
отвечать на ее вопросы, как бороться с возникающими
проблемами... Пункт можно объединить с 6.
8. ОПИСАНИЕ ТЕСТОВ. Какие входные данные были использованы,
каковы получены результаты, другие параметры работы (в задаче
сортировки, например - время работы).
9. ОГЛАВЛЕНИЕ. (Для лабораторной работы не обязательно).
Общий критерий таков: любой незнакомый с задачей человек
нормального интеллекта должен, имея ваш отчет и не задавая
дополнительных вопросов, суметь запустить программу и
разобраться, что она делает. Если он программирует на том же
языке, он должен понять, как устроена программа.
1. ЛАБОРАТОРНАЯ РАБОТА ПО ПРОГРАММИРОВАНИЮ УЧЕНИКА 10д КЛАССА ШКОЛЫ N57
АХМАНОВА СЕРГЕЯ ПО ТЕМЕ "СОРТИРОВКИ".
2. ПОСТАНОВКА ЗАДАЧИ.
Дан файл, содержащий числа типа longint, расположенные в произвольном
порядке. Требуется расположить эти числа по возрастанию, используя не более
40 килобайт оперативной памяти и дискового пространства не более чем в два
раза больше исходного файла.
3. АЛГОРИТМ (метод решения).
Сначала исходный файл разбивается на куски по 10000 чисел, каждый кусок
сортируется в памяти и записывается в один из двух временных файлов, причем
так, что количество кусков в этих файлах отличается не более чем на 1(далее -
первоначальная сортировка).
Затем, несколько раз выполняется операция "склеивание"(одно выполнение
операции "склеивание" мы будем незывать "шаг"), т.е два исходных
файла, в которых находились отсортированные куски копируются в два других
файла, при этом из двух кусков, находящихся в разных файлах и имеющих
одинаковые номера создается один отсортированный кусок. Этот кусок
записывается в первый выходной файл если исходные куски имели нечетные номера
и во второй, если исходные куски имели четные номера.
4. ВНУТРЕННЯЯ СПЕЦИФИКАЦИЯ ПРОГРАММЫ.
При написании программы использовалась среда Borland Pascal 7.0 и
встроенный компилятор.
Для ускоренного обмена с диском применялся блоковый ввод-вывод, т.е
информация читается и записывается целыми кластерами. Для осуществления этого
способа ввода-вывода был написан модуль(Files), с помощью которого ввод-вывод
внешне не отличается от обычного.
Схема программы предельно проста: сначала выполняется первоначльная
сортировка(процедура firstsort), затем вызываем склеивание(процедура
ftrans(in1, in2, out1, out2: workfile);), где пары файлов все время меняются и
после каждого запуска процедуры проверяется условие выхода.
Процедура ftrans открывает все файлы, затем выполняет несколько раз
процедуру слива одного куска(onestep) и закрывает файлы.
5. КОММЕНТИРОВАННЫЙ ТЕКСТ ПРОГРАММЫ.
{Модуль Files.
Сдесь переписаны все процедуры и функции необходимые для работы с файлами,
работающие с блоками. Работа с ними осуществляется также как и с
обычными процедурами модуля System.}
unit Files;
interface
const typesize=4;
const bufsize = 2048;
type using=longint;
type buffer = array[1..bufsize] of using;
type pbuffer = ^buffer;
type filemode = (fread, fwrite, closed);
type tfile = record
buf: pbuffer;
mode: filemode;
f: file;
count, leng: integer;
end;
procedure fAssign(var w: tfile; name: string);
procedure fReWrite(var w: tfile);
procedure fReset(var w: tfile);
procedure fPut(var w: tfile; d: using);
procedure fGet(var w: tfile; var d: using);
procedure fClose(var w: tfile);
function fEof(var w: tfile): boolean;
implementation
procedure fAssign(var w: tfile; name: string);
begin
Assign(w.f, name);
w.mode:=closed;
end;
procedure fReWrite(var w: tfile);
begin
if w.mode=closed then
begin
ReWrite(w.f, typesize);
new(w.buf);
w.count:=0;
w.leng:=0;
w.mode:=fwrite;
end;
end;
procedure fReset(var w: tfile);
begin
if w.mode=closed then
begin
Reset(w.f, typesize);
new(w.buf);
BlockRead(w.f, w.buf^, bufsize, w.leng);
w.count:=1;
w.mode:=fread;
end;
end;
procedure fPut(var w: tfile; d: using);
begin
if w.mode=fwrite then
begin
w.count:=w.count+1;
w.buf^[w.count]:=d;
if w.count=bufsize then
begin
BlockWrite(w.f, w.buf^, w.count);
w.count:=0;
end;
end;
end;
procedure fGet(var w: tfile; var d: using);
begin
if (w.mode=fread) then
begin
d:=w.buf^[w.count];
if w.leng=w.count then
begin
BlockRead(w.f, w.buf^, bufsize, w.leng);
w.count:=1;
end else w.count:=w.count+1;
end;
end;
procedure fClose(var w: tfile);
begin
if w.mode=fwrite then BlockWrite(w.f, w.buf^, w.count);
dispose(w.buf);
w.mode:=closed;
Close(w.f);
end;
function fEof(var w: tfile): boolean;
begin
if (w.mode=fread) and (w.leng=0) then fEof:=true
else fEof:=false;
end;
begin
end.
{конец files.pas}
{----------------------------------------------------------------------------}
{Файл sort.pas - сортировка в памяти.}
var k: integer;
function SwapTops(no: integer): integer;
var t: longint;
begin
if (memo^[2*no+1]>memo^[2*no]) then
begin
t:=memo^[no];
memo^[no]:=memo^[2*no+1];
memo^[2*no+1]:=t;
SwapTops:=2*no+1;
end else
begin
t:=memo^[no];
memo^[no]:=memo^[2*no];
memo^[2*no]:=t;
SwapTops:=2*no;
end;
end;
procedure SwapHalf(no: integer);
var t: longint;
begin
if memo^[no]
begin
t:=memo^[no];
memo^[no]:=memo^[2*no];
memo^[2*no]:=t;
end;
end;
function Reg(no: integer): boolean;
begin
if (2*no)>k then Reg:=true else
if (2*no+1)>k then
begin
SwapHalf(no);
Reg:=true;
end else
if (memo^[2*no]<=memo^[no]) and (memo^[2*no+1]<=memo^[no]) then Reg:=true
else Reg:=false;
end;
procedure HalfReg(no: integer);
var next: integer;
begin
next:=no;
while (not Reg(next)) do next:=SwapTops(next);
end;
procedure RegTree;
var i: integer;
begin
for i:=k downto 1 do HalfReg(i);
end;
procedure SwapLeaves(l1, l2: integer);
var t: longint;
begin
t:=memo^[l1];
memo^[l1]:=memo^[l2];
memo^[l2]:=t;
end;
procedure SortMemo(len: integer);
begin
k:=len;
RegTree;
for k:=len-1 downto 1 do
begin
SwapLeaves(1, k+1);
HalfReg(1);
end;
end;
{конец sort.pas}
{----------------------------------------------------------------------------}
{Основная пограмма}
uses Dos, Files{Подключение модуля, осуществляющего ввод-вывод.};
const memlen=10000;{Размер памяти, разрешенной для использования}
type tmemo = array[0 .
Скачали: 17 раз
