Основы программирования Файлы. Рекурсия. Методические указания для студентов 1 курса факультета математики, механики и компьютерных наук

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Федеральное государственное образовательное учреждение высшего профессионального образования «ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»

С.С. Михалкович

Основы программирования Файлы. Рекурсия

МЕТОДИЧЕСКИЕ УКАЗАНИЯ для студентов 1 курса факультета математики, механики и компьютерных наук

Ростов-на-Дону 2007 3

Аннотация Методические указания содержат лекции по темам «Файлы», «Рекурсия» курса «Основы программирования» для студентов направления «Информационные технологии» факультета математики, механики и компьютерных наук Методические указания разработаны кандидатом физико-математических наук, доцентом кафедры алгебры и дискретной математики Михалковичем С.С.

Печатается в соответствии с решением кафедры алгебры и дискретной математики факультета математики, механики и компьютерных наук ЮФУ, протокол № 3 от 13 ноября 2006 г. 4

1 Файлы Файл – это именованная область на диске, предназначенная для хранения информации. Основным достоинством файлов является возможность хранить данные между запусками программы. Кроме того, количество информации в файле может быть значительным, превышая объем оперативной памяти. Файлы подразделяются по двум признакам: по типу элементов и по способу доступа. По типу элементов различают текстовые и двоичные (бинарные) файлы. Текстовые файлы предназначены для хранения текста и состоят из строк разной длины, разделяемых специальными невидимыми символами перехода на новую строку. В операционной системе Windows разделителем строк в текстовых файлах служит пара символов с кодами 13 и 10, идущих подряд. В системах Unix и Linux разделителем строк является символ с кодом 10. Будем называть эти символы маркером конца строки и обозначать EOLN (от англ. End Of Line). Двоичные файлы предназначены для хранения произвольной информации. В языке Паскаль существует две разновидности двоичных файлов – типизированные и бестиповые. Типизированные файлы состоят из элементов одного типа, что позволяет работать с ними как с массивами, обращаясь к элементам по индексу. Бестиповые файлы предназначены для низкоуровневой работы с файлами, и в данной книге рассматриваться не будут. По способу доступа различают файлы с последовательным и произвольным доступом. В файлах с последовательным доступом мы имеем доступ только к текущему элементу. При совершении операции чтения или записи осуществляется переход к следующему элементу. Таким образом, нельзя получить доступ к элементу, не обратившись к предыдущим. Последовательный доступ отражает тот факт, что на диске данные файла хранятся последовательно и при обращении к ним головка жесткого диска обычно считывает или записывает порцию последовательно идущих данных. Заметим, что текстовые файлы имеют только последовательный доступ, поскольку их элементами являются строки, имеющие, вообще говоря, разную длину. В файлах с произвольным доступом данные считаются принадлежащими к одному типу, элементы которого имеют одинаковый размер. Поэтому мы можем обратиться к произвольному элементу по его номеру (как в массиве). Так, двоичные файлы в языке Паскаль имеют произвольный доступ. Перед началом работы с файлом его требуется открыть, а по окончании работы – закрыть. Если по окончании работы программы файл не закрыт, то часть записываемых в него данных может быть потеряна. С каждым открытым файлом связан так называемый файловый указатель – текущая позиция в файле, в которой будут производиться операции чтения/записи. При открытии файла файловый указатель обычно устанавливается на начало файла, а при каждой операции чтения/записи автоматически продвигается вперед на размер считанных/записанных данных. 5

В зависимости от типа файл может быть открыт только на чтение, только на запись или на чтение и запись одновременно. Поскольку текстовые файлы имеют только последовательный доступ, то они могут быть открыты либо только на чтение, либо только на запись. Двоичные же файлы имеют произвольный доступ и поэтому открываются на чтение и запись одновременно. Чтобы осуществлять доступ к файлу на диске, в программе описывается файловая переменная, которая связывается с конкретным файлом с помощью специальной процедуры. Затем файл открывается, и с ним производятся операции чтения/записи. По окончании работы файл следует закрыть. Файловые переменные представляют собой скрытые записи, хранящие различную информацию о файле. Эти переменные запрещено присваивать друг другу и передавать по значению как параметры подпрограмм. Файловая переменная, связанная с текстовым файлом, в языке Паскаль имеет тип text, для типизированного файла – тип file of тип компонент, для бестипового файла – тип file. Перечислим основные подпрограммы для работы с файлами, общие для типизированных и текстовых файлов. C каждой файловой переменной после открытия файла связывается некоторый буфер – область оперативной памяти, в которую данные из файла считываются опережающим образом. Наличие буфера ускоряет операции с файлом. Все операции чтения/записи осуществляются не с самим файлом, а с его буфером. Если мы считываем из буфера и данные в буфере заканчиваются, то осуществляется чтение в буфер следующей порции информации из файла. Если мы производим запись в буфер и он заканчивается или если мы перемещаемся в другое место файла с помощью операции произвольного доступа, то содержимое буфера записывается в файл, после чего в буфер считывается новое содержимое файла. Если файл был открыт на запись, то при закрытии файла содержимое буфера сбрасывается в этот файл. По этой причине если не закрыть файл, то последняя информация, записанная в него и содержащаяся в буфере, может не сохраниться на диске.

2.1 Основные процедуры и функции для работы с файлами Assign(f,name) – процедура, связывающая файловую переменную f с файлом на диске с именем name. Вызывается до открытия файла. Не требует наличия файла на диске. Reset(f) – процедура, открывающая существующий файл и устанавливающая файловый указатель на его начало. Если файла на диске нет, происходит ошибка времени выполнения. Для текстового файла открывает его на чтение. Rewrite(f) – процедура, создающая новый файл с именем, указанным в процедуре Assign, и открывающая его. Если файл уже есть, то он удаляется и создается пустой файл. Если файл по каким-либо причинам нельзя создать (например, имя файла содержит запрещенные символы), происходит ошибка времени выполнения. Для текстового файла открывает его на запись. 6

Close(f) – процедура, закрывающая открытый файл. Для неоткрытого файла ее вызов приводит к ошибке. Eof(f)– функция, возвращающая True, если достигнут конец файла, и False в противном случае. Если достигнут конец файла, то есть файловый указатель стоит непосредственно за последним элементом файла, считается, что файловый указатель стоит на специальном элементе EOF (Eof – end of file), называемом маркером конца файла. Для чтения/записи в текстовых и типизированных файлах используются стандартные процедуры Read и Write, при вызове которых в качестве первого параметра передается файловая переменная. Read(f,x1,x2,x3) – считывает данные из файла f в переменные x1, x2, x3. Для типизированных файлов тип переменных должен совпадать с типом элементов файла, для текстовых – переменные x1, x2, x3 могут иметь те же типы, что и в процедуре Read для ввода данных с клавиатуры (т.е. символьный, строковый или числовой). При этом данные, считываемые из текстового файла, должны храниться в том же виде, как при вводе с клавиатуры; в частности, при считывании числовых данных пропускаются лидирующие пробелы. Данные же, считываемые из типизированного файла, должны храниться в том же формате, в каком хранятся значения соответствующих типов в оперативной памяти. Write(f,x1,x2,x3) – записывает данные в файл f из переменных x1, x2, x3. Для типизированных файлов тип переменных должен совпадать с типом элементов файла, для текстовых вместо переменных можно использовать любые выражения символьного, строкового или числового типа. В текстовый файл данные записываются в текстовом виде, а в типизированный – в том виде, в котором хранятся значения этих типов в оперативной памяти. При выполнении Read и Write, файловый указатель передвигается вперед на количество обработанных компонент. Если файловый указатель стоит за концом файла, то вызов процедуры Write произведет запись в конец файла. Вызов же процедуры Read в этом случае для типизированных файлов приведет к ошибке (для текстовых – ошибки не происходит). Erase(f) – удалить файл (файл должен быть закрыт). Rename(f,newname) – переименовать файл (файл должен быть закрыт).

2.2 Подпрограммы для работы с файлами в Delphi Cледующие подпрограммы доступны в Delphi при подключении модуля SysUtils: FileExists(name) – функция, возвращающая True, если файл с именем name существует, и False в противном случае. DirectoryExists(name) – функция, возвращающая True, если каталог с именем name существует, и False в противном случае. 7

DeleteFile(name) – функция, удаляющая файл с именем name и возвращающая True, если файл удален, и False в противном случае. RemoveDir(name) – функция, удаляющая каталог с именем name и возвращающая True, если каталог удален, и False в противном случае. GetCurrentDir – функция, возвращающая имя текущего каталога. SetCurrentDir(name) – процедура, устанавливающая каталог с именем name текущим. CreateDir(name) – процедура, создающая каталог с именем name. Если в переменной s типа string хранится полное имя файла, то ExtractFilePath(s) – функция, возвращающая путь к файлу. ExtractFileName(s) – функция, возвращающая имя файла. ExtractFileExt(s) – функция, возвращающая расширение файла. Например, для s='D:\MyPrograms\a.pas' функция ExtractFilePath(s) возвращает 'D:\MyPrograms\', функция ExtractFileName(s) возвращает 'a.pas' и функция ExtractFileExt(s) возвращает '.pas'. Процедуры Assign, Rename и Close, а также тип text в Delphi имеют синонимы AssignFile, RenameFile, CloseFile и TextFile. Они были введены для устранения коллизии имен при совместном использовании с классами компонент, в которых имеются методы с именами Assign, Rename, Close, Text.

2.3 Простые примеры: чтение и запись Пример 1. Рассмотрим задачу записи всех целых чисел от 1 до 9 в файл. Приведем код для типизированных файлов: var f: file of integer; i: integer; begin Assign(f,'a.dat'); Rewrite(f); for i:=1 to 9 do write(f,i); Close(f); end; Вначале с файловой переменной f связывается файл на диске a.dat, затем файл создается и одновременно открывается, в цикле в него записываются числа, после чего файл закрывается. Для текстовых файлов (тип text) код аналогичен, однако для разделения чисел в тексте между ними выводятся пробелы: 8

Assign(f,'a.txt'); Rewrite(f); for i:=1 to 9 do if i<9 then write(f,i,’ ’) else write(f,i); Close(f); Несмотря на похожий код программ, содержимое этих файлов будет существенно различаться. Файл a.dat будет иметь размер, равный 9 элементам типа integer, то есть 36 байтам, и будет содержать целые числа в двоичном формате, в котором они хранятся в оперативной памяти. Просматривать содержимое такого файла лучше всего в специализированном редакторе (например, в программе FAR по F3, установив шестнадцатеричный способ отображения). Файл a.txt будет содержать числа в том виде, в котором они выводятся на экран: 1 2 3 4 5 6 7 8 9 Пример 2. Рассмотрим обратную задачу – считать из файла все числа и вывести их на экран. Пусть числа хранятся в файле a.dat в двоичном формате. Тогда следует использовать типизированные файлы и следующий программный код: var f: file of integer; x: integer; begin Assign(f,'a.dat'); Reset(f); while not Eof(f) do begin Read(f,x); Write(x,' '); end; Close(f); end; Если числа хранятся в файле a.txt в текстовом формате и разделены пробелами, то следует использовать текстовые файлы. Код программы будет почти таким же, за исключением того, что файловая переменная должна иметь тип text и связываться с файлом a.txt.

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

Имеется два способа обработки ошибок ввода/вывода. Первый способ применяется при отключенном контроле над ошибками ввода/вывода (директива компилятора {$I-}). Он состоит в использовании стандартной функции IOResult, которая возвращает целочисленный результат последней операции ввода/вывода. Если IOResult возвращает 0, то операция успешна, в противном случае возвращается код ошибки. Приведем пример, иллюстрирующий этот механизм. Пример 1. Составить функцию MyFileExists, проверяющую, существует ли файл с именем name. function MyFileExists(name: string): boolean; var f: file; begin Assign(f,name); {$I-} Reset(f); {$I+} Result := IOResult=0 if Result then Close(f); end; Отметим, что в модуле SysUtils имеется аналогичная функция FileExists. Второй способ обработки ошибок ввода/вывода использует механизм исключений. Если контроль над ошибками ввода/вывода включен (директива компилятора {$I+}, этот режим действует в Delphi по умолчанию), то генерируется исключение. Пример 2. Составить функцию MyFileExists, используя механизм обработки исключений. Для реализации этого способа контроль над ошибками ввода-вывода должен быть включен ({$I+}) и к программе должен подключаться модуль SysUtils: {$I+} uses SysUtils; function MyFileExists(name: string): boolean; var f: file; begin Assign(f,name); try Reset(f); Close(f); Result:=True; 10

except Result:=False; end; end;

2.5 Типизированные файлы Напомним, что для описания типизированного файла используется конструкция file of тип. При этом в качестве типа компонентов файла не может фигурировать файловый тип или тип длинных строк AnsiString (по умолчанию в Delphi string=AnsiString, поэтому конструкция file of string вызовет ошибку компиляции). При работе с типизированными файлами кроме основных процедур и функций можно использовать следующие: Truncate(f) – процедура, усекающая типизированный файл в позиции файлового указателя. Все элементы, начиная с текущего (то есть с элемента, на котором расположен файловый указатель), удаляются. Файл должен быть открыт. FileSize(f) – функция, возвращающая количество элементов в типизированном файле. FilePos(f) – функция, возвращающая позицию файлового указателя. Элементы нумеруются от нуля, так что номер последнего элемента равен FileSize(f)-1. Seek(f,i)– процедура, перемещающая файловый указатель на элемент с номером i. Рассмотрим несколько примеров, иллюстрирующих основные действия с типизированными файлами. Пример 1. Добавить число 0 в конец файла целых чисел a.dat (если файл не существует, то создать его). Решение. uses SysUtils; const name='a.dat'; var f: file of integer; x: integer; begin Assign(f,name); if not FileExists(name) then Rewrite(f) else Reset(f); Seek(f,FileSize(f)); x:=0; write(f,x); 11

Close(f); end; В данном примере следует обратить внимание на команду Seek(f,FileSize(f)), перемещающую файловый указатель за последний элемент, то есть на маркер конца файла. Пример 2. Дан файл вещественных чисел. Возвести все его элементы в квадрат. Решение 1. Всякий раз после считывания элемента будем возводить его в квадрат, возвращаться назад и записывать на старое место. const name='b.dat'; var f: file of real; x: real; begin Assign(f,name); Reset(f); for i:=0 to FileSize(f)-1 do begin read(f,x); x:=x*x; Seek(f,FilePos(f)-1); write(f,x); end; Close(f); end; В данном примере следует обратить внимание на команду Seek(f,FilePos(f)-1), перемещающую файловый указатель на предыдущий элемент. Решение 2. Создадим второй файл и будем записывать в него квадраты чисел из первого файла, после чего удалим первый файл и переименуем второй, дав ему имя исходного файла. const name='b.dat'; var f,f1: file of real; x: real; begin Assign(f,name); Reset(f); Assign(f1,'temp.dat'); Rewrite(f1); for i:=0 to FileSize(f)-1 do begin 12

read(f,x); x:=x*x; write(f1,x); end; Close(f1); Close(f); end; Пример 3. На диске хранится файл 'group.dat', содержащий записи о студентах. Каждая запись состоит из следующих полей: имя студента (типа string[30]), курс и группа. Требуется найти запись о студенте Иванове и перевести его в 10 группу. Данный пример иллюстрирует использование типизированных файлов для программирования простейших баз данных. Решение. const name = 'group.dat'; type Student = record name: string[30]; course,group: integer; end; var f: file of Student; s: Student; begin Assign(f,name); Reset(f); ind:=-1; for i:=0 to FileSize(f)-1 do // поиск begin read(f,s); if s.name = 'Иванов' then begin s.group:=10; Seek(f,i); write(f,s); break; end; end; Close(f); end. 13

Пример 4. Составить процедуру, сортирующую методом «пузырька» элементы файла целых чисел по возрастанию. Решение. При сортировке методом «пузырька» обмениваются соседние элементы, что удобно для файловой сортировки. Будем считывать из файла за один раз пару элементов и, если их следует поменять местами, записывать эти элементы в обратном порядке. Перед каждой операцией считывания/записи будем позиционировать файловый указатель с помощью операции Seek. type RealFile=file of real; procedure SortFile(var f: RealFile); var i,j: integer; x,y: real; begin for i:=FileSize(f)-1 downto 1 do for j:=0 to i-1 do begin Seek(f,j); read(f,x,y); if x>y then begin Seek(f,j); write(f,y,x); end; end; end; Следует обратить внимание на уже отмеченный факт, что файловую переменную можно передавать в подпрограмму только по ссылке. Отметим также, что задачу можно решить и так: считать данные из файла в массив, отсортировать его, после чего записать полученный массив в файл. Очевидно, сортировка в оперативной памяти пройдет быстрее, и такой метод предпочтителен для небольших файлов. Однако если содержимое файла не помещается целиком в оперативную память, то сортировка непосредственно в файле – единственный путь.

2.6 Текстовые файлы Напомним, что текстовые файлы имеют тип text и состоят из строк разной длины, разделяемых маркером конца строки EOLN. Символ с кодом 26 воспринимается как признак конца текстового файла. Будем называть его маркером конца текстового файла и обозначать EOF. При обращении к файлу из программы считается, что в конце файла обязательно находится символ EOF, даже если он отсутствует в физическом файле. Например, файл, состоящий из четырех строк 14

var i: integer; begin end. следующим образом воспринимается Паскаль-программой: var i: integer;<EOLN>begin<EOLN><EOLN>end.<EOF> Подпрограммы работы с текстовыми файлами имеют ряд особенностей. Процедура Reset(f) открывает текстовый файл f только на чтение, а процедура Rewrite(f) – только на запись. Процедура Write в качестве параметров может содержать любые выражения целого, вещественного, символьного, строкового или логического типа; переменные тех же типов, кроме логического, могут присутствовать в операторе ввода Read. Вывод осуществляется в текстовом виде, при этом можно использовать форматы вывода вида :w (w – целое число, задающее ширину поля вывода) и для вывода вещественных значений – формат :w:d (d – целое число, задающее количество цифр после десятичной точки; если d=0, то десятичная точка не выводится). При вводе чисел данные должны быть отделены друг от друга пробелами, символами табуляции или символами перехода на новую строку. Если при вводе числа файловый указатель находится на таком символе-разделителе, он пропускает все символы-разделители до первого значащего символа (символа с кодом больше 32), после чего пытается прочитать число. При неудачной попытке и включенном контроле за ошибками ввода-вывода {$I+} в Delphi либо генерируется исключение (если подключен модуль SysUtils), либо происходит ошибка времени выполнения (если модуль SysUtils не подключен). В отличие от двоичных файлов, считывание за пределами текстового файла не приводит к ошибке (в частности, функция IOResult возвращает 0), файловый указатель при этом не перемещается. При чтении за концом файла в символьную переменную записывается символ конца файла (#26), в числовую – нулевое значение, в строковую – пустая строка. Как и при вводе с клавиатуры и выводе на экран, для текстовых файлов можно использовать процедуры Writeln и Readln. Процедура Writeln после вывода вставляет в текстовый файл маркер конца строки. В частности, Writeln(f) просто осуществляет переход на новую строку в файле f. Процедура Readln после ввода пропускает все символы до конца строки включительно (вместе с символом EOLN). В частности Readln(f), просто переставляет файловый указатель в начало новой строки. Далее перечислим стандартные подпрограммы, предназначенные для работы только с текстовыми файлами. 15

Append(f) – процедура, открывающая текстовый файл в режиме добавления. Файловый указатель при этом устанавливается на маркер конца файла. Если файл не существует, то происходит ошибка времени выполнения. Eoln(f) – функция, возвращающая True, если файловый указатель стоит на маркере конца строки. SeekEof(f) – функция, пропускающая все пробелы, символы табуляции и символы перехода на новую строку, после чего возвращающая то же, что и Eof(f). SeekEoln(f) – функция, пропускающая все пробелы и символы табуляции, после чего возвращающая то же, что и Eoln(f). Две последние функции обычно используются для ввода чисел. Для текстовых файлов подпрограммы Truncate, Seek, FileSize, FilePos не применяются: их использование приведет к ошибке компиляции. Рассмотрим несколько примеров, иллюстрирующих основные действия с текстовыми файлами. Пример 1. Дан текстовый файл a.txt, содержащий целые числа, разделенные любым количеством пробелов или символов перехода на новую строчку. Найти их количество и сумму. Приведем пример подобного файла: 5 3 <EOLN> 4<EOLN> 77 8 <EOF> Решение 1. Поэлементная обработка. Вместо Eof будем использовать функцию SeekEof, которая пропускает пробельные символы перед тем как проанализировать состояние конца файла. Это важно при считывании последнего числа: после считывания числа 8 файловый указатель будет находиться на пробеле после него; вызов SeekEof продвинет указатель на конец файла и вернет True. Для обработки возможных ошибок ввода окаймим также тело цикла блоком try с пустой секцией except: в случае ошибки в файле нечисловые символы будут пропущены. Далее приводится полный текст первого варианта решения. uses SysUtils; var f: text; s,c,x: integer; begin Assign(f,'a.txt'); Reset(f); s:=0; c:=0; while not SeekEof(f) do 16

try read(f,x); s:=s+x; c:=c+1; except end; Close(f); writeln(c,' ',s); end. Отметим, что если использовать функцию Eof вместо SeekEof, то при наличии пробелов в конце файла после считывания последнего числа Eof(f) вернет False и на следующей итерации цикла вызов read(f,x) запишет в переменную x число 0. В результате количество целых чисел c будет на 1 больше правильного. Решение 2. Посимвольная обработка. Вторая стратегия решения заключается в посимвольном считывании и накапливании в некоторой строковой переменной s текущей лексемы. Лексемой здесь мы будем называть любую последовательность символов, не являющихся разделителями. Если считанный символ является разделителем и лексема в строке s не пуста, то она считается сформированной и обрабатывается (преобразуется в число), после чего строка s обнуляется. Если же считанный символ не является разделителем, то он просто добавляется к строке s. Преобразование лексемы в число можно осуществить процедурой Val, что позволяет обойти использование механизма исключений. Далее приводится полный текст второго варианта решения. var f: text; ch: char; i: integer; begin Assign(f,'a.txt'); Reset(f); sum:=0; s:=''; repeat read(f,ch); if not (ch in [#0..#32]) then s:=s+ch else if s<>'' then begin Val(s,i,errcode); if errcode=0 then sum:=sum+i; 17

s:=''; end until Eof(f); Close(f); end. Заметим, что в данной задаче условие Eof(f) эквивалентно условию ch=#26. Заметим также, что разбиение на лексемы в данном варианте решения можно использовать в ряде других задач (связанных, например, с разбиением текста на слова). Пример 2. Преобразовать строки текстового файла, воспользовавшись для преобразования каждой строки пользовательской функцией Convert. Решение. В отличие от предыдущего примера, где мы пользовались поэлементным или посимвольным считыванием, будем считывать строку целиком, после чего ее обрабатывать. Такое решение естественно назвать построчной обработкой. Результат преобразования будем записывать во вспомогательный файл (имя ему дадим произвольно). В конце программы решение содержится во вспомогательном файле, поэтому удалим основной файл и дадим вспомогательному файлу имя основного: var f,f1: text; // f1-вспомогательный файл s: string; begin Assign(f,'a.txt'); Reset(f); Assign(f1,'$tmp.dat'); Rewrite(f1); while not Eof(f) do begin readln(f,s); s:=Convert(s); writeln(f1,s) end Close(f); Close(f1); Erase(f); Rename(f1,'a.txt'); end. Обратим внимание на ошибку, которую часто допускают начинающие в подобной ситуации. Если вместо процедуры readln в данной программе использовать процедуру read, то программа зациклится. Причина состоит в том, что оператор read считывает строку до символа-разделителя строк, устанавливая файловый указатель непосредственно на нем. Поэтому все вызовы read, начиная со 18

второго, будут возвращать пустую строку, а файловый указатель продвигаться не будет. Кроме того, после прерывания зациклившейся программы на диске останется большой временный файл $tmp.dat. В заключение заметим, что данный каркас решения можно использовать и для родственных задач. Например, если требуется вычислить количество и сумму чисел в файле (как в примере 1), то в данном решении достаточно заменить функцию Convert процедурой подсчета количества и суммы чисел в строке и изъять все строки, связанные со вспомогательным файлом.

2.7 Алгоритмы внешней сортировки Алгоритмы внешней сортировки – это алгоритмы, позволяющие сортировать данные во внешней памяти. Они ориентированы на последовательный перебор элементов и поэтому ранее широко применялись именно для сортировки файлов. Однако эти алгоритмы могут быть использованы для любых последовательно организованных данных: например, для массивов и списков. Кроме того, данные алгоритмы по скорости работы сравниваются с алгоритмом быстрой сортировки и потому являются одними из лучших. Реализация этих алгоритмов, однако, является достаточно громоздкой, поэтому в настоящем пункте приведем лишь сам алгоритм. Далее будем предполагать, что используемые файлы имеют только последовательный доступ. Сами файлы будем называть также лентами (по аналогии с лентой магнитофонной кассеты, доступ к которой может быть только последовательным). Трехленточная двухфазовая сортировка слиянием

Пусть исходные данные хранятся в файле C, и количество данных есть степень двойки. Приводимый ниже алгоритм использует на каждом шаге две фазы (разделение и слияние) и три ленты (файла). Отсюда его название – трехленточная двухфазовая сортировка слиянием. Разобьем данные на серии. Серией будем называть группу подряд идущих отсортированных элементов. I шаг. На первом шаге в каждой серии будет содержаться один элемент. C: 23 │ 12 │ 49 │ 96 │ 14 │ 69 │ 73 │ 28 I фаза. Разделение. Файлы A и B очищаются. Серии в файле C с нечетными номерами записываются в файл A, а с четными – в файл B. A: 23 │ 49 │ 14 │ 73 B: 12 │ 96 │ 69 │ 28

19

II фаза. Слияние. Файл C очищается. Серии элементов с одинаковыми номерами в файлах A и B сливаются в одну серию с помощью алгоритма слияния двух упорядоченных последовательностей в одну и дописываются в конец файла C. C: 12 23 │ 49 96 │ 14 69 │ 28 73 II шаг. В каждой серии – два элемента. I фаза. Разделение. A: 12 23 │ 14 69 B: 49 96 │ 28 73 II фаза. Слияние. C: 12 23 49 96 │ 14 28 69 73 III шаг. В каждой серии – четыре элемента. I фаза. Разделение. A: 12 23 49 96 B: 14 28 69 73 II фаза. Слияние. C: 12 14 23 28 49 69 73 96 Заметим, что в каждой фазе совершается один последовательный проход по каждому файлу. Отметим также, что если количество элементов в файле C равно n, то количество шагов алгоритма равно log 2 n . Поскольку на каждом шаге совершается два прохода по файлу C с n элементами, то количество операций при сортировке слиянием имеет временную сложность n ⋅ log 2 n (как и для быстрой сортировки). Четырехленточная однофазовая сортировка слиянием

В предыдущем алгоритме вторая фаза неэффективна – данные просто переписываются из одного файла в другой. От этой фазы можно избавиться, введя дополнительную ленту (файл). Для этого на фазе слияния следует записывать данные не в один файл, а попеременно в два, а затем использовать эти файлы в качестве исходных на следующем шаге. Пусть первоначально файл C содержит те же данные, что и в предыдущем пункте. C: 23 12 49 96 14 69 73 28 На первом шаге данные из файла C следует разбить на два файла, попеременно записывая их в файл A и файл B: A: 23 │ 49 │ 14 │ 73 B: 12 │ 96 │ 69 │ 28 Произведем слияние серий. Серии с нечетными номерами будем сливать в первый файл, с четными – во второй. 20

C: 12 23 │ 14 69 D: 49 96 │ 28 73 Повторим слияние серий, используя полученные файлы в качестве исходных. A: 12 23 49 96 B: 14 28 69 73 На последнем шаге полученные два файла следует слить в один, записав элементы второго файла в конец первого. C: 12 14 23 28 49 69 73 96 Отметим, что на каждом шаге по каждому файлу мы совершаем один последовательный проход. Естественное слияние

В двух предыдущих алгоритмах не учитывается упорядоченность элементов. Эти алгоритмы работают одинаковое время для любых последовательностей данных, в частности, если данные уже отсортированы. Предложим более совершенный алгоритм, в котором учитывается уже имеющаяся упорядоченность элементов. Такой алгоритм называется естественным слиянием. Пусть данные находятся в файле C. Разобьем их на серии упорядоченных элементов. C: 17 19 21 │ 13 57 67 │ 23 29 │ 11 59 61 │ 7 31 37 │ 2 43 67 │ 5 Применим алгоритм трехленточной двухфазовой сортировки, но в конце каждой фазы будем разбивать элементы на серии заново. I шаг. I фаза. Разделение. A: 17 19 21 │ 23 29 │ 7 31 37 │ 5 B: 13 57 67 │ 11 59 61 │ 2 43 67 Обратим внимание, что две первых серии в массиве A могут быть объединены в одну: A: 17 19 21 23 29 │ 7 31 37 │ 5 II фаза. Слияние. C: 13 17 19 21 23 29 57 67 │ 7 11 31 37 59 61 │ 2 5 43 67 II шаг. I фаза. A: 13 17 19 21 23 29 57 67 │ 2 5 43 67 B: 7 11 31 37 59 61 II фаза. C: 7 11 13 17 19 21 23 29 31 37 57 59 61 67 │ 2 5 43 67 21

III шаг. I фаза. A: 7 11 13 17 19 21 23 29 31 37 57 59 61 67 B: 2 5 43 67 II фаза. C: 2 5 7 11 13 17 19 21 23 29 31 37 43 57 59 61 67 67 Разбиение на серии не обязательно проводить специально – это можно делать в процессе слияния. Очевидно, серия заканчивается, если следующий элемент либо отсутствует, либо меньше предыдущего. Заметим также, что для сортировки нам потребовалось всего 3 шага, несмотря на то, что исходная последовательность состоит из 18 элементов, а не из 8, как в предыдущем пункте.

2 Рекурсия 2.1 Основные определения Рекурсия – это способ определения объекта, при котором он частично определяется через такой же объект. Определение, содержащее рекурсию, называется рекурсивным определением. Например, натуральное число – это либо 1, либо целое число, следующее за натуральным. Рекурсивные определения удобно записывать с помощью форм БэкусаНаура: Массив ::= <пусто> | элемент Массив СписокПараметров ::= параметр | СписокПараметров ’,’ параметр Обратим внимание, что во всех предыдущих примерах объект при некотором условии определяется нерекурсивно. Это условие является признаком окончания рекурсии. Обратим также внимание, что рекурсивный объект может стоять как в начале рекурсивного определения (леворекурсивное определение), так и в конце (праворекурсивное определение). Рекурсивно можно определять не только объекты, но и математические функции. Функция называется рекурсивной, если ее значение при некоторых значениях аргументов определяется через значение этой функции при других значениях аргументов. Например: ⎧n ⋅ ( n − 1)! , åñëè n > 0, n! = ⎨ ⎩1, åñëè n = 0. ⎧a ⋅ a n −1 , åñëè n > 0, n a =⎨ ⎩1, åñëè n = 0.

22

В программировании рекурсия – это описание подпрограммы, содержащее прямой или косвенный вызов этой подпрограммой самой себя. Если подпрограмма р вызывает себя в своем теле, то такая рекурсия называется прямой, если же подпрограмма р вызывает подпрограмму q, которая прямо или косвенно вызывает р, то такая рекурсия называется косвенной. Рекурсией также называют процесс выполнения рекурсивной подпрограммы.

2.2 Простые примеры использования рекурсии Рассмотрим несколько примеров рекурсивных подпрограмм. Пример 1. procedure p; begin write(1); p; end; При вызове процедуры p произойдёт рекурсивное зацикливание: будет выводиться 1, после чего процедура снова будет вызывать себя и т.д. до бесконечности. Поскольку при каждом вызове процедуры на программный стек помещается ее запись активации, то в конце концов программный стек переполнится, и программа завершится с ошибкой. Таким образом, чтобы рекурсия завершалась, необходимо, чтобы рекурсивный вызов происходил не всегда, а лишь при выполнении некоторого условия. Пример 2. procedure p(n: integer); begin write(n,' '); if n>0 then p(n-1); end; При вызове p(5) вначале выведется 5, после чего вызовется p(4), выведется 4 и вызовется p(3) и т.д. до вызова p(0), который выведет 0 и, поскольку условие n>0 станет ложным, рекурсия завершится. Итак, в результате вызова p(5) на экран будет выведено 5 4 3 2 1 0 Таким образом, использование рекурсии позволяет заменить цикл. Отметим, что в простых примерах такая замена неэффективна, так как накладные расходы на рекурсивный вызов процедур (копирование параметров на программный стек, запоминание адреса возврата и т.д.) намного превосходят затраты на организацию цикла.

23

Пример 3. procedure p(n: integer); begin if n>0 then p(n-1); write(n,' '); end; При вызове p(5) вначале проверится условие n>0 и, поскольку оно истинно, вызовется p(4), затем p(3) и т.д. до p(0). Так как при вызове p(0) условие n>0 уже не выполняется, то осуществится вывод 0 и произойдет выход из вызова p(0) в вызов p(1) сразу после условного оператора. Далее осуществится вывод 1 и выход из вызова p(1). Процесс возврата из уже сделанных рекурсивных вызовов продолжится, пока не будет осуществлен выход из вызова p(5). В результате на экран будет выведено 0 1 2 3 4 5 Схема рекурсивных вызовов в примерах 2 и 3 изображена на рисунке:

Процесс рекурсивных вызовов называется рекурсивным спуском, а процесс возврата из них – рекурсивным возвратом. Глубиной рекурсии называется максимальное число вложенных рекурсивных вызовов (в примерах 2 и 3 глубина рекурсии равна 5). Число вложенных рекурсивных вызовов в данный момент выполнения программы называется текущим уровнем рекурсии. Отметим, что в примере 2 действия осуществляются на рекурсивном спуске, поэтому порядок действий – прямой (в порядке вызова рекурсивных процедур). В примере 3, напротив, действия осуществляются на рекурсивном возврате, т.е. откладываются до достижения наивысшей глубины рекурсии, после чего начинают выполняться в порядке, обратном порядку вызова. Реализуем рекурсивные функции из примеров в начале пункта. Пример 4. Вычисление n! Реализация повторяет рекурсивное определение n!, данное в начале главы: function Nfact(n: integer): integer; begin if n=0 then Result:=1 else Result:=n*Nfact(n-1); end; 24

Пример 5. Вычисление a n . Рассмотрим рекурсивное определение a n , которое является более эффективным, чем приведенное в начале главы, и, кроме того, учитывает случай n < 0 : ⎧1, если n = 0, ⎪ n/2 2 ⎪( a ) , если n > 0, n − четное, n a =⎨ n −1 ⎪a ⋅ a , если n > 0, n − нечетное, ⎪1 a n , если n < 0. ⎩

Реализация также не вызывает затруднений: function Power(a: real; n: integer): real; begin if n=0 then Result:=1 else if n<0 then Result:=Power(a,-n) else if Odd(n) then Result:=a*Power(a,n-1) else Result:=Sqr(Power(a,n div 2)); end; При программировании рекурсивных подпрограмм следует следить за глубиной рекурсии: она не должна быть очень большой, чтобы программный стек не переполнился. Нетрудно видеть, что при вычислении a 16 глубина рекурсии равна 5:

При вычислении же a15 функция Power последовательно вызывается для аргументов 15, 14, 7, 6, 3, 2, 1, 0, и глубина рекурсии составляет 7. Недостаток данного алгоритма состоит в том, что переменная a не меняется, но передается в каждый рекурсивный вызов. Сделаем переменную a глобальной по отношению к рекурсивной функции, для чего окаймим ее нерекурсивной функцией с параметрами a и n, осуществляющей в своем теле стартовый вызов рекурсивной функции: function Power(a: real; n: integer): real; function Power0(n: integer): real; begin if n=0 then Result:=1 25

else if Odd(n) then Result:=a*Power0(n-1); else Result:=Sqr(Power0(n div 2)); end; begin Result:=Power0(n); end; Пример 6. Минимум в массиве. Чтобы найти минимум в массиве из n элементов, достаточно найти минимум в массиве из первых n – 1 элементов, после чего выбрать минимальный из этого минимума и последнего элемента массива. Если в массиве всего один элемент, то он – минимальный. Запишем данный алгоритм в виде рекурсивной функции MinA: ⎧ A[n ], n = 1, MinA( A, n ) = ⎨ ⎩ MinA( A[n ], MinA( A, n − 1)), n > 1.

Реализация повторяет рекурсивное определение: function MinA(const A: RArr; n: integer): real; begin if n=1 then Result:=A[n] else begin Result:=MinA(A,n-1); if A[n]
Замечание 3. Можно доказать, что любая прямая рекурсия может быть заменена итерацией.

2.3 Доказательство завершимости рекурсии Как показать, что при вызове пряморекурсивной подпрограммы не происходит рекурсивного зацикливания, то есть рекурсивный вызов завершим? В самом простом случае с каждым рекурсивным вызовом связывается целое число n. Предположим, что рекурсия завершается, когда n ≤ 0 . Если нам удастся показать, что при каждом рекурсивном вызове n уменьшается, то рекурсивный вызов завершим. Именно поэтому в большинстве рекурсивных подпрограмм удобно использовать целый параметр n, который при каждом рекурсивном вызове уменьшается на 1, и завершать рекурсию, когда данный параметр становится равным 0.

2.4 Формы рекурсивных подпрограмм Выделим следующие виды пряморекурсивных подпрограмм. 1) Действия осуществляется на рекурсивном спуске. procedure p(n); begin S(n); if B(n) then p(n-1) end; 2) Действия осуществляются на рекурсивном возврате. procedure p(n); begin if B(n) then p(n-1) S(n); // отложенные действия end; 3) Действия осуществляются и на рекурсивном спуске, и на рекурсивном возврате. procedure p(n); begin S1(n); if B(n) then p(n-1) S2(n); end; Данный вид рекурсии удобно представлять себе следующим образом. Мы спускаемся по лестнице с пронумерованными ступеньками (n – номер ступеньки), делая шаг на каждую ступеньку, пока выполняется условие B(n), после чего возвращаемся в начальную точку. Перед тем, как совершить следующий шаг, мы выполняем действие S1(n) и обязуемся выполнить действие S2(n) когда будем воз27

вращаться. Таким образом, действия на рекурсивном спуске совершаются в прямом порядке, а обещанные действия осуществляются на рекурсивном подъеме в порядке, обратном порядку обещаний. 4) Каскадная рекурсия. procedure p(n); begin S(n) if B1(n) then p(n-1); if B2(n) then p(n-1); end; 5) Удаленная рекурсия. function f(i: integer): integer; begin if B1(n) then Result:=... else Result:=f(f(i-1)); end; В этом виде рекурсии результат рекурсивного вызова является параметром другого рекурсивного вызова. Наиболее известным примером удаленной рекурсии является функция Аккермана: ⎧m + 1, если n = 0, ⎪ A( n, m ) = ⎨ A( n − 1, 1), если n > 0, m = 0, ⎪ A( n − 1,A( n, m − 1)), если n > 0, m > 0. ⎩

В последних двух видах рекурсии рекурсивные вызовы образуют древовидную структуру.

2.5 Пример плохого использования рекурсии Пример 7. Пример плохого использования рекурсии. Числа Фибоначчи. Как известно, определение чисел Фибоначчи рекурсивно: ⎧1, n = 1,2, fn = ⎨ ⎩ f n −1 + f n −2 , n > 2.

Данное определение легко переводится в рекурсивную функцию: function Fib(n: integer): integer; begin if (n=1) or (n=2) then Result:=1 else Result:=Fib(n-1)+Fib(n-2); end;

28

Однако, такое «лобовое» решение крайне неэффективно, поскольку содержит большое количество повторяющихся вычислений. Изобразим дерево рекурсивных вызовов для вызова Fib(7):

Из рисунка видно, что, например, Fib(5) вычисляется дважды, Fib(4) – трижды, Fib(3) – 5 раз и т.д., то есть количество повторных вызовов представляет собой, по иронии судьбы, последовательность чисел Фибоначчи!

2.6 Более сложные примеры использования рекурсии Пример 8. Ханойские башни. Это – классический пример задачи, у которой имеется простое рекурсивное решение, а нерекурсивное решение является существенно более громоздким и дает лишь незначительный выигрыш в эффективности. Задача состоит в следующем. Имеется три штыря, на одном из которых лежит пирамида из n дисков, причем, меньшие диски лежат на больших (см. рисунок).

Требуется, перекладывая по одному диску на соседние штыри, переложить всю пирамиду с одного штыря на другой за наименьшее количество ходов. При этом запрещается класть больший диск на меньший. Сведем задачу с n дисками к задаче с n – 1 дисками (фактически, применим метод математической индукции по числу дисков). Пусть нам требуется переложить пирамиду из дисков со штыря с номером f (from) на штырь с номером t (to), используя штырь w (work) в качестве вспомогательного. Для этого необходимо вначале переложить пирамиду из n – 1 диска со штыря f на штырь w, используя штырь t в качестве вспомогательного, затем переместить оставшийся диск со штыря f на штырь t и, наконец, переложить пирамиду из n – 1 диска со штыря w на штырь t, используя штырь f в качестве вспомогательного. 29

procedure MoveTown(n,f,t,w: integer); begin if n=0 then exit; MoveTown(n-1,f,w,t); MoveDisk(f,t); MoveTown(n-1,w,t,f); end; Процедура MoveDisk, обеспечивающая перемещение одного диска, либо выдает текстовую информацию о том, с какого на какой диск было осуществлено перемещение, либо перемещает диск графически, меняя рисунок с изображениями штырей и дисков, подобный приведенному в начале данного примера. Нетрудно показать, что глубина рекурсии равна n, а количество перемещений дисков составляет 2 n − 1 . Пример 2. Сгенерировать все перестановки длины n. Заполним массив тождественной перестановкой. Будем менять первый элемент с каждым последующим, включая себя, после этого совершать те же действия с оставшейся частью массива и менять элементы обратно: for i:=1 to n do begin Swap(A[i],A[1]); ... Swap(A[i],A[1]); end; В итоге каждый элемент побывает на первом месте. Вместо многоточия вызовем аналогичную процедуру для элементов со второго по последний. Таким образом, мы реализовали следующую идею: получить все перестановки n элементов можно, поставив на первое место каждый элемент и дописав к нему все перестановки из оставшихся элементов. Очень важным шагом здесь является последний оператор цикла, возвращающий обратно элемент, переставленный на первом шаге цикла. Это гарантирует, что в начале каждой итерации цикла мы имеем дело с одной и той же перестановкой. Поскольку рекурсивные вызовы необходимо совершать для элементов с индексами от 2 по n, затем от 3 по n и т.д., в качестве параметра рекурсивной процедуры будем передавать k – начальный индекс переставляемого элемента (таким образом, перестановка будет совершаться для элементов с номерами от k до n). В результате наша рекурсивная процедура примет вид: procedure Permutation0(k: integer); var i: integer; begin for i:=k to n do begin 30

Swap(A[i],A[k]); ... Permutation0(k+1); Swap(A[i],A[k]); end; end; Очевидно, при k=n рекурсию надо завершать и выдавать полученную перестановку. Приведем итоговую процедуру, считая, что для вывода массива A длины n составлена процедура Print(A,n). procedure Permutation(n: integer); var A: IArr; procedure Permutation0(k: integer); var i: integer; begin for i:=k to n do begin Swap(A[i],A[k]); if k=n then Print(A,n) else Permutation0(k+1); Swap(A[i],A[k]); end; end; var i: integer; begin for i:=1 to n do A[i]:=i; Permutation0(1); end;

2.7 Быстрая сортировка Алгоритм быстрой сортировки – один из самых производительных и часто используемых алгоритмов сортировки. Основная идея алгоритма быстрой сортировки состоит в следующем. На первом шаге выбирается некоторый опорный элемент x, относительно которого переупорядочиваются остальные элементы массива. Переупорядочение осуществляется следующим образом: все элементы, меньшие x, переставляются перед x, а больше или равные x – после x. В итоге массив оказывается разбит на две части: элементы, меньшие x, и элементы, большие или равные x. Затем к первой и второй частям рекурсивно применяется алгоритм быстрой сортировки до тех пор, пока в каждой части не останется по одному элементу. Желательно выбрать элемент x таким, чтобы количество элементов в 31

первой и второй части было примерно одинаковым (в идеале отличалось бы на 1 – в этом случае элемент x называется медианой массива). Однако, поиск медианы массива – достаточно долгий алгоритм, поэтому обычно в качестве элемента x выбирают любой элемент массива, например, средний. Рассмотрим алгоритм подробнее. После выбора опорного элемента x введем два индекса i и j, указывающие соответственно на первый и последний элементы массива A. Увеличивая i, найдем элемент A[i], не меньший x. Затем, уменьшая j, найдем элемент A[j], не больший x. Такие элементы всегда найдутся: в крайнем случае, таким элементом будет сам элемент х. Поменяем элементы A[i] и A[j] местами, после чего увеличим i на 1 и уменьшим j на 1. Продолжим эти действия до тех пор, пока i не окажется больше j. В этот момент все элементы A[1]..A[j] меньше или равны x, а все элементы A[i]..A[n] - больше или равны x. Теперь применим наш алгоритм рекурсивно к подмассивам A[1]..A[j] и A[i]..A[n]. Процесс рекурсивных вызовов прекращается, если подмассив состоит из одного элемента. Рассмотрим конкретный пример. Пусть массив A размера n=9 имеет вид: 2 7 6 9 4 5 8 3 1 i j Выберем в качестве x средний элемент A[5]=4 и положим i=1, j=n. Увеличивая i, найдем элемент A[i]>=x (это элемент A[2]=7) и уменьшая j найдем элемент A[j]<=x (это элемент A[9]=1). 2 7 6 9 4 5 8 3 1 i j Поменяем их местами и передвинем индексы i и j соответственно вперед и назад: 2 1 6 9 4 5 8 3 7 i j Аналогично поменяем местами элементы 6 и 3, затем 9 и 4. В результате индекс i станет больше индекса j: 2 1 3 4 9 5 8 6 7 j i Следует обратить внимание на то, что i может быть больше j на 1 или на 2, а также на то, что опорный элемент в преобразованном массиве может поменять свое место. Итак, мы разделили массив на две части. Часть элементов с номерами от 1 до j меньше или равна x, а часть элементов с номерами от j до n – больше или равна x. Осталось рекурсивно применить алгоритм быстрой сортировки к обеим частям. Ниже приводится код алгоритма: 32

procedure QuickSort(var A: IArr; n: integer); procedure QuickSort0(l,r: integer); var i,j,x: integer; begin i:=l; j:=r; x:=A[(l+r) div 2]; repeat while A[i]<x do Inc(i); while A[j]>x do Dec(j); if i<=j then begin Swap(A[i],A[j]); Inc(i); Dec(j); end until i>j; if l<j then QuickSort0(l,j); if i
2.8 Рекурсия в модулях Подпрограммы, участвующие в косвенной рекурсии, могут описываться в разных модулях. В этом случае возникает рекурсивная зависимость между модулями. Пусть подпрограмма р вызывает подпрограмму q, а подпрограмма q вызывает подпрограмму р, то есть имеет место косвенная рекурсия. Наша задача – поместить р в модуль Unit1.pas, а q – в модуль Unit2.pas. Циклическая зависимость между модулями запрещена, если обе ссылки на модули в секции uses содержатся в разделе interface. То есть, следующие описания приведут к ошибке: Unit1.pas unit Unit1; interface uses Unit2; procedure p;

Unit2.pas unit Unit2; interface uses Unit1; procedure q;

...

...

33

Однако циклическая зависимость между модулями разрешена, если одна или обе ссылки модулей друг на друга содержатся в разделе implementation. Таким образом, задача об описании взаимно рекурсивных подпрограмм в разных модулях решается следующим образом: Unit1.pas unit Unit1; interface procedure p; implementation uses Unit2; procedure p; begin ... q; end; end.

Unit2.pas unit Unit2; interface procedure q; implementation uses Unit1; procedure q; begin ... p; end; end.

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

2.9 Интерпретатор формул Реализуем разбор и вычисление выражения, заданного следующей грамматикой: Expr ::= Term { "+" Term | "-" Term } Term ::= Factor { "*" Factor } Factor ::= num | ( Expr ) num ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

Формула представляет собой выражение со скобками, знаками операций + - * и целыми числами от 0 до 9. Формула будет разбираться и тут же вычисляться. Посуществу, мы напишем простейший интерпретатор формул. Правилам грамматики Expr, Term и Factor поставим в соответствие функции, возвращающие целое значение. Заметим, что определение грамматики содержит косвенную рекурсию: Expr определяется через Term, Term – через Factor, Factor – вновь через Expr. Поэтому перед описанием функции Expr следует использовать forward-объявления функций Term и Factor.

34

Пусть формула хранится в строке s и является правильной, номер текущей позиции в строке s хранится в целой переменной ns. Перед тем как проанализировать следующий символ, вызывается процедура MoveNext, переходящая на следующую лексему в строке s и записывающая ее в символьную переменную CurSym. Если строка закончилась, то в переменную CurSym записывается нулевой символ. Чтобы уменьшить количество глобальных переменных, поместим все функции грамматики и процедуру MoveNext внутрь функции-оболочки Calc и сделаем ns и CurSym ее локальными переменными. Функция Calc будет принимать строку s в качестве параметра и возвращать вычисленное выражение. Приведем далее полный текст программы. function Calc(s: string): integer; var ns: integer; CurSym: char; procedure MoveNext; begin Inc(ns); if ns<=Length(s) then CurSym:=s[ns] else CurSym:=#0; end; function Num: integer; begin Result:=Ord(CurSym)-Ord('0'); end; function Term: integer; forward; function Factor: integer; forward; function Expr: integer; begin Result:=T; while CurSym in ['+','-'] do begin if CurSym='+' then begin MoveNext; Result:=Result+Term; end else begin MoveNext; Result:=Result-Term; 35

end end; end; function Term: integer; begin Result:=Factor; while CurSym='*' do begin MoveNext; Result:=Result*Factor; end; end; function Factor: integer; begin if CurSym='(' then begin MoveNext; Result:=Expr end else Result:=Num; // CurSym является цифрой MoveNext; end; begin // Calc ns:=0; MoveNext; Result:=Expr; end; begin // основная программа writeln(Calc('1+2-4')); end. Обратим внимание на то, что процедура MoveNext должна быть вызвана перед каждой функцией грамматики и, в частности, в начале функции Calc.

2.10 Перевод формулы в префиксную форму Обычной формой записи выражений является инфиксная. В ней знак бинарной операции op записывается между операндами: A op B. Если знак бинарной операции записывается перед операндами, то такая форма запись называется префиксной: op A B. Если же знак бинарной операции записывается после операндов, то форма записи выражения называется постфиксной: A B op.

36

Например: Инфиксная форма 1+2*4 (1+2)*4

Префиксная форма +1*24 *+124

Постфиксная форма 124*+ 12+4*

Обратим внимание, что ни префиксная, ни постфиксная форма не содержат скобок; по этой причине их часто называют префиксной бесскобочной и постфиксной бесскобочной формой записи выражения. Реализуем компилятор, переводящий выражение в инфиксной форме в префиксную бесскобочную форму. В отличие от предыдущей программы, функции Expr, Term, Factor будут возвращать строковое представление префиксной бесскобочной формы. Как и в предыдущем примере, поместим функции Expr, Term, Factor и процедуру MoveNext внутрь функции Prefix, принимающей в качестве параметра строку s – выражение в инфиксной форме. После преобразования строки к префиксной бесскобочной форме вызывается функция Calc, играющая роль ее интерпретатора. Следует обратить внимание на то, что если префиксная бесскобочная форма построена, то она не содержит синтаксических ошибок (все синтаксические ошибки были выявлены на этапе "компиляции" в префиксную бесскобочную форму), и при ее интерпретации о проверке синтаксических ошибок уже можно не заботиться. Приведем полный текст программы. function Prefix(s: string): string; var ns: integer; CurSym: char; procedure MoveNext; begin Inc(ns); if ns<=Length(s) then CurSym:=s[ns] else CurSym:=#0; end; function Term: string; forward; function Factor: string; forward; function Expr: string; begin Result:=Term; while CurSym in ['+','-'] do begin Result:=CurSym+Result; MoveNext; 37

Result:=Result+Term; end; end; function Term: string; begin Result:=Factor; while CurSym='*' do begin Result:='*'+Result; MoveNext; Result:=Result+Factor; end; end; function Factor: string; begin if CurSym='(' then begin MoveNext; Result:=Expr; if CurSym=')' then MoveNext else error; end else if CurSym in ['0'..'9'] then begin Result:=CurSym; MoveNext end else error end; begin // Prefix MoveNext; Result:=Expr; end; function Calc(s: string): integer; var i: integer; function Calc0: integer; var o1,o2: integer; begin Inc(i); case s[i] of '+': begin o1:=Calc0; o2:=Calc0; Result:=o1+o2; end; 38

'-': begin o1:=Calc0; o2:=Calc0; Result:=o1-o2; end; '*': begin o1:=Calc0; o2:=Calc0; Result:=o1*o2; end; '0'..'9': Result:=Ord(s[i])-Ord('0'); end; end; begin // Calc i:=0; Result:=Calc0; end; var res: string; begin res:=Prefix('(1+2)*3'); writeln(res); writeln(Calc(res)); end.

2.11 Алгоритм перебора с возвратом Алгоритм перебора с возвратом используется, когда решение представляет собой некоторую последовательность элементов: a1 , a2 ,..., an . Суть его заключается в следующем. На каждом этапе имеется некоторое частичное решение a1 , a2 ,..., ak , к которому мы пытаемся добавить следующий элемент из множества возможных (происходит перебор возможных продолжений). Процесс добавления элементов завершается либо когда получено решение, либо когда не остается элементов, которые можно добавить. Если элементов для добавления нет, а решение не получено, то последний добавленный элемент удаляется (осуществляется возврат к предыдущему шагу), и предпринимается попытка добавить другой элемент. Алгоритм заканчивается если найдено решение либо все варианты исчерпаны. Пусть глобальная логическая переменная Success получает значение True как только будет найдено решение. До начала работы алгоритма она должна быть инициализирована в False. Пусть также i – переменная, характеризующая глубину рекурсии и передаваемая как параметр рекурсивной процедуре. Запишем алгоритм в «крупных командах». Алгоритм перебора с возвратом для нахождения одного решения

procedure Try0(i: integer); begin формирование списка кандидатов

repeat выбор очередного кандидата (перебор) if подходит then

begin 39

запись кандидата if решение неполное then

begin Try0(i+1); if not Success then стирание кандидата (возврат)

end; else Success:=True end; until Success or кандидатов больше нет end; Отметим, что как только переменная Success получает значение True, мы выходим из всех рекурсивных вызовов процедуры Try0, не совершая никаких дополнительных действий. Рассмотрим реализацию указанного выше алгоритма на примере задачи обхода конем шахматной доски размера n × n . Составим вначале внутреннюю процедуру Try0, для которой переменная Success (удача) и массив Solution (решение) будут глобальными. Всего из данной клетки конь может совершить максимум 8 ходов, которые мы пронумеруем так, как показано на рисунке.

Для каждого из этих ходов необходимо проверить, находится ли клетка в пределах шахматной доски, и не ходил ли конь в эту клетку раньше. Если клетка – в пределах доски и конь в нее еще не ходил, то мы пробуем совершить в нее ход, помечая клетку номером хода, после чего, если все клетки обойдены, то мы устанавливаем переменную Success в True (решение найдено), в противном случае вызываем процедуру Try0 повторно с координатами новой клетки в качестве параметра и проверяем, решена ли задача. Если задача не решена, то ход следует признать неудачным и стереть его из списка ходов (возврат). Далее приводится код решения. program KnightWay; const n=8; dx: array [1..8] of integer=(-1,1,2,2,1,-1,-2,-2); dy: array [1..8] of integer=(2,2,1,-1,-2,-2,-1,1); var Solution: array [1..n,1..n] of integer; // массив ходов 40

procedure TryM(x,y: integer; var Success: boolean); procedure Try0(i,x,y: integer); var k, // номер кандидата u,v: integer; // координаты следующего хода коня begin k:=0; repeat Inc(k); u:=x+dx[k]; v:=y+dy[k]; if (u>0) and (u<=n) and (v>0) and (v<=n) and (Solution[u,v]=0) then begin Solution[u,v]:=i; if i
В глобальной процедуре TryM, содержащей Try0, обнуляется массив Solution и совершается первый ход, после чего переменная Success полагается равной False и вызывается Try0 с координатами первой клетки в качестве параметров. Алгоритм перебора с возвратом для нахождения всех решений

Алгоритм построения всех решений проще предыдущего, поскольку в нем отсутствует флаг Success и после нахождения решения оно сразу же обрабатывается (например, выводится на экран), и поиск оставшихся решений продолжается. procedure Try0(i: integer); begin Формирование списка кандидатов

repeat выбор очередного кандидата if подходит then

begin запись кандидата if решение неполное then

Try0(i+1) else печать решения (или его обработка) стирание кандидата

end until кандидатов больше нет end; Упражнение. Вывести все решения в задаче об обходе конем шахматной доски.

Литература 1. Зеленяк О. Практикум программирования на Turbo Pascal / О. Зеленяк. – М.: DiaSoft, 2002. – 310 с. 2. Ставровский А. Турбо Паскаль 7.0 / А.Ставровский. – Киев: BHV, 2001. – 400 с. 3. Вирт Н. Алгоритмы и структуры данных / Н. Вирт. – М.: Мир, 1989. – 360 с.

42