Название документа: Любутов О.Д. Решение олимпиадных задач

Аннотация: Олимпиадные задачи по программированию

Работа с файлами

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

В разных языках программирования принята различная классификация файлов. В паскале это типизированный файл, нетипизированный файл и текстовый файл. В бейсике файлы делятся на файлы прямого доступа (аналог типизированных) и файлы последовательного доступа. Чем же они отличаются друг от друга? Сами файлы – ничем. Отличается способ интерпретации данных.

Любой существующий файл можно открыть или как файл прямого доступа или как последовательного.

Файл последовательного доступа состоит (должен состоять) из строк (нескольких байтов) оканчивающихся специальным признаком (обычно это символы возврата каретки и перевода строки, их ASCIIкоды 13 и 10).

Таким образом, если мы открыли для чтения файл (как файл последовательного доступа) и пытаемся прочитать данные, например, в строковую переменную, то в результате в переменной окажется записана последовательность символов до первого встретившегося признака конца строки. При следующей попытке чтения – будут считаны символы до следующего конца строки. И так далее до конца файла.

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

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

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

Давайте посмотрим, как на практике осуществляется работа с файлами. Начнем с файлов последовательного доступа.

Для работы с файлом его необходимо «открыть», а по окончании работы «закрыть». Для этого в бейсике существуют операторы OPENи CLOSE. Вот их формат:

OPEN <имя файла> FOR <тип доступа> AS #<номер канала>

и

CLOSE #<номер канала>

Где

<имя файла> - это путь и имя файла (если путь не указан, то программа будет искать      файл в папке, откуда запущен проект или откомпилированная программа)

< тип доступа > - одно из зарезервированных слов:

INPUT – существующий файл открывается для чтения. Необходимо, чтобы файл с таким именем существовал.

OUTPUT – создается пустой файл с заданным именем. Если файл с таким именем существовал до этого, то он затирается вновь созданным.

APPEND – существующий файл открывается для дозаписи. То есть все что мы запишем, будет располагаться после уже имеющейся в файле информации.

<номер канала> - просто число, которое в дальнейшем будет использоваться для идентификации       файла.

Между операторами OPENи CLOSEмы можем работать с открытым файлом. Читать из него, писать или дописывать в него. Вот как это реализуется. Допусти мы хотим создать файл proba.txt в корне на диске C. И записать в него первое двустишие стихотворения Некрасова и числа от 1 до 10.

DIM S as string, I as integer

OPEN “C:\proba.txt” FOR OUTPUT AS #1

      S=”Однажды, в студеную зимнюю пору”

PRINT #1,S

      PRINT #1,”Я из лесу “;

      PRINT #1,”вышел, был сильный мороз“

      FOR I=1 TO 10

            IF I<7 THEN PRINT #1,I; ELSE PRINT #1,I

NEXT I

CLOSE #1

Обратите внимание! Запись в файл осуществляется так же, как и вывод на экран, только перед выводимой информацией ставится знак # и номер канала.  Разделители «;» и «,» работают так же как и при выводе на экран. То есть в файле текст будет выглядеть так:

Однажды, в студеную зимнюю пору

Я из лесу вышел, был сильный мороз

 1 2 3 4 5 6 7

 8

 9

 10

И вообще вывод в файл (оператором PRINT #) полностью соответствует выводу на экран (оператором PRINT), только экран не имеет ограничений по ширине.

Для чтения из файла используются два оператора:

INPUT # и LINE INPUT #

Разница между ними заключается в том, что INPUT # считывает входные данные до первого разделителя (пробела для чисел и запятой для текста), а LINEI NPUT # используется для считывания строки целиком, игнорируя пробелы и другие разделители до конца строки (аналог текстового файла в паскале). Поэтому если мы хотим считать из файла несколько числовых значений, разделенных пробелами, то мы будем использовать INPUT #. А если мы захотим прочитать всю строку целиком (как текст), то будем использовать LINE INPUT #

Допустим в файле у нас записано:

Proba1 proba2, proba3 proba4

1 2 3 4

Попробуем прочитать данные из файла:

DIM S as string, I as integer, K as integer

OPEN “C:\proba.txt” FOR INPUT AS #1

INPUT #1,S

MsgBox S

INPUT #1,S

MsgBox S

FOR I=1 TO 4

      INPUT #1,K

      MsgBox K

NEXT I     

CLOSE #1

На экране появится сначала Proba1 proba2, затем proba3 proba4, затем по очереди числа от 1 до 4.

Еще следует упомянуть функцию определения конца файла. Необходима, когда мы не знаем, сколько данных расположено в файле. Функция EOF(<номер канала>) возвращает логическое значение «True», если достигнут конец файла. Например, нам нужно вывести на экран все содержимое текстового файла:

DIM S as string

OPEN “C:\proba.txt” FOR INPUT AS #1

DO WHILE NOT EOF(1)

LINE INPUT #1,S

MsgBox S

LOOP

CLOSE #1

Про файлы последовательного доступа, пожалуй, все.

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

Реализуется это следующим образом:

На БЕЙСИКЕ:

            Open "C:\proba.txt" For Random As #1 Len = 2

В данной строке открывается файл прямого доступа (об этом говорит служебное слово Len), на диске C, с именем  proba.txt, по первому каналу и длиной записи равной двум байтам. Если файл proba.txt существует на диске С, то операции чтения или записи будут производится с ним, в противном случае будет создан файл с таким именем.

Чтение и запись осуществляется специальными операторами:

            GET #1,<переменная хранящая номер записи>,<переменная – приемник данных>

            PUT #1,< переменная хранящая номер записи>,<переменная – источник данных>

Номер записи в бейсике начинается с единицы.

И завершается работа с файлом оператором CLOSE #1

На Паскале:

Прежде всего необходимо объявить файловую переменную, размер которой будет определять размер записи.

var

  FileVar: file of тип;

Например:

var F: File of byte;

                 a:byte;

                 i:integer;

Для перемещения по записям в паскале используется процедура seek(<файловая переменная>,< переменная хранящая номер записи >). В паскале записи начинаются с нулевой записи.

Все остальное происходит так же как с текстовыми файлами.

Нужно связать файловую переменную с конкретным файлом:

Assign(F, 'С:\proba.txt');

Затем открыть файл:

            Reset(F);

Теперь можно прочитать из файла 20 символов, начиная с 25-го символа и вывести их на экран:

for i:=25 to 44 do

    begin

      seek(F,i);

      read(F,a);

      write(chr(a));

    end;

И не забудем закрыть файл:

  Close(F);

А теперь попробуем рассмотреть олимпиадную задачу, где был задан файл с 999999 чисел, не превосходящих по модулю 1000000000 (по 4 байта на число). Требовалось найти медиану этого числового массива. Медианой массива называется число, расположенное в середине упорядоченного массива. В нашем случае медианой будет значение 500000 элемента в упорядоченном массиве.

Так как задача реализовывалась на DOS-овских языках программирования (BP7.0 QB и т.д.), где объем памяти ограничен 64Кб (если не использовать динамическую память), то понятно, что разместить весь файл в оперативной памяти (4Мб) не представляется возможным. Можно придумать много разных способов решения данной задачи, и в зависимости от производительности компьютера они либо уложатся в ограничение по времени выполнения (30 секунд), либо нет. Но наиболее оптимальным способом решения данной задачи будет работа с данными непосредственно в файле.

Для нахождения медианы массива нам совершенно не обязательно отсортировывать массив. Попробуем найти «посадочное место» (индекс элемента в отсортированном массиве) первого элемента. Для этого будем сравнивать наш элемент поочередно с каждым элементом массива, начиная с последнего. Если наш элемент не больше последнего, то сравниваем его с предпоследним. Если не больше предпоследнего, то сравниваем с предпредпоследним, и так далее, до тех пор, пока не найдется элемент, который будет меньше нашего. Тогда мы меняем местами наш элемент и тот, который меньше. А затем, начинаем сравнивать наш элемент со следующим, стоящим за тем, который мы обменяли с нашим. Чтобы было понятнее, давайте рассмотрим на числах:

Мы хотим найти «посадочное место» первого элемента нашего массива

↑                                                                                            ↑

Сравниваем его с последним, и так как он не больше его (4<8), то дальше будем сравнивать наш элемент с предпоследним:

↑                                                                                 ↑

Здесь мы видим, что 4>3, поэтому мы меняем местами эти элементы и сравниваем наш элемент со следующим (с семеркой):

↑                                                                     ↑

Так как наш элемент меньше семерки (порядок сортировки по возрастанию не выполняется), то мы снова меняем его местами:

↑                                                         ↑

Здесь порядок сортировки нас устраивает (4<6), поэтому сравниваем наш элемент с предыдущим:

↑                                             ↑

То же самое:

↑                                 ↑

Здесь порядок сортировки нарушен (4>2), поэтому меняем:

↑                     ↑

Порядок сортировки нарушен (9>4), опять меняем:

↑          ↑

Опять нарушен порядок сортировки (4>1). Меняем:

↑↑

Мы видим, что обе стрелочки (указатели) сошлись на одном элементе. Это означает, что мы нашли «посадочное место для нашего элемента (четверки). Обратите внимание! Массив не отсортирован. Но все элементы меньше четверки находятся от нее слева и все элементы больше четверки находятся от нее справа. Это значит, что в отсортированном массиве наш элемент будет стоять именно на этом месте.

Но это же не медиана массива! – скажете вы. Да. Это еще не медиана. Но знание «посадочного места» этого элемента поможет нахождению медианы.

Итак, мы нашли «посадочное место» нашего элемента. Если оно (случайно) оказалось в середине массива – значит наш элемент и есть медиана. А если нет, тогда мы смотрим, левее или правее середины массива оказалось «посадочное место». Если левее, то медиана будет в правой части массива, для которой мы повторим наш алгоритм нахождения «посадочного места», ну а если правее, то для левой части массива.

Данный алгоритм используется в быстрой сортировке Хора. Только здесь нет рекурсии, поскольку мы каждый раз отбрасываем ненужную часть массива.

Вот приблизительный текст программы на языке паскаль:

var F: File of longint; {файловая переменная}

    bg,ed,i:longint;    {bg и ed – начальная и конечная границы интервала}

    x,y,a,b:longint;    {x,y – номера записей, а a,b-значения этих записей }

begin

  Reset(F);

    bg:=0;

    ed:=999999;

    repeat

      x:=bg;

      y:=ed;

      repeat

        seek(F,x);

        read(F,a);

        repeat

          y:=y-1;

          seek(F,y);

          read(F,b);

        until ((a>b) or (x>=y));

        if (x>=y) then break;

        seek(F,x);

        write(F,b);

        seek(F,y);

        write(F,a);

        repeat

          x:=x+1;

          seek(F,x);

          read(F,b);

        until ((a<b) or (x>=y));

        if (x>=y) then break;

        seek(F,x);

        write(F,a);

        seek(F,y);

        write(F,b);

      until(x>=y);

      if (x=499999) then break;

      if (x<499999) then bg:=x+1 else ed:=x;

    until (bg>=ed);

    writeln('mediana=',a);

  Close(F);

end.

В заключении хочется сказать, что на сегодняшний день данная задача представляет лишь теоретический интерес, как пример владения техническими приемами работы с файлами прямого доступа. Реализация программ на объектно-ориентированных языках позволяет весь массив хранить в памяти и получать результат не за 30 секунд, а менее чем за одну секунду. Но алгоритм нахождения медианы полезно знать в любом случае.