Programming Taskbook

Электронный задачник по программированию

©  М. Э. Абрамян (Южный федеральный университет, Университет МГУ-ППИ в Шэньчжэне), 1998–2024

Наивный алгоритм поиска: Match4 (язык Pascal)

В качестве первого примера рассмотрим одно из заданий, связанных с реализацией наивного алгоритма поиска, требующего порядка nm сравнений символов (n — длина строки-образца, m — длина текста, в котором выполняется поиск):

Match4°. Даны строки P, T и число k. Строка P считается образцом (англ. pattern), строка T — текстом, в котором ищется образец. Известно, что длина суффикса строки T, начинающегося в позиции k, больше или равна |P|. Используя посимвольное сравнение, выполняемое слева направо, проверить, входит ли образец P в текст T, начиная с позиции k. Если входит, то вывести True, иначе вывести False. Вывести также количество потребовавшихся сравнений символов.

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

Для создания заготовки программы следует перейти в рабочий каталог задачника (по умолчанию это каталог C:\PT4Work) и вызвать программный модуль PT4Load с помощью его ярлыка Load. На экране появится окно модуля PT4Load, в котором будут перечислены все доступные группы заданий:

В списке должна присутствовать группа Match. Если она не указана, то это означает, что динамическая библиотека PT4Match.dll, в которой определена эта группа заданий, не найдена задачником. Для того чтобы библиотека была обнаружена, необходимо, чтобы она располагалась либо непосредственно в рабочем каталоге, либо в подкаталоге LIB системного каталога задачника (по умолчанию системным каталогом является каталог C:\Program Files\PT4).

В заголовке окна указывается имя текущей программной среды и номер ее версии. Приведенный рисунок соответствует настройке, при которой текущей средой является Free Pascal Lazarus версии 0.9. Если указана среда, отличная от требуемой, следует вызвать контекстное меню модуля PT4Load (щелкнув в его окне правой кнопкой мыши) и выбрать нужную среду из появившегося списка.

После ввода допустимого имени задания (в нашем случае Match4) кнопка «Загрузка» станет доступной. Нажатие этой кнопки (или клавиши [Enter]) приведет к автоматическому запуску выбранной среды программирования и загрузке в нее программы-заготовки для выполнения указанного задания.

В случае языка Pascal программа-заготовка будет иметь следующий вид:

    program Match4;
    uses PT4;
    begin
      Task('Match4');
    end.

Директива uses подключает к программе модуль PT4, содержащий дополнительные процедуры задачника; процедура Task обеспечивает инициализацию задания, имя которого указано в качестве ее параметра. Созданная программа уже может быть запущена на выполнение; для этого в среде Lazarus (как и в среде Delphi) достаточно нажать клавишу [F9]. В результате на экране появится окно задачника, содержащее формулировку задания, исходные данные и пример правильного решения:

Формулировка заданий содержит более пяти экранных строк, поэтому справа от соответствующего раздела окна указываются кнопки прокрутки. Прокрутку можно также выполнять клавишами со стрелками ([Up] или [Left] — прокрутка к началу, [Down] или [Right] — прокрутка к концу). Число, расположенное слева от раздела формулировки задания, указывает номер первой отображаемой на экране строки формулировки.

Раздел исходных данных содержит три элемента (две строки и одно целое число), снабженных комментариями. Исходные данные отображаются на экране желтым цветом, комментарии — серым. Следует обратить внимание на специальный комментарий, расположенный между исходными строками: это линейка, позволяющая быстро найти символ по его номеру. На линейке указываются позиции 1, 5, 10, 15 и т. д. (начиная с позиции 5, шаг равен 5). Позиция с указанным номером помечается символом «|» (вертикальная черта). Напомним, что в заданиях групп Match и Align предполагается, что символы строки нумеруются от 1.

Анализируя приведенные исходные данные, легко установить, что, начиная с позиции k = 27, строка T содержит 5 символов, совпадающих с соответствующими символами строки-образца P, после которых располагается символ, не совпадающий с шестым символом строки P. Таким образом, в данном случае надо вывести False, причем для проверки потребуется шесть сравнений символов (пять из которых выявят совпадение, а шестое — несовпадение символов).

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

Если в программе не выполняется ввод и вывод данных, то ее запуск считается ознакомительным, и проверка правильности решения не производится.

В окне задачника предусмотрен вызов справки, содержащей сведения о вариантах запуска программы с заданием, краткое описание процедур, предназначенных для ввода-вывода данных и отладки программы, а также список горячих клавиш. Для вызова окна справки достаточно нажать клавишу [F1] или кнопку «?», расположенную в правой части заголовка окна задачника.

Для завершения программы достаточно нажать кнопку «Выход» или клавишу [Esc] (можно также нажать клавишу [F9], т. е. ту же клавишу, которая используется для запуска программы).

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

    program Match4;
    uses PT4;
    var
      P, T: string;
      k: integer;
    begin
      Task('Match4');
      GetS(P);
      GetS(T);
      GetN(k);
    end.

Данные необходимо вводить в том порядке, в котором они перечислены в условии задачи. Порядок можно также определить по расположению исходных данных в соответствующем разделе окна задачника: ввод надо выполнять по строкам, перебирая данные в каждой экранной строке слева направо (как при чтении обычного текста). Для ввода строковых данных надо использовать процедуру GetS, для ввода символьных данных — процедуру GetC, а для ввода целочисленных данных — процедуру GetN (заметим, что в заданиях групп Match и Align исходные данные других типов не используются).

Запуск нового варианта программы уже не будет считаться ознакомительным, поскольку программа выполняет ввод исходных данных. Однако результаты не выводятся, поэтому информационная панель будет содержать сообщение об ошибке «Выведены не все результирующие данные»:

Следует обратить внимание на то, что при каждом запуске программы ей предлагается другой набор исходных данных, поэтому успешно выполнить задание можно, лишь запрограммировав алгоритм, правильно обрабатывающий любые допустимые исходные данные. В случае набора, приведенного на рисунке, программа должна была вывести значение True, так как строка T действительно содержит вхождение образца P, начиная с позиции 24. Для этой проверки требовалось выполнить 9 сравнений (т. е. сравнить все символы образца P с соответствующими символами текста T). Чтобы убедиться в этом, можно перейти на вкладку «Пример верного решения», щелкнув на ярлычке вкладки мышью или нажав клавиатурную комбинацию [Ctrl]+[Tab]:

Закрыв окно задачника и вернувшись в редактор среды Free Pascal Lazarus, реализуем требуемый алгоритм:

    program Match4;
    uses PT4;
    var
      P, T: string;
      Res: boolean;
      k, Cnt, i: integer;
    begin
      Task('Match4');
      GetS(P);
      GetS(T);
      GetN(k);
      Res := true;
      Cnt := 0;
      for i := 1 to Length(P) do
      begin
        Inc(Cnt);
        if P[i] <> T[k+i-1] then
        begin
          Res := false;
          break;
        end;
      end;
      PutB(Res);
      PutN(Cnt);
    end.

Результирующее логическое значение сохраняется в переменной Res типа boolean, а количество выполненных сравнений символов — в целочисленной переменной Cnt. Для вывода логического значения используется специальная процедура задачника PutB, а для вывода целочисленного значения — процедура PutN. При выполнении заданий групп Match и Align может также потребоваться выводить символьные и строковые данные; для этого предназначены процедуры PutC и PutS соответственно.

При запуске этого варианта решения задачник выведет сообщение об успешном тестовом испытании:

Из текста информационной панели можно определить, что для успешного выполнения задания необходимо, чтобы программа прошла 5 тестовых испытаний с различными исходными данными. Испытания должны быть проведены подряд; при неудачном испытании счетчик тестовых испытаний сбрасывается в 0, поэтому после исправления алгоритма серию испытаний придется начинать заново.

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

    program Match4;
    uses PT4;
    var
      P, T: string;
      k, Cnt, p0, t0: integer;
    begin
      Task('Match4');
      GetS(P);
      GetS(T);
      GetN(k);
      Cnt := 0;
      p0 := 1;
      t0 := k;
      while (p0 <= Length(P)) and (P[p0] = T[t0]) do
      begin
        Inc(p0);
        Inc(t0);
        Inc(Cnt);
      end;
      PutB(p0 = Length(P)+1);
      PutN(Cnt);
    end.

В данной программе используются переменные p0 и t0, содержащие текущие позиции строк P и T соответственно. Цикл while завершается, если либо p0 выходит за границу строки P, либо обнаруживается несовпадение символов в текущих позициях строк P и T. Заметим, что в случае выхода p0 за границу P сравнение P[p0] и T[t0] не производится. Это обеспечивается благодаря сокращенной схеме вычисления логических выражений: если первый операнд операции and является ложным (или первый операнд операции or является истинным), то второй операнд не вычисляется, так как уже по первому операнду можно определить значение данной операции (False для операции and, True для операции or).

При запуске данного варианта программы может быть получено сообщение об успешном тестовом испытании:

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

Сравнение с правильными результатами показывает, что было неверно определено количество сравнений (вместо числа 5 было выведено 4). Действительно, в варианте решения, использующем цикл while, счетчик Cnt увеличивается только при начале очередной итерации цикла (когда условие цикла возвращает значение True). Если же при вычислении второго операнда логического выражения будет обнаружено несовпадение символов, то цикл немедленно завершится, однако значение счетчика Cnt не увеличится; таким образом, итоговое значение Cnt окажется на 1 меньше требуемого. С другой стороны, когда выход из цикла происходит при достижении конца строки P, число сравнений символов определяется правильно, поскольку при вычислении условия в цикле уже первый операнд операции and оказывается ложным, и поэтому сравнение символов не выполняется.

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

Для исправления варианта программы с циклом while достаточно добавить перед выводом значения Cnt дополнительную проверку:

      if p0 <> Length(P)+1 then
        Inc(Cnt);

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

После пяти успешных тестовых запусков программы в окне задачника будет выведено сообщение о том, что задание выполнено:

С помощью программного модуля PT4Results можно просмотреть протокол выполнения задания. Для этого достаточно запустить ярлык Results, содержащийся в рабочем каталоге. Информация о ходе выполнения задания Match4 будет выглядеть примерно следующим образом:

    Match4   p28/04 12:17 Ознакомительный запуск.
    Match4   p28/04 12:22 Выведены не все результирующие данные.
    Match4   p28/04 12:31 Ошибочное решение.--2
    Match4   p28/04 12:35 Задание выполнено!

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

Примечание. Помимо сред Delphi и Lazarus задания на языке Pascal можно выполнять также в среде PascalABC.NET. По причине более глубокой интеграции задачника в среду PascalABC.NET (по сравнению с другими программными средами) процесс выполнения задания в среде PascalABC.NET имеет некоторые отличия. Во-первых, вызов программных модулей задачника PT4Load и PT4Result осуществляется непосредственно из самой программной среды (можно использовать клавиатурные комбинации [Ctrl]+[Shift]+[L] и [Ctrl]+[Shift]+[R] соответственно или кнопки на панели инструментов). Во-вторых, для ввода исходных данных и вывода результатов можно, наряду с уже описанными специальными процедурами групп Get и Put, использовать стандартные процедуры ввода-вывода языка Pascal Read–Write, причем с любым количеством параметров.

Для того чтобы группы заданий Match и Align были доступны для выполнения в среде PascalABC.NET, необходимо разместить библиотеки PT4Match.dll и PT4Align.dll либо в рабочем каталоге данной системы (по умолчанию это каталог C:\PABCWork.NET), либо в подкаталоге LIB каталога PT4, находящегося в системном каталоге PascalABC.NET (по умолчанию это каталог C:\Program Files\PascalABC.NET).

Разработка сайта:
М. Э. Абрамян, В. Н. Брагилевский

Последнее обновление:
01.01.2024