Вы - -й посетитель этой странички 

Олимпиады по информатике. Пути к вершине

Лекции читает Е.В. Андреева

Лекция 3. Техника программирования олимпиадных задач

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

Директивы компилятора

    Как уже было показано выше, при программировании на языке Турбо Паскаль практически необходимо вставлять директивы для компилятора в текст программы. В противном случае при компиляции программы из командной строки (в этом случае используются те значения для ключей компилятора, которые установлены по умолчанию) или из среды программирования, в которой через меню были установлены не те значения для ключей, при которых отлаживалась программа, работа программы может не соответствовать ожиданиям. Напомним, что разместить директивы компилятора (значения ключей компилятора и характеристики оперативной памяти, выделяемой программе при ее выполнении) в тексте программы можно с помощью команды <Ctrl> + <O> <O> . Наличие директив компилятора в тексте позволяет легко их редактировать, а компиляция такой программы будет производиться согласно установленным параметрам тех или иных ключей. Приведем значения ключей компилятора, наиболее оптимальные для отладки программы, и прокомментируем наиболее важные из рекомендованных установок параметров:

{$A+, B-, D+, E+, F+, G-, I+, L+, N+, O-, R+, S+, T+, Q+, P-, V+, X+}
{$M 65520, 0, 655360}

    Собственно, для отладки программы наиболее значимыми являются ключи D+ и L+. Именно благодаря им в исполнимый код программы вставляется отладочная информация и из среды программирования программу можно выполнять “по шагам”, просматривая значения тех или иных переменных на различных стадиях выполнения программы.
    Еще одна пара ключей — E+ и N+ необходима, если программа использует вещественные числовые типы данных, арифметические и логические операции над которыми производятся с помощью сопроцессора, а именно: comp, single, double и extended. Без упомянутых ключей программа, использующая эти типы, просто не будет компилироваться. Строго говоря, ключ E+ был необходим лишь для компьютеров, сопроцессор в которых отсутствовал и операции над вещественными числами осуществлялись с помощью так называемого эмулятора — программы, реализующей эти операции только через команды процессора. Однако все процессоры класса Pentium содержат встроенный сопроцессор, который будет использоваться при выполнении программы, написанной на языке Турбо Паскаль, в случае установки ключа компилятора N+. Заметим, что одновременное “включение” и эмулятора и сопроцессора приводит к использованию последнего при наличии сопроцессора и эмулятора при его отсутствии. То есть такая комбинация ключей делает программу “переносимой”, не зависящей от компьютера, на котором она исполняется.
    Установка ключа I+ приводит к тому, что при работе программы строго контролируется соответствие поступающих на вход программы констант типам переменных, которым значения этих констант будут присвоены. В случае несоответствия типов, например при вводе символа вместо числа или вещественного числа вместо целого, выполнение программы будет прервано.
    Совершенно незаменима при отладке программы установка ключей компилятора R+ и Q+ (последний из них появился лишь в версии Turbo Pascal 7.0). Они позволяют контролировать во время выполнения программы “выход за границу массивов” и “выход за границу допустимого диапазона значений” при операциях над целочисленными переменными. То есть при попытке обращения к несуществующему элементу массива или если во время выполнения операции (арифметической или присваивания) над целыми числами результат, в том числе и промежуточный, не является допустимым для соответствующего типа, то выполнение программы прерывается. При этом ключ R+ отвечает за корректную работу с массивами и присваивание только допустимых значений переменным типа byte и shortint, а Q+ — за корректное выполнение арифметических операций над целыми числами в рамках соответствующих типов (подробнее об организации целочисленной компьютерной арифметики и возникающих при этом ошибках можно прочитать в главе 6 книги Е.Андреевой, И.Фалиной “Системы счисления и компьютерная арифметика”. М: “Лаборатория базовых знаний”, 2000). При отсутствии такого контроля поиск ошибки может быть затруднен тем, что промежуточные вычисления чаще всего производятся в целом типе наибольшего размера (обычно 32-разрядном), и лишь при присваивании полученного значения переменной меньшего размера лишние старшие разряды оказываются отброшенными. Как следствие, отладочная информация о значении арифметического выражения и его результат могут не совпадать.
    Рассмотрим это на примере следующей простой программы:

    {$Q-}
    var a:integer;
    begin
        a := 1 * 2 * 3 * 4 * 5 * 6 * 7;
        writeln('7!=', a);
        a := a * 8;
        writeln('8!=', a)
    end.

    Если после получения переменной a своего первого значения, равного 7!, мы посмотрим в отладчике значение выражения a * 8, то оно будет равно 40 320, а в результате второго присваивания значение a окажется равным —25 216.
    Наконец, при установленном ключе компилятора S+ в программу вставляется код проверки стека на переполнение. Максимальный размер стека устанавливается директивой компилятора $M, о параметрах которой речь пойдет ниже. Заметим, что прерывание работы программы с диагностикой Stack overflow (переполнение стека) чаще всего означает, что в программе есть подпрограмма, использующая рекурсивные вызовы, работа которой вследствие ошибки завершиться не может.
    После того как программа отлажена, то, как уже говорилось в п. 9 порядка решения олимпиадных задач (см. лекцию 2), ряд ключей компилятора следует заменить на противоположные, а именно: сдавать программу на тестирование следует с ключами D-, I-, L-, R-, Q- . Объясняется это двумя причинами. Во-первых, при отмене ряда проверок и отсутствии отладочной информации программа будет выполняться быстрее. Во-вторых, если часть ошибок при отладке не устранена, но ошибки эти не являются для программы фатальными (например, обращение к несуществующему элементу массива может не влиять на правильное формирование реальных его элементов), то программа может вполне успешно пройти процедуру тестирования. Если же проверка корректного обращения с данными в исполняемом коде остается, то скорее всего на большинстве тестов выполнение программы будет прервано досрочно и результат ее работы просто не будет получен.
    Рассмотрим теперь, на что влияет директива компилятора $M. В обычном режиме конфигурация памяти, отводимой для работы программы, характеризуется тремя числами. Первое число определяет максимальный размер в байтах для стека, который будет использоваться программой. Максимально возможный размер стека равен 65 520 байтам, размер стека по умолчанию — 16 384 байтам, а минимально возможный — 1024 байтам. Если в программе используется рекурсия, то скорее всего ей понадобится достаточно большой стек, вплоть до максимально возможного. Но и однократный вызов процедуры или функции требует наличия стека достаточного размера, особенно если в качестве параметра- значения в процедуру или функцию передается массив (по этой причине массивы и сопоставимые с ними по объему занимаемой памяти переменные рекомендуется передавать только по ссылке, в Паскале — с использованием ключевого слова var). Уменьшать размер стека с помощью директивы компилятора имеет смысл только в случае использования динамических переменных, применять которые при решении задач школьных олимпиад по информатике требуется достаточно редко. На размер памяти, отводимой под глобальные статические переменные, повлиять практически невозможно, все вместе они не могут занимать более 64 килобайт памяти (например, один массив из 10 000 чисел типа real занимает 60 000 байт, то есть почти всю допустимую память). Данное ограничение является неестественным для современных компьютеров, следовательно, системы программирования, его содержащие, будут вытеснены, как это уже произошло на международной олимпиаде по информатике 2001 года (см. № 37/2001). Оставшуюся после размещения глобальных переменных и фиксации размера стека оперативную память можно использовать лишь для создаваемых во время работы программы динамических переменных. Показанные в нашем примере значения второго и третьего параметров в директиве $M как раз и позволяют использовать всю оставшуюся в распоряжении программы память. Ее размер в обычном случае работы DOS-приложения ограничен 640 килобайтами, часть из которых используют другие программы (командный процессор, драйвер русской клавиатуры и т.д.). В условиях олимпиады участникам обычно гарантируется наличие 350—400 килобайт свободной оперативной памяти для работы программы участника (конкретное значение оговаривается заранее), и именно на этот объем и следует ориентироваться при создании динамических переменных. К сожалению, каждая из создаваемых во время работы программы динамических переменных в отдельности не может занимать более все тех же 64 килобайт памяти. Примеры создания и использования динамических переменных будут приведены ниже.
    В заключение рассмотрим директивы так называемой условной компиляции, которые иногда удобно применять при отладке олимпиадных задач. В зависимости от того, была или нет определена с помощью директивы $define некоторая последовательность символов, часть кода программы, ограниченная директивами $ifdef и $endif, может быть как включена, так и исключена из процесса компиляции. Если же два фрагмента программы являются альтернативными, то есть включен в программу должен быть строго один из них, то в дополнение к уже перечисленным можно использовать директиву $else. Рассмотрим это на примере организации ввода данных в программу или из файла, или с клавиатуры (например, по условию задачи данные должны вводиться из файла, а при отладке входные параметры удобнее вводить с клавиатуры).

    var n : integer;
    begin
    {$define debug}
    {$ifdef debug}
        assign(input,'con');
    {$else}
        assign(input,'input.txt');
    {$endif}
        reset(input);
        read(n)
        …
    end.

    Так как в приведенном фрагменте программы последовательность debug определена, то ввод данных будет осуществляться с клавиатуры, если же эту команду отменить (закомментировать или слово debug в ней заменить на, например, nodebug), то ввод данных будет производиться из файла INPUT.TXT.

Ввод и вывод данных

    В большинстве олимпиадных задач ввод данных и вывод результатов работы программы предлагается производить из текстового файла. У ряда участников олимпиад такое техническое требование вызывает некоторое затруднение. Покажем, как можно быстро преодолеть все сложности работы с файлами и сделать при этом как можно меньше ошибок.
    Как уже видно из примера, приведенного в конце предыдущего раздела, для организации ввода данных из текстового файла наличие файловой переменной типа text в программе вовсе не обязательно. Более того, перенаправление стандартного потока ввода input и потока вывода output в файлы и является более удобным при программировании, и избавляет от ряда ошибок. Как это можно сделать, видно из приведенного выше примера (см. также лекцию 2). После подобного перенаправления ввод данных из файла осуществляется с помощью обычных процедур read и readln, а вывод — с помощью write и writeln без указания в качестве первого параметра имени какой-либо файловой переменной. Такой подход избавляет от типичной ошибки при работе с текстовыми файлами, которая заключается в том, что в некоторых обращениях к процедурам ввода или вывода имя файловой переменной оказывается пропущенным. Это не нарушает работу программы в целом, так как часть информации может быть записана в файл, а часть — выведена на экран. Но так как проверке подлежит лишь создаваемый программой файл, то скорее всего оценить такую программу на олимпиаде будет невозможно. Вторая типичная ошибка при работе с файлом, открытым на запись, — отсутствие в конце программы команды, закрывающей файл. В таком случае создаваемый программой выходной файл скорее всего окажется пустым. Дело в том, что реальная запись данных на жесткий диск происходит или при выполнении команды close, или, если количество выводимой информации велико, в момент переполнения буфера оперативной памяти, предназначенного для ускорения работы с файлами. Но и от этой ошибки работа со стандартным потоком вывода спасает. Дело в том, что файл output закрывается при окончании работы программы автоматически, вне зависимости от наличия или отсутствия команды close(output).
    Рассмотрим теперь полезные приемы программирования ввода данных различных типов. Начнем с описания считывания из текстового файла или консоли (клавиатуры), которая с точки зрения программы также является текстовым файлом, числовых данных. В условии задачи ввод большого количества чисел может быть задан двумя способами. В первом способе сначала предлагается ввести количество чисел, а уж затем сами эти числа. В данном случае при программировании сложности не возникают. Во втором же случае количество чисел приходится определять в процессе их считывания. Пусть, например, для каждой строки входного файла требуется найти среднее арифметическое для чисел, расположенных в ней, количество чисел в каждой из строк и количество строк при этом неизвестно. Наиболее простым и правильным будет следующее решение такой задачи:

    while not seekeof do
    begin
        n := 0;
        s := 0;
        while not seekeoln do
        begin
            read(a);
            s := s + a;
            n := n + 1
        end;
        {readln;}
        if n > 0 then writeln(s/n:0:2) else writeln
    end;

    Заметим, что обычно применяемые в таких случаях функции eof и eoln заменены на seekeof и seekeoln соответственно. Имя файловой переменной при этом опускается, что опять же работает для стандартного потока ввода, даже после перенаправления его в файл. Только при показанном способе ввода чисел не возникают ошибки в работе подобной программы, связанные с наличием пробелов в конце строк и пустых строк в конце файла, так как для корректного использования функции eof требуется, чтобы признак конца файла стоял непосредственно после последнего числа в файле. То же требование относится к признаку конца строки при использовании функции eoln. Несмотря на то, что числа расположены в различных строках файла, процедуру readln при вводе именно чисел можно не использовать (в приведенном примере она взята в комментарий, снятие которого не изменит работу программы). Отметим, что техническую проблему, связанную с обработкой заранее неизвестного количества чисел в строке или в файле в целом, разрешить на языке программирования Си несколько сложнее.
    Наоборот, если во входном файле находится текст, размер которого неизвестен, то поступать следует несколько по-другому. Использование seekeoln может привести к ошибке, так как в тексте пробел уже является значимым символом. С другой стороны, служебные символы, обозначающие конец строки в файле и перевод на новую строку (их коды 13 и 10), не могут считаться частью текста и не должны анализироваться алгоритмом его обработки. Поэтому если известно, что длина каждой строки текстового файла не превосходит 255 символов, то удобнее всего считывание производить с использованием переменной типа string:

    while not eof do
    begin
        readln(S);
        if S <> '' then {обработать строку S}
    end;

    В этом примере использование readln, а не read является уже принципиальным. Если же ограничения на количество символов в одной строке нет, то считывание следует производить посимвольно. Причем на всероссийской или международной олимпиаде отсутствие такого ограничения означает, что при тестировании программы действительно будут тесты, содержащие очень длинные строки, а на школьной или районной олимпиаде — что скорее всего такое ограничение просто забыли включить в текст условия, а все тесты будут состоять все-таки из коротких строк. Пример посимвольного считывания текста из файла:

    while not eof do
    begin
        n := 0;
        while not eoln do
        begin
            read(с);
            {запись символа с в массив или его обработка}
            n := n + 1
        end;
        readln;{!}
        if n > 0 then {обработка строки}
                    else {строка пустая}
    end;

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

    while not seekeof do
    begin
        read(c);
        S := '';
        {формируем строку с фамилией}
        while c <> ' ' do
        begin
            S := S + c;
            read(с)
        end;
        read(n);{считываем год рождения}
        readln(c,c);{считываем пол}
        …{обработка считанной информации}
    end;

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

    writeln(x:0:0)

    Если же результат работы программы представляет собой произвольное вещественное число, то формат его вывода обычно оговорен в условии задачи. Так, если требуется получить в дробной части три цифры, то печать можно производить по формату x:0:3.

Инициализация данных и создание динамических переменных

    Как уже говорилось в предыдущей лекции, одна из типичных ошибок при программировании, в том числе и олимпиадных задач, — неинициализация глобальных переменных. Нулевые значения всем статическим переменным в программе присвоить достаточно легко. Сделать это можно аналогично тому, как было показано в процедуре initial в “универсальной программе для решения олимпиадных задач” (см. лекцию 2), а именно:   

fillchar(i,Ofs(Last) - Ofs(i) + SizeOf(Last),0)

    Здесь i — имя обязательно первой из описанных в программе переменных, Last — имя последней из глобальных переменных (число 65500, являющееся параметром fillchar в initial не приведет к ошибке, только если статические переменные занимают не менее 65 000 байт. Поэтому использовать конкретные числовые значения в данном случае не рекомендуется).
    Таким образом, данная стандартная процедура заполнит нулями все байты памяти, которые могут использовать статические переменные. После выполнения этой операции все числовые переменные, в том числе и элементы массивов, получат нулевые значения, всем символьным будет присвоен символ с кодом 0, а всем строковым — пустые строки, так как в байт, отвечающий за длину строки, также занесен ноль, и т.д. Если же количество глобальных переменных в программе невелико и не для всех из них ноль подходит в качестве начального значения, то инициализацию можно проводить для каждой переменной в отдельности. Для простых переменных это можно делать с помощью оператора присваивания или путем описания переменных как типизированных констант (в разделе описаний const, но с одновременным указанием и типа переменной, и ее значения). Для массивов — с использованием все той же процедуры fillchar, но в пределах конкретного массива. Например:

    var a : array[1..1000] of integer;
           c : array[1..10000]of char;
    begin
        {заполняем массив a нулями}
        fillchar(a, sizeof(a), 0);
        {заполняем символом плюс массив с}
        fillchar(с, sizeof(с), '+');
        …
    end.

    К сожалению, таким способом ненулевые значения можно присвоить лишь массивам, элементы которых по размеру не превосходят один байт (типы byte, shortint, char, boolean). Значения элементов массивов других типов приходится задавать в цикле. Однако если два массива одного и того же типа требуется проинициализировать одинаково, то заполнить в цикле можно только один из них, а второму массиву просто присвоить первый (присваивание — единственная допустимая операция над составными переменными, такими, как массив, как над целыми объектами). Иногда массивы удобно описывать и задавать в разделе констант путем непосредственного перечисления значений всех элементов массивов.
    Как уже говорилось выше, для размещения всех глобальных переменных программе отводится не более 64 килобайт оперативной памяти. Однако при решении задач иногда требуется завести несколько массивов, размер каждого из которых не менее 32 килобайт. Покажем, как достаточно просто решить подобную проблему:

    const n = 150;
    type aa = array[1..n, 1..n] of integer;
    var a : aa; {a — массив}
          b : ^aa; {b — указатель на массив}
          i, j : integer;
    begin
        fillchar(a, sizeof(a), 0);
        new(b); {создание динамического массива}
        {копирование массива a в динамический массив}
        b^ := a;
            for i := 1 to n do
                for j := 1 to n do
                {обращение к элементам динамического массива}
                    b^[i,j] := i + j;
        …
    end.

    Из примера видно, что работа с динамическими массивами не намного отличается от работы со статическими. Причем использовать данный прием можно “по образцу”, не вдаваясь в механизм работы с указателями. Если же размер двухмерного массива превосходит 64 килобайта, то создать его с помощью динамических переменных можно, например, следующим образом:

    const n = 500;
              m = 100;
    type aa = array[1..n] of integer;
    var b : array[1..m] of ^aa;
        {b — массив указателей на одномерный массив}
          i,j : integer;
    begin
        for i := 1 to m do
            {создание m динамических массивов}
            new(b[i]);
        for i := 1 to m do
            for j := 1 to n do
                {обращение к элементам двухмерного массива}
                    b[i]^[j] := i + j;
    …
    end.

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

Подсчет времени работы программы

    На олимпиадах высокого уровня, к которым можно отнести и региональные соревнования, практически всегда в тексте условия задачи указано максимальное время работы программы на одном тесте. Поэтому писать программу, которая будет работать при каких-либо входных данных дольше этого времени, смысла нет. Если же выбранный участником алгоритм в отведенное для работы программы время не укладывается, то зачастую помогает прием, называемый отсечение по времени. Применяется он в основном в задачах, решение которых производится с помощью перебора вариантов (а большинство олимпиадных задач в силу их дискретности можно решать с помощью полного перебора вариантов, правда, лишь при небольших размерностях). Пусть в условии задачи требуется найти любой допустимый или даже оптимальный вариант, а при отсутствии допустимого варианта выдать сообщение, что решение отсутствует. Тогда работу программы следует организовать так, чтобы по истечении отведенного на ее выполнение времени выполнение программы заканчивалось и печаталось лучшее из рассмотренных к этому моменту решений или сообщение об отсутствии решения. Если перебор в такой программе организовать “с предпочтением”, то есть сначала рассматривать наиболее вероятные варианты, то такая программа может работать правильно почти на всех входных данных, несмотря на возможную неэффективность заложенного в нее алгоритма. Так как правильно организованный перебор зачастую быстро находит решение задачи, а рассмотрение остальных вариантов необходимо в нем лишь для того, чтобы доказать оптимальность уже найденного. Поэтому если за отведенное время не найден никакой вариант, то будем считать, что решение в задаче отсутствует (конечно, это не всегда оказывается справедливым), а если какой-то вариант найден, но перебор еще не закончен, то опять же можно надеяться, что этот вариант и есть искомый. В любом случае такая программа всегда результативно заканчивает свою работу за время ее тестирования, и баллы, полученные за нее, могут быть весьма высокими (иногда такая программа получает полный балл за ре шение задачи).
    Осталось показать, как программно реализовать описанный прием отсечения рассматриваемых вариантов по времени. Опытные участники олимпиад делают это так:

    const timetest = 10;
            {время тестирования программы}
    var timer : longint absolute $40:$6c;
            timeold : longint;
    begin
        timeold := timer;
    while true do
        if timer — timeold > 18.2 * (timetest — 0.5) then
            begin
                …{запись текущего результата в файл или сообщение об отсутствии решения}
                halt
            end else {собственно работа программы}
    end.

    Данная программа использует тот факт, что к значению четырехбайтовой целой переменной, расположенной по абсолютному адресу $40:$6С, раз в 1/18.2 секунды аппаратно прибавляется единица. Поэтому если мы опишем в нашей программе переменную, привязав ее к этому адресу, то легко сможем определить время работы программы. А именно, запомнив в самом начале программы значение этой переменной (в нашем примере это оператор timeold := timer), в процессе работы определить время выполнения в секундах можно по формуле (timer — timeold) / 18.2. Поэтому если время тестирования известно, то прерывать поиск решения следует за некоторое время до его окончания (в нашем примере это 0,5 секунды), для того чтобы успеть вывести результат.

Лекция 4. Алгоритмы поиска в олимпиадных задачах

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

Алгоритмы поиска в неупорядоченных одномерных массивах

    Рассмотрим сначала нюансы реализации “технических” задач поиска, которые встречаются в различных алгоритмах. Начнем с, казалось бы, тривиальной задачи поиска элемента в неупорядоченном массиве. Во всех примерах, относящихся к поиску в одномерном массиве, будем использовать следующую переменную a:

        a:array[0..N] of <скалярный тип>;

— при этом собственно элементы массива, которые мы будем рассматривать, пронумерованы от 1 до N, а нулевой элемент будем использовать как вспомогательный в случае необходимости. Конкретный же тип элемента в большинстве описываемых алгоритмов не важен, он может быть как любым числовым, так и символьным или даже строковым. Алгоритм поиска в массиве элемента, значение которого равно K, может выглядеть так:

i := 0;
repeat
    i := i + 1
until (i = N) or (a[i] = K);
if a[i] = K then write(i)
                else write(0)
{следующее неверно (!!!):
if i = N then write(0)
            else write(i) }

    При отсутствии в массиве элемента с искомым значением K печатается значение нулевого индекса. Оказывается, что и такую достаточно простую программу можно упростить, заодно продемонстрировав так называемый “барьерный” метод, который часто применяется в программировании в том числе и олимпиадных задач. В данном случае он заключается в том, что мы можем занести в дополнительный элемент массива (например, нулевой) искомое значение K, избавившись тем самым в условии окончания цикла от проверки на выход за границу массива:

a[0] := K;
i := N;
while (a[i] <> K) do
    i := i — 1;
write(i)

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

imax := 1;
imin := 1;
for i := 2 to N do
    if a[i] < a[imin] then imin := i else
    if a[i] > a[imax] then imax := i

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

max := —MaxInt - 1;
{минимальное значение типа integer}
min := MaxInt;
{максимальное число значение integer}
for i := 1 to N do
    if a[i] < min then min := a[i] else
    if a[i] > max then max := i

    Казалось бы, на этом рассмотрение алгоритмов поиска в неупорядоченном массиве можно завершить. Однако именно с одновременного поиска минимума и максимума можно начать класс алгоритмов поиска более эффективных, чем приведенные выше стандартные алгоритмы. Причем именно при решении олимпиадных задач их знание может пригодиться в первую очередь. Итак, в приведенном выше алгоритме поиска максимального и минимального элементов в массиве в худшем случае выполняется 2N — 2 сравнений. Покажем, что ту же задачу можно решить за 3 éN/2ù — 2 сравнений (обозначение é ù  соответствует для неотрицательных чисел округлению до ближайшего целого числа, большего или равного выражению в указанных скобках, в отличие от целой части, где округление производится до ближайшего целого, меньшего или равного рассматриваемому выражению). Пусть у нас имеется четное число элементов. Разобьем их на пары и в каждой из N/2 пар за одно сравнение определим, какой элемент больше, а какой меньше. Тогда максимум можно искать уже любым способом только из наибольших элементов в парах, а минимум — среди наименьших. Общее число сравнений при этом равно
    N/2 + 2(N/2 — 1) = 3N/2 — 2.
    Для нечетного числа элементов элемент, не попавший ни в одну из пар, должен участвовать в поиске как максимума, так и минимума.
    Еще большей эффективности можно добиться при одновременном поиске максимального и второго по величине числа. Для этого организуем поиск максимума по схеме “теннисного турнира”, а именно: разобьем элементы на пары и определим в каждой из пар больший элемент, затем разобьем на пары уже эти элементы и т.д. В “финале” и будет определен максимум. Количество сравнений в таком алгоритме, как и в традиционной схеме, равно N—1. Однако максимальный элемент участвовал при этом в élog₂Nù сравнениях, причем одно из них проходило обязательно со вторым по величине элементом. Таким образом, теперь для поиска этого элемента потребуется всего  élog₂Nù — 1 сравнение (!!!). Попробуйте самостоятельно построить эффективный алгоритм для поиска уже первых трех по величине элементов.
    В данном контексте можно поставить также задачу поиска i-го по счету элемента, называемого i-й порядковой статистикой. Кроме максимума и минимума, специфической порядковой статистикой является медиана — элемент с номером (N + 1)/2 для нечетных N и два соседних элемента для четных. Конечно, задачу поиска любой порядковой статистики можно решить, предварительно отсортировав массив. Но, как будет показано ниже, оптимальные по количеству сравнений универсальные (то есть пригодные для произвольных массивов) алгоритмы сортировки выполняют порядка N log₂N сравнений. А задачу поиска i-й порядковой статистики можно решить, производя O(N) сравнений. Алгоритм, который гарантирует эту оценку, достаточно сложен, он подробно изложен в [1, 2, 3]. Мы же приведем схему алгоритма, который в худшем случае не является линейным, однако обычно работает существенно быстрее, следовательно, именно его и нужно использовать в практике реального программирования, в том числе и олимпиадных задач:

    Оптимальную реализацию пункта 3 можно заимствовать из алгоритма так называемой быстрой сортировки (см., например, [4]).
    Наконец, рассмотрим задачу поиска в последовательности из N чисел, хранения которой не требуется вообще, следовательно, ее длина может быть очень велика. Пусть известно, что в этой последовательности встречаются по одному разу все числа от 0 до N, кроме одного. Это пропущенное число и требуется найти. Вот возможное решение такой задачи:

    S := 0;
    for i := 1 to N do
    begin
        read(a); S := S + a
    end;
    writeln(N * (N + 1) div 2 — S)

    Данную программу легко переписать так, чтобы она работала и для значений N, превосходящих максимальное представимое целое число. Для этого следует использовать переменные типа extended, а цикл for заменить на while. Используя аналогичный прием, попробуйте решить следующую задачу. Пусть N — количество чисел, нечетно и известно, что среди вводимых N чисел каждое имеет ровно одно равное себе, а одно число — нет. Найдите это число.

    Указание. В данном случае можно воспользоваться свойством логической функции “исключающее или”, обозначаемой в Паскале как xor: a xor b xor b ≡ a.

    О других алгоритмах поиска в одномерных массивах можно прочитать, например, в [2, 3, 5, 6]. Особый интерес среди них представляет задача международной олимпиады по информатике 2000 года, посвященная нахождению медианы в массиве, причем не путем сравнения элементов между собой, а с помощью операции определения среднего элемента среди трех произвольных элементов массива, выполняемой библиотечным модулем, предоставленным участникам олимпиады.

Поиск в упорядоченных массивах

    Под упорядоченными в дальнейшем будут пониматься неубывающие массивы, если не оговорено иное. То есть a[1] ≤ a[2] ≤ … ≤ a[N].
    Сначала приведем пример реализации широко известного алгоритма двоичного (бинарного) поиска элемента, равного K, в уже упорядоченном массиве. Оказывается, досрочный выход из цикла в случае нахождения элемента выигрыша по скорости практически не дает, а лишние проверки делают программу более громоздкой. Поэтому рекомендуется производить поиск, пока диапазон рассматриваемых элементов состоит более чем из одного элемента.

    L := 1; R := N + 1;
    while L < R do
    begin
        m := (L + R)div 2;
        if a[m] < K then L := m + 1
                          else R := m
    end;
    if a[m] = K then write(m) else write(0)

    На полуфинале чемпионата мира по программированию среди студенческих команд вузов, проходившем в Санкт-Петербурге в 2000 году, предлагалась следующая обратная двоичному поиску задача (см. сайт neerc.ifmo.ru, на котором можно найти тесты и ответы к ним для указанной задачи). Известно, что алгоритм бинарного поиска, аналогичный приведенному выше, но заканчивающий свою работу в случае досрочного обнаружения элемента, за Q сравнений определил, что искомым является элемент с номером I. Какова могла быть при этом размерность массива (указать все допустимые диапазоны значений N)? Несмотря на кажущуюся сложность при заданных в условии ограничениях, задача решалась путем простого перебора различных значений N и обращения с каждым из этих значений к функции бинарного поиска. Конструктивный же подход к решению задачи намного сложнее. Однако и в случае подбора можно использовать немало интересных фактов. Например, длина каждого из диапазонов возможных значений N является степенью двойки, а каждый следующий диапазон не меньше предыдущего. Это позволяет значительно сократить количество рассматриваемых значений N. Кроме того, максимальное допустимое значение для N легко найти аналитически.
    Рассмотрим теперь задачу поиска в упорядоченном массиве наибольшего “равнинного” участка. То есть требуется найти такое число p, что в массиве имеется последовательность из p равных элементов и нет последовательности из p + 1 равных по значению элементов (см., например, [7]). Оказывается, существует алгоритм решения этой задачи, количество операций в котором может оказаться существенно меньше, чем N. Так, если мы уже нашли последовательность из p₁ равных между собой чисел, то другую последовательность имеет смысл теперь рассматривать только если ее длина не менее p₁ + 1. Поэтому если a[i] — первый элемент предполагаемой новой подпоследовательности, то сравнивать его надо сразу с элементом a[i + p], где p — максимальная величина для уже рассмотренных подпоследовательностей из равных элементов. Приведем фрагмент программы, решающий данную задачу. В качестве результата мы получаем длину максимальной подпоследовательности p, номер элемента, с которого эта подпоследовательность начинается, k и значение элементов в найденной подпоследовательности:

    p := 1; k := 1;
    i := 1; f := false;
    while i + p <= N do
        if a[i + p] = a[i] then
        begin
            p := p + 1; f := true
        end
        else if f then
                    begin
                        k := i; i := i + p; f := false
                    end
                else i := i + 1;
    writeln(p,' ',k, ' ',a[k])

    В [7] можно найти еще одну интересную задачу под названием “Жулик на пособии” поиска в упорядоченных последовательностях уже практически какой угодно длины. Пусть имеются три упорядоченных по алфавиту списка из фамилий людей, получающих пособие по безработице в трех различных местах. Длина каждого из списков может быть как угодно большой (каждый из списков можно хранить в отдельном файле). Известно, что по крайней мере одно лицо фигурирует во всех трех списках. Требуется написать программу поиска такого лица, порядок количества операций в которой не будет больше, чем сумма длин всех трех списков. Приведем фрагмент программы, работающий с тремя файлами, обращение к элементам которых (они могут быть любого типа, в том числе и string, к элементам которого в Паскале применимы операции сравнения, чтения и записи) из программы происходит с помощью файловых переменных x, y, z типа text:

    readln(x,p); readln(y,q); readln(z,r);
    while not((p = q)and(q = r)) do
    begin
        if p < q then readln(x,p)
        else if q < r then readln(y,q)
                else if r < p then readln(z,r)
    end;
    writeln(p);{p=q=r}

    Покажите, что для поставленной задачи чтение из файла всегда будет производиться корректно и на каждом шаге цикла значение одной из трех переменных p, q, r будет изменено. Кроме того, докажите, что с помощью этой программы всегда будет найден именно минимальный из элементов, присутствующих во всех трех файлах.
    Наконец, рассмотрим задачу поиска элемента, значение которого равно K, в двухмерном массиве, упорядоченном по строкам и столбцам: a[i,j] ≤ a[i,j+1], a[i,j] ≤ a[i+1,j], 1 ≤ i < N, 1 ≤ j < M. Данная задача решается за M + N действий, а не за M•N, как в произвольном массиве. Поиск следует начинать с эле- мента a[N,1]. Этот элемент самый маленький в своей строке и самый большой в своем столбце (в математике подобные элементы называют “седловыми точками”). Поэтому если он окажется меньше, чем K, то из рассмотрения первый столбец можно исключить, а если больше — из рассмотрения исключается последняя строка и т.д. Вот возможная реализация этого алгоритма:

    i := N; j := 1;
    while (i > 0) and (j < M + 1) and (a[i,j] <> K) do
        if a[i,j] < K then j := j + 1
        else i := i - 1;
    if (i > 0) and (j < M + 1) then writeln(a[i,j])

    Программа могла бы быть еще короче и эффективнее, если бы в ней использовался упоминавшийся выше барьерный метод. В данном случае для организации барьера требуется дополнить массив нулевой строкой и (M + 1)-м столбцом. Во все созданные барьерные элементы следует поместить значение K. Тогда условие в цикле можно сократить до следующего: a[i, j] <> K.

Алгоритмы поиска и задачи на взвешивания

    Появление подобных задач, например, задачи определения фальшивой монеты, в контексте рассмотрения алгоритмов поиска не случайно. Во-первых, поиск и в этом случае осуществляется путем операций сравнения, правда, уже не только одиночных элементов, но и групп элементов между собой. Во-вторых, как будет показано ниже, в отличие от олимпиад по математике для младших школьников задачи на взвешивания вполне можно решать конструктивно.
    В качестве примера рассмотрим задачу, предлагавшуюся на теоретическом туре одной из региональных олимпиад по информатике. Пусть у нас имеется 12 монет, одна из которых фальшивая, по весу отличающаяся от остальных монет, причем неизвестно, легче она или тяжелее. Требуется за три взвешивания определить номер фальшивой монеты (попробуйте решить эту задачу самостоятельно, и вы убедитесь, что это совсем не просто, а порой вообще кажется невозможным). Введем следующие обозначения. Знаком “+” будем обозначать монеты, которые во время текущего взвешивания следует положить на весы, причем если монета на весах уже была, то на ту же самую чашу, на которой эта монета находилась во время своего предыдущего взвешивания. Знаком “—” будем обозначать монеты, которые следует переложить на противоположную чашу весов, по отношению к той, на которой они находились (каждая в отдельности), заметим, что если монета на весах еще не была, то знак “—” к ней применен быть не может. Наконец, знаком “0” — монеты, которые в очередном взвешивании не участвуют. Тогда существует 14 различных способов пометки монет для трех взвешиваний:

    Из полученной таблицы вычеркнем 2 столбца так, чтобы в каждой из трех строк количество ненулевых элементов оказалось четным (ведь мы не можем во время одного взвешивания положить на две чаши весов нечетное число монет). Это могут быть, например, столбцы 4 и 14. Теперь будем взвешивать 12 монет так, как это записано в оставшихся 12 столбцах. То есть в первом взвешивании будут участвовать 8 произвольных монет, во втором — 3 монеты следует с весов убрать, 2 — переложить на противоположные по отношению к первому взвешиванию чаши весов и 3 монеты положить на весы впервые (на свободные места так, чтобы на каждой из чаш вновь оказались по 4 монеты). Согласно схеме проведем и третье взвешивание, опять располагая на каждой чаше весов по 4 монеты. Результат каждого взвешивания в отдельности никак не анализируется, а просто записывается. При этом равновесие на весах всегда кодируется нулем, впервые возникшее неравновесное состояние — знаком “плюс”, если при следующем взвешивании весы отклонятся от равновесия в ту же самую сторону, то результат такого взвешивания также кодируется плюсом, а если в другую сторону — то минусом. Например, записи “=<<” и “=>>” кодируются как “0++”, а записи “<=>” и “>=<” — как “+0-”. Так как мы не знаем, легче или тяжелее остальных монет окажется фальшивая, то нам важно, как изменялось состояние весов от взвешивания к взвешиванию, а не то, какая именно чаша оказывалась тяжелее, а какая легче. Поэтому два на первый взгляд различных результата трех взвешиваний в этом случае кодируются одинаково. После подобной записи результатов взвешиваний фальшивая монета уже фактически определена. Ею оказывается та, которой соответствует такой же столбец в таблице, как и закодированный нами результат трех взвешиваний. Для первого из примеров это монета, которая участвовала во взвешиваниях по схеме, указанной в 10-м столбце таблицы, а для второго — в 8-м. В самом деле, состояние весов в нашей задаче меняется в зависимости от того, где оказывается фальшивая монета во время каждого из взвешиваний. Поэтому монета, “поведение” которой согласуется с записанным результатом взвешиваний, такой результат и определяет.
    Анализ таблицы показывает, что эту задачу можно решить не только для 12, но и для 13 монет. Для этого следует исключить из рассмотрения любой не содержащий нулей столбец, например, все тот же четвертый. В остальном все действия остаются неизменными. Для произвольного числа монет N > 2 количество взвешиваний определяется по формуле  élog₃(2•N + 1)ù (за одно взвешивание задача не разрешима ни для какого количества монет!!!), но подход к решению задачи при этом не изменится.
    Попробуйте теперь решить задачу, которая предлагалась в 1998 году на уже упоминавшемся выше полуфинале чемпионата мира по программированию среди студенческих команд вузов. В ней также требовалось определить номер фальшивой монеты, вес которой отличался от остальных. Но все взвешивания уже были проведены, а их результаты записаны. Число взвешиваний являлось входным параметром в задаче (оно могло быть и избыточным по сравнению с описанным выше оптимальным алгоритмом определения номера фальшивой монеты). При этом в каждом из взвешиваний могло участвовать любое четное количество имеющихся монет (сколько и какие именно — известно). Результаты записывались с помощью символов “<”, “>” и “=”.
    Еще одна задача на взвешивания рассмотрена в [8]. В общем случае в ней требуется найти набор из минимального количества гирь, такой, что с его помощью можно взвесить любой груз, весящий целое число килограммов, в диапазоне от 1 до N кг. При необходимости гири можно располагать на обеих чашах весов. Так, для N = 40 это гири 1, 3, 9 и 27 кг.

Поиск подстроки в строке

    Формализовать эту задачу можно следующим образом. Пусть задан массив s из N элементов (строка) и массив p из M элементов (подстрока), причем 0 < M ≤ N. Требуется обнаружить первое непрерывное вхождение p в s. Эта задача на практике встречается очень часто. Так, в большинстве текстовых редакторов реализована операция поиска по образцу, которая практически полностью сов- падает с описанной задачей. Если размер массива s — N не превосходит 255, а тип его элементов — char, то в Турбо Паскале такой поиск можно выполнять с помощью стандартной функции Pos(p,s). Однако в общем случае ее приходится реализовывать самостоятельно. Прямой поиск, основанный на последовательном сравнении подстроки сначала с первыми M символами строки, затем с символами с номерами 2 .. M + 1 и т.д., в худшем случае произведет порядка N•M сравнений. Но для этой задачи известен алгоритм Боуера и Мура (см., например, [5]), который для произвольных строк выполняет не намного более N/M сравнений. То есть разница в вычислительной сложности составляет M² (!!!). Рассмотрим последний алгоритм, на примере которого также можно показать, что использование небольшого количества дополнительной памяти (в данном случае вспомогательного массива, размер которого равен размеру алфавита строк) позволяет существенно ускорить выполнение программы.
    Перед фактическим поиском для всех символов, которые могут встретиться в строке, вычисляется и запоминается в массиве d расстояние от самого правого вхождения этого символа в искомую подстроку до ее конца. Если же какого-то символа из алфавита строки в подстроке нет, то такое расстояние считается равным длине подстроки M. Посимвольное же сравнение подстроки с не- которым фрагментом строки производится не с начала, а с конца искомой подстроки (образца). Если какой-либо символ образца не совпадает с соответствующим символом фрагмента строки, а х — последний символ фрагмента строки, то образец можно сдвинуть вдоль строки вправо на d[x] символов. Если большинство символов в строке отличны от символов подстроки, то сдвиг будет происходить на M элементов, что и обеспечит приведенную выше сложность алгоритма. Покажем работу алгоритма на примере поиска слова коала в строке:

    кокаколулюбитикоала.
    коала
        коала
            коала
                коала
                    коала

    Здесь подчеркнуты символы, которые участвовали в сравнениях. Сдвиги определялись такими значениями массива d: d['к'] = 4, d['л'] = 1, d['ю'] = 5. Если бы последней в рассматриваемом фрагменте строки оказалась буква а, то величина сдвига была бы равна 2, так как в образце есть еще одна такая буква, отстоящая от конца на 2 символа, а при ее отсутствии сдвиг был бы равен 5. Приведем теперь возможную реализацию описанного алгоритма, для простоты считая, что размер подстроки не превосходит 255, что не снижает общности этой программы:

    const nmax = 10000;
    var p : string; {подстрока}
        s : array[1..nmax] of char; {строка}
        d : array[char] of byte; {массив сдвигов}
        c : char;
        m,i,j,k : integer;
    begin
        …{задание строки и подстроки}
        m := length(p);{длина подстроки}
        for c := chr(0) to chr(255) do d[c] := m;
        for j := 1 to m — 1 do d[p[j]] := m — j;
        {массив d определен}
        i := m + 1;
        repeat {выбор фрагмента в строке}
            j := m + 1; k := i;
            repeat {проверка совпадения}
                k := k — 1; j := j — 1
            until (j < 1) or (p[j] <> s[k]);
            i := i + d[s[i — 1]];{сдвиг}
        until (j < 1) or (i > nmax + 1);
        if j < 1 then write(k + 1) else write(0)
    end.

    Приведенный алгоритм не дает выигрыша только в одном случае — когда количество частичных совпадений искомой подстроки с фрагментами текста достаточно велико. Это возможно, например, при чрезвычайной ограниченности алфавита, из символов которого составляются строки. Тогда следует применять алгоритм Кнута — Мориса — Пратта, описанный в [5], или комбинацию из двух алгоритмов.
    Рассмотренную проблему не следует путать с такой задачей. Пусть заданы массив s из N элементов и массив p из M элементов, причем 0 < M ≤ N. Требуется выяснить, можно ли из первого массива вычеркнуть некоторые члены так, чтобы он совпал со вторым. Число операций в данном случае имеет порядок N + M.

Литература

    1. Ахо А.А., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы. М.: Вильямс, 2000.
    2. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. М.: МЦНМО, 2000.
    3. Окулов С.М. Основы программирования. “Информатика” № 27, 2001.
    4. Окулов С.M. Сортировка и поиск. “Информатика” № 35, 2000.
    5. Вирт Н. Алгоритмы и структуры данных. M.: Мир, 1989.
    6. Шень А. Программирование: теоремы и задачи. М.: МЦНМО.
    7. Грис Д. Наука программирования. M.: Мир, 1984.
    8. Андреева Е., Фалина И. Системы счисления и компьютерная арифметика. М.: Лаборатория базовых знаний, 2000.