Сортировки

Рефераты, курсовые, дипломные, контрольные (предпросмотр)

Тип: Исследование. Файл: Word (.doc) в архиве zip. Категория: Информатика, IT
Адрес этого реферата http://referat-kursovaya.repetitor.info/?essayId=25148 или
Загрузить
В режиме предпросмотра не отображаются таблицы, графики и иллюстрации. Для получения полной версии нажмите кнопку «Загрузить». Рефераты, контрольные, дипломные, курсовые работы предоставляются в ознакомительных целях, не для плагиата.

ПОСТАНОВКА ЗАДАЧИ.

Дан файл, содержащий числа типа longint, расположенные в произвольном порядке. Требуется расположить эти числа по возрастанию, используя не более 40 килобайт оперативной памяти и дискового пространства не более чем в два раза больше исходного файла.

АЛГОРИТМ (метод решения).

Сначала исходный файл разбивается на куски по 10000 чисел, каждый кусок сортируется в памяти и записывается в один из двух временных файлов, причем так, что количество кусков в этих файлах отличается не более чем на 1(далее - первоначальная сортировка).

Затем, несколько раз выполняется операция "склеивание"(одно выполнение операции "склеивание" мы будем незывать "шаг"), т.е два исходных файла, в которых находились отсортированные куски копируются в два других файла, при этом из двух кусков, находящихся в разных файлах и имеющих одинаковые номера создается один отсортированный кусок. Этот кусок записывается в первый выходной файл если исходные куски имели нечетные номера и во второй, если исходные куски имели четные номера.

ВНУТРЕННЯЯ СПЕЦИФИКАЦИЯ ПРОГРАММЫ.

При написании программы использовалась среда Borland Pascal 7.0 и встроенный компилятор.

Для ускоренного обмена с диском применялся блоковый ввод-вывод, т.е информация читается и записывается целыми кластерами. Для осуществления этого способа ввода-вывода был написан модуль(Files), с помощью которого ввод-вывод внешне не отличается от обычного.

Схема программы предельно проста: сначала выполняется первоначльная сортировка(процедура firstsort), затем вызываем склеивание(процедура ftrans(in1, in2, out1, out2: workfile);), где пары файлов все время меняются и после каждого запуска процедуры проверяется условие выхода.

Процедура ftrans открывает все файлы, затем выполняет несколько раз процедуру слива одного куска(onestep) и закрывает файлы.

КОММЕНТИРОВАННЫЙ ТЕКСТ ПРОГРАММЫ.

Модуль Files.

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

ВНЕШНЯЯ СПЕЦИФИКАЦИЯ.

Для корректной работы программы необходим компьютер AT286, 40K свободной conventional памяти, операционная система MS-DOS 3.0 или более поздняя версия. Возможны версии программы, использующие меньше памяти, процессоры слабее 286 и т.д. Программа использует место на диске вдвое большее исходного файла(не считаяя сам файл).

РУКОВОДСТВО ПОЛЬЗОВАТЕЛЯ.

При запуске программы обязательно должна быть определена переменная среды TEMP!

Формат запуска программы:

f_sort[.exe] входной файл выходной файл

Программа не задает ни каких вопросов, что сильно упрощает работу с ней.

Результат работы можно поверить с помощью прилагаемой утилиты f_check, создать случайный исходный файл - с промощью f_make.

Причинами ошибок могут служить не соответствие системы требованиям, изложенным в п. 6, недостаточное место на диске, размер(в байтах) исходного файла не кратен 4.

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

ОПИСАНИЕ ТЕСТОВ.

Программма тестировалась неодноктатно, на входе использовались, в основном, файлы из случайных чисел различной длины. На выходе были получены файлы тойже длины, не содержащие ошибок, т.е. числа в этох файлах оказались в порядке не строгого возрастания. Содержимое этих файлов полностью совпало с разультатами работы других программ сортировки на тех же входных файлах, что сильно снижает вероятность дифектов программы.

При тестировании использовались операционные системы MS-DOS 6.22, Windows`95, компьютеры PC AT 486DX4-100, 486SX-25, работающие с локальным винчестером, робочие станции 486DX-40, 386SX, работающие в сети Novell.

Результаты тестирования(на файле размером 4M) занесены в таблицу: компьютер работа в сети время работы

486DX4-100 нет 3 мин.

486SX-25 нет 7 мин.

486DX-40 да

386SX да

Форма отчета о лабораторной работе

1. ТИТУЛЬНЫЙ ЛИСТ. "Лабораторная работа ученика... по теме..."

2. ПОСТАНОВКА ЗАДАЧИ. Описание решаемой задачи на естественном языке.

3. АЛГОРИТМ (метод решения). Описание применяемого алгоритма на естественном языке, примерно в стиле, примененном в книге "Программирование: теоремы и задачи" для объяснения сортировок.

4. ВНУТРЕННЯЯ СПЕЦИФИКАЦИЯ ПРОГРАММЫ. Описание структуры программы - ее относительно независимых кусков (процедур, функций, модулей...) и интерфейса между ними (например, какие параметры они друг другу передают и каков их содержательный смысл - в терминах, использованных в п.3). Использованный язык программирования.

5. КОММЕНТИРОВАННЫЙ ТЕКСТ ПРОГРАММЫ. Пункт может быть объединен с 4.

6. ВНЕШНЯЯ СПЕЦИФИКАЦИЯ. Требования программы к машине. Обязательно: ОС, использованная память (можно написать "работает под ДОС, используя только 640K"), место на диске.

7. РУКОВОДСТВО ПОЛЬЗОВАТЕЛЯ. Как запустить программу, что отвечать на ее вопросы, как бороться с возникающими проблемами... Пункт можно объединить с 6.

8. ОПИСАНИЕ ТЕСТОВ. Какие входные данные были использованы, каковы получены результаты, другие параметры работы (в задаче сортировки, например - время работы).

9. ОГЛАВЛЕНИЕ. (Для лабораторной работы не обязательно).

Общий критерий таков: любой незнакомый с задачей человек нормального интеллекта должен, имея ваш отчет и не задавая дополнительных вопросов, суметь запустить программу и разобраться, что она делает. Если он программирует на том же языке, он должен понять, как устроена программа.



При любом использовании материалов сайта обязательна гиперссылка на сайт «Репетитор».
Разработка и Дизайн компании Awelan
www.megastock.ru
Проверить аттестат