Ступенька мастерства: решаем задачи на обработку строк

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

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

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

Самостоятельная работа “Сравнение строк”

Цель работы — проверить:

• понимают ли учащиеся, как в Pascal происходит сравнение строк;

• навыки чтения (понимания) алгоритма, записанного в виде программы на Pascal.

Работа представлена в двух вариантах одинаковой сложности и рассчитана на 25–30 минут.

Вариант 1

1. Поставьте знак сравнения (>, <, =) между парами строк и объясните свой ответ.

'Процессор'____'Процесс'

'Balkon'___'balkon'

'balkon'____'balken'

'кошка '____'кошка'

'коТ'_____'кот'

2. Что будет выведено на экран в результате выполнения следующей программы:

var s: string;
         i, j: integer;
begin
    s := 'программа';
    for i := 1 to length (s) do
         begin
             for j := 1 to i - 1 do write(' ');
             writeln (s[i])
         end
end.

Вариант 2

1. Поставьте знак сравнения (>, <, =) между парами строк и объясните свой ответ.

'Компьютер'____'Комп'

'Stroka'____'stroka'

'кошка'____'кошка'

'кот'_____'kот'

'муха'____'слон'

2. Определите результат выполнения программы.

var s: string;
    i, k: integer;
begin
   s := 'абракадабра';
   k := 0;
   for i := 1 to length (s) do
       if s[i] = 'a' {if copy (s, i, 1) = 'a'}
          then k := k + 1;
   writeln (k: 5)
end.

Решение самостоятельной работы “Сравнение строк”

Вариант 1

1. Сравнение строк производится посимвольно слева направо до первого несовпадающего символа, и та строка считается большей, в которой код первого несовпадающего символа больше. Если две сравниваемые строки имеют различную длину, то недостающие символы короткой строки заменяются символами с кодом #0, другими словами, если две сравниваемые строки имеют различную длину, но совпадают вплоть до последнего символа более короткой строки, то короткая строка считается меньше.

'Процессор' > 'Процесс'. Строки совпадают вплоть до последнего символа второй, более короткой строки, поэтому вторая строка меньше.

'Balkon' < 'balkon'. В таблице кодировки заглавные буквы идут раньше строчных. Код первого символа первой строки 'B' меньше кода первого символа второй строки 'b', поэтому первая строка меньше.

'balkon' > 'balken'. Первые несовпадающие символы строк 'o' и 'e'. Код символа 'o' больше кода символа 'e', поэтому первая строка больше.

'кошка ' > 'кошка'. Дополняем вторую, более короткую строку символом с кодом #0. Первый несовпадающий символ первой строки “Пробел” имеет код #32, соответствующий символ второй строки имеет код #0, поэтому первая строка больше.

'коТ' < 'кот'. Первые несовпадающие символы строк 'Т' и 'т'. Заглавные буквы в таблице кодировки расположены раньше и имеют меньшие коды, поэтому 'Т' < 'т', и первая строка меньше.

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

Вариант 2

1. 'Компьютер' > 'Комп'. Строки совпадают вплоть до последнего символа второй, более короткой строки, поэтому вторая строка меньше.

'Stroka' < 'stroka'. В таблице кодировки заглавные буквы идут раньше строчных и имеют меньшие коды. Код первого символа первой строки 'S' меньше кода первого символа второй строки 's', поэтому первая строка меньше.

'кошка' = 'кошка'. Все символы строк совпадают, поэтому строки равны.

'кот' > 'kот'. Первые несовпадающие символы строк 'к' и 'k'. Символы латиницы находятся в первой половине таблицы кодировки, символы кириллицы — во второй. Код символа 'к' больше кода символа 'k', поэтому первая строка больше.

'муха' < 'слон'. Первые несовпадающие символы строк 'м' и 'с'. Код символа 'м' меньше кода символа 'с', поэтому первая строка меньше.

2. Программа выведет на экран число повторений символа 'а' в строке. Для данного примера это будет число 5.

Самостоятельная работа “Преобразование строки в число и наоборот”

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

• Str (x, st) — преобразует число x вещественного или целого типов в строку символов st. Например, для x = 13 результат выполнения процедуры Str(x,st) есть строка st = '13'.

• Val (st, x, k) — преобразует строку символов st в числовое значение целой или вещественной переменной x, которое определяется типом этой переменной. Параметр k = 0, если преобразование прошло успешно, иначе k будет равно номеру позиции первого символа в строке st, где обнаружен ошибочный символ (в том числе и пробел). Например, для st := '12345' результат выполнения процедуры Val (st, x, k) есть k = 0, x = 12345.

Цель работы — проверить:

• умеют ли учащиеся работать с процедурами Str и Val;

• навыки чтения (понимания) алгоритма, записанного в виде программы на Pascal.

Работа представлена в двух вариантах одинаковой сложности и рассчитана на 25–30 минут.

Вариант 1

1. Запишите результат выполнения следующих стандартных процедур:

Str (1234, st) __________________________

Str (452.567, st) ________________________

Str (4.52567е+2, st) _______________________

Val ('234.56', x, k) _______________________

Val ('12-45', x, k) _______________________

Val ('5.87c-5', x, k) ______________________

2. Определите результат выполнения программы.

var s: string;
    k: integer;
begin
     s := 'абракадабра'; k := length (s);
     if k mod 2 = 1 then delete (s, k div 2 + 1, 1)
end.

Вариант 2

1. Запишите результат выполнения следующих стандартных процедур:

Str (365.874, st) _______________________

Str (2.89784е+4, st) ______________________

Val ('9876', x, k) _______________________

Val ('1.0098e+6', y, k) ____________________

Val ('679-8', y, k) ______________________

Val ('2,567', y, k) ______________________

2. Определите результат выполнения программы:

var s: string;
    k, sum, d, i: integer;
begin
    sum := 0; s := '12r345ty';
    for i := 1 to length (s) do
        begin
          val (s[i], d, k);
          if k = 0 then sum := sum + d
        end;
writeln (sum:6)
end.

Решение самостоятельной работы
“Преобразование строки в число и наоборот”

Вариант 1

1.

Str (1234, st) Результат: st = '1234'

Str (452.567, st) Результат: st = '452.567'

Str (4.52567е+2, st)

Результат: st = '4.52567e+2'

Val ('234.56', x, k)

Результат: k = 0, x = 234.56

Val ('12-45', x, k)

Результат: k = 3, x = 0

{знак '-' в записи чисел может быть на первом месте или после признака экспоненты, символа 'e'}

Val ('5.87c-5', x, k)

Результат: k = 5, x = 0

{символ 'c' не должен встречаться в записи числа}

2. Если в строке нечетное число символов, то в ней удаляется средний символ. В строке 'абракадабра', указанной в задании, будет удален средний символ 'а', и получится строка 'абракдабра'. Строки с четным числом символов не изменяются.

Вариант 2

1.

Str (365.874, st) Результат: st = '365.874'

Str (2.89784е+4, st)

Результат: st = '2.89784е+4'

Val ('9876', x, k)

Результат: k = 0, x = 9876

Val ('1.0098e+6', y, k)

Результат: k = 0, y = 1.0098e+6

Val ('679-8', y, k)

Результат: k = 4, y = 0

{знак '-' в записи чисел может быть на первом месте или после признака экспоненты, символа 'e'}

Val ('2,567', y, k)

Результат: k = 2, y = 0

{разделителем целой и дробной части в записи действительного числа может быть только точка}

2. В процессе работы программы символы строки поочередно преобразуются процедурой val в число. Это преобразование успешно только для символов, изображающих десятичные цифры, при этом код ошибки (параметр k) принимает значение 0, а результат преобразования запоминается в переменной d. Для всех остальных символов процедура val формирует код ошибки в переменной k. Если преобразование символа строки в число d произошло успешно k = 0), то это число добавляется к сумме. Таким образом, в результате работы программы подсчитывается сумма цифр, входящих в строку. Для строки, указанной в задании, это будет число 15.

1. Технические задачи

К базовым техническим задачам на обработку строк мы относим следующие задачи:

• создание новой строки через операцию конкатенации;

• отслеживание длины слова и максимальной длины строки;

• формирование строки в обратном порядке;

• использование стандартных процедур и функций для преобразования строк;

• использование процедур Val и Str для преобразования символьной информации в числовую и обратно;

• замена символов в строке.

Создание новой строки через операцию конкатенации

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

Пример. На ввод подается последовательность слов. Ввод каждого слова заканчивается нажатием клавиши .

mama

Papa

sun

Reteat

'' (пустое слово, вводится нажатием клавиши )

Выходная строка: mama.Papa sun.Repeat

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

Const c = #0;
var tmp, st: string;
begin
   st := '';
   readln(tmp); tmp := c + tmp;
   while tmp <> '' do
     begin
       if tmp[1] = c
         then st := st + tmp
          else if tmp[1] in ['A' .. 'Z']
                  then st := st + '. '+ tmp
                  else st := st + ' ' + tmp;
                 {обратим внимание, что операторы присваивания можно
                  записать через стандартную в Pascal функцию concat,
                  а именно str := concat(str, '. ', tmp) и
                  str := concat(str, ' ', tmp))}
         readln(tmp);
    end;
delete(st,1,1);
{удаляем барьерный элемент}
writeln(st);
readln
end.

Отслеживание длины слова и максимальной
длины строки

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

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

while tmp <> '' do
  begin
    if length(str) + length(tmp) <= 255
      then
         if tmp[1] = c
           then st := st + tmp
           else if tmp[1] in ['A' .. 'Z']
                  then st := st + '. '+ tmp
                  else st := st + ' ' + tmp
      else writeln('Слово уже не может быть записано в строку');
    readln(tmp)
   end;

2. Игра “Баше наоборот”. Написать игру для двух игроков, которые пишут в строку не более k символов за один ход. Выигрывает тот, кто выполнил запись в строку последним. Строка содержит n символов.

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

Игра Баше относится к играм с выигрышной стратегией. Исход игры определен после первого хода, если партнеры не делают ошибок. Выигрышный алгоритм игры Баше для первого игрока легко построить, если рассуждать с “конца”, то есть рассмотреть сначала позицию перед последним ходом. Для выигрыша надо оставить противнику перед его последним ходом k + 1 предмет. Тогда, сколько бы он ни взял предметов (больше k брать нельзя), своим ходом вы забираете последний предмет. Поэтому перед предпоследним ходом надо оставить на столе 2(k + 1) предметов. В этом случае на любой ход противника можно ответить так, что в куче останется k + 1 предмет.

Таким образом, в игре есть ряд ключевых позиций – k + 1, 2(k + 1), 3(k + 1) предметов и т.д., создав которые первый игрок выигрывает. Если начальная позиция не ключевая, то нужно сразу же получить ключевую позицию, взяв “лишние” предметы, а затем уверенно доводить игру до победы.

Игру “Баше наоборот” можно запрограммировать, используя в качестве “кучи” предметов переменную типа string. Приведем программу для нескольких игроков.

const
  n = 100; {количество символов в строке}
  k = 10; {количество символов, которые можно вписать за один ход}
  m = 5; {количество игроков}
var st, tmp: string;
    i, p: integer;
begin
    st := '';
    i := 1;
    while length(st) < n do
       begin
         p := n - length(st);
         writeln('Ходит игрок', i);
         writeln('Осталось ', p, ' символов);
         Readln(tmp);
         While (length(tmp) > k) or
               (length(tmp) < 1) or
               (length(tmp) > p) do
         begin
             writeln('введите строку не более ', k, 'символов');
             readln(tmp)
         end;
           st := st + tmp;
           if length(st) = n
              then writeln ('УРА! Игрок ', i, 'выиграл');
           i := i mod m + 1 {чередование игроков}
      end
end.

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

const
  n = 100; {количество символов в строке}
  k = 10; {количество символов, которые можно вписать за один ход}
  m = 2;
var
  st, tmp: string;
  i, p, j: integer;
begin
  st := '';
  i := 1;
  while length(st) < n do
    begin
      p := n - length(st);
      if i = 1 then
          begin
            tmp := '';
            p := (n – length(st)) mod (k + 1);
            for j := 1 to p do tmp := tmp + '1';
            writeln('{Ход компьютера - ', tmp)
          end;
      if i = 2 then
          begin
            writeln('Ходит игрок', i);
            writeln('Осталось ', p, ' символов);
            readln(tmp);
            while (length(tmp) > k) or
                  (length(tmp) < 1) or
                  (length(tmp) > p) do
            begin
              writeln('Введите строку не более ',k, 'символов');
              readln(tmp)
            end
          end;
      st := st + tmp;
      if length(st) = n then writeln ('УРА! Игрок ', i, 'выиграл');
      i := i mod m + 1 {чередование игроков}
    end
end.

Формирование строки в обратном порядке

3. Сформировать строку, все символы которой идут в обратном порядке относительно исходной.

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

var st, newst: string;
    i, p: integer;
begin
  readln(st);
  p := length(st);
  newst := '';
  for i := p downto 1 do newst := newst + st[i];
  writeln(newst)
end.

Второй способ позволяет нам не заводить дополнительную переменную типа string, а перевернуть строку внутри себя.

var st: string;
    i, p: integer;
    tmp: char;
begin
   readln(st);
   p := length(st);
   for i := 1 to p div 2 do
      begin
        tmp := st[i];
        st[i] := st[p – i + 1];
        st[p – i + 1] := tmp
      end;
     writeln(st)
end.

Использование стандартных процедур и функций
для работы со строками

4. Удалить среднюю букву при нечетной длине строки и две средние буквы при четной длине строки.

Решение

var s:string; k,m:integer;
begin
    writeln('Введите строку');
    readln(s);
    k := length(s); m := k div 2;
    if k mod 2 = 1
      then delete (s,m + 1,1)
      else delete (s,m,2);
    writeln('Полученная строка');
    writeln (s);
end.

5. Переписать в одну строку часть исходной строки до заданного слова, а в другую строку все — после заданного слова.

Решение

var st, podst, prest, postst: string;
    k, p, p1: integer;
begin
  writeln('Введите строку');
  readln(st);
  writeln('Введите искомое слово');
  readln(podst);
  k := pos(podst, st);
  p := length(st);
  p1 := length(podst);
  if k = 0
    then writeln ('Искомое слово не найдено')
    else
      begin
        prest := copy(st, 1, k - 1);
        postst := copy(st, k + p1, p – k – p1 + 1);
      end;
  if prest <> '' then writeln('Строка до искомого слова: ', prest);
  if postst <> '' then writeln('Строка после искомого слова: ', postst)
end.

Использование процедур Val и Str

6. Подсчитать сумму цифр, встречающихся в строке.

Решение

var s:string; k,x,n,i,sum:integer;
begin
    writeln('Введите строку');
    readln(s);
    n := length(s); sum := 0;
    for i := 1 to n do
       begin
         val (s[i],x,k);
         if k = 0 then sum := sum + x;
       end;
    writeln ('Сумма = ',sum:5);|
end.

7. Дана строка цифр без пробелов. Четные цифры записать в одну строку, а нечетные — в другую. Вывести исходную и полученные строки.

Решение

var s, s1, s2:string;
    i, x, k: integer;
begin
  readln(s);
  s1 := '';s2 := '';
  i := 1;
  while i <= length(s) do
    begin
      val(s[i], x, k);
      if odd(x) then s1 := s1 + s[i]
                else s2 := s2 + s[i];
      i := i + 1;
    end;
   writeln(s1);
   writeln(s2)
end.

8. Оператор последовательно через пробел вводит сумму заработка сотрудников своей организации за последний месяц. В сумме заработка при вводе рубли от копеек отделяются точкой. Сформировать строку следующего содержания: “Сумма подоходного налога организации составила __ рублей”.

Пример. Входные данные: 5040, 10289, 10073.80.

Результат: Сумма подоходного налога организации составила 3302.36 рублей.

Решение

var st, st1, tmp: string;
    code, i: integer;
    zp, sum: real;
begin
  writeln('Введите заработную плату всех сотрудников,
           отделяя одну сумму от другой пробелом');
  readln(st1);
  st := st1; {исходные данные портить не рекомендуется}
  sum := 0;
  while length(st) > 0 do
    begin
      i := pos(' ', st);
      if i <> 0 then tmp := copy(st, 1, i - 1)
                else begin tmp := st;
      i := length(tmp) end;
      val(tmp, zp, code);
      if code = 0 then sum := sum + zp;
           {суммируем, если не было ошибки}
      delete(st, 1, i)
    end;
    str((sum*0.13):10:2, tmp);
    tmp := 'Сумма подоходного налога организации составила ' + tmp
            + ' рублей';
    writeln(tmp)
end.

Замена символов в строке

9. У Леонида Пантелеева в рассказе “Буква «ты»” девочка Иринушка думала, что буква “я” читается как “ты”. Во входной строке записаны слова в произношении Иринушки. Замените неправильный слог “ты” на правильный слог “я”.

Решение. Заметим, что в данной задаче более длинное слово заменяется более коротким, поэтому проверку на выход за “длину” строки проводить не нужно, исключение может составить только первая вставка.

var str, str1, str2: string;
    m, i: byte;
begin
   str := 'тыблоко, тыхта, тыстреб, тыма, тырмарка, тыкорь, тызык';
   str1 := 'ты';
   str2 := 'я';
   m := length(str1);
   while pos(str1, str) <> 0 do
      begin
        insert(str2, str, pos(str1, str));
        delete(str, pos(str1, str), m)
      end;
    writeln(str)
end.

2. Базовые алгоритмы

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

· выделение очередного слова в строке. Слово может заканчиваться “пробелом” или знаком препинания;

• определение длины слова;

• определение самого длинного слова в строке;

• форматирование строки (по ширине или по центру);

• удаление лишних пробелов между словами;

• подсчет частоты встречаемости символов в строке.

Договоримся считать словом любую последовательность символов, ограниченную с двух сторон одним из элементов следующего множества: {начало строки, конец строки, пробел, “.”, “,”, “;”, “:”, “!”, “?”}. Для более “читаемого” решения будем в программах использовать множество символов [“.”, “,”, “;”, “:”, “!”, “?”, “ ”].

Выделение очередного слова в строке

10. Слова в строке разделены пробелами, найти самое длинное слово.

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

Кроме того, использование метода барьерных элементов дает возможность написать более эффективную программу.

var s, s1, s_max: string;
    a, i: integer;
begin
  write('st == ');
  readln (s);
  s := s + ' '; {барьерный элемент}
  i := 1;
  a := length(s);
  s_max := '';
  repeat
    if s[i] <> ' ' then
      begin
        s1 := '';
        while ([i] <> ' ' do
          begin
            s1 := s1 + s[i];
            i := i + 1;
          end;
        if length(s1) > length(s_max) then s_max := s1;
       end
                   else i := i + 1
  until i >= length(s);
  writeln('long word=',s_max)
end.

11. Посчитать количество слов в строке. Словом считается любая последовательность латинских букв, которая заканчивается пробелом или знаком препинания или стоит в конце строки.

Решение. Для написания эффективной программы (во внутреннем цикле While не будет лишней проверки на конец строки) воспользуемся методом “барьерных элементов” и добавим к исходной строке лишний пробел. В результате все слова строки будут оканчиваться символом из множества Letters.

Const Letters: Set Of Char = [' ','.',',','?','!',':',';'];
var p, q, kol: byte;
    s : string;
begin
  readln(s);
  s := s + ' ';
  kol := 0;
  p := 1; {Проверять с 1-го символа в строке}
  while p <= length(s) do {Поиск по строке}
    begin
      q := p; { Запомнить позицию p }
      while not (s[p] in Letters) do inc(p);
      {Пока очередной символ является буквой, увеличивать позицию p}
      if q <> p then
       {позиция p сдвинута относительно q, значит, найдено слово}
       inc(kol);
      inc (p)
      {передвинув позицию p, продолжить поиск по строке}
    end;
  writeln(kol)
end.

12. Вывести все слова строки на экран в столбик. Словом в задаче будем считать любую последовательность латинских букв. Например, строка asd33end содержит два слова — asd и end. А строка 123456 не содержит ни одного слова.

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

Const Letters: Set Of Char = ['A'..'Z','a'..'z'];
var p,q: byte;
    s, sc : string;
begin
  readln(s);
  p := 1; {Проверять с 1-го символа в строке}
  while p <= length(s) do { Поиск по строке}
    begin
      q := p; {Запомнить позицию p}
      while (s[p] in Letters) do inc(p);
      {Пока очередной символ является буквой, увеличивать позицию p}
      if q <> p then
        {позиция p сдвинута относительно q, значит, найдено слово}
        begin
          sc := copy (s, q, p - q);
          {Вырезать слово}
          writeln (sc) {и вывести его на экран}
        end;
        inc (p)
        {передвинув позицию p, продолжить поиск по строке}
    end
end.

Определение длины слова

13. Дана строка. Определить длину самого длинного слова.

Решение. Под словом будем понимать любую последовательность латинских букв, которая заканчивается пробелом или знаком препинания или стоит в конце строки.

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

Const Letters: Set Of Char = [' ','.',',','?','!',':',';'];
var p, q, max_dl, dl: byte;
    s: string;
begin
  readln(s);
  s := s + ' ';
  max_dl := 0;
  p := 1; {Проверять с 1-го символа в строке}
  while p <= length(s) do { Поиск по строке}
    begin
      q := p; { Запомнить позицию p }
      dl := 0;
      while not (s[p] in Letters) do
        begin
          inc(p);
          {Пока очередной символ не является знаком препинания или
           пробелом,    увеличивать позицию p}
          inc(dl)
        end;
       if q <> p then
         {позиция p сдвинута относительно q, значит, найдено слово}
         if dl > max_dl then max_dl := dl;
         inc (p)
         {передвинув позицию p, продолжить поиск по строке}
   end;
   writeln(max_dl)
end.

Удаление лишних пробелов между словами

Как было отмечено в начале статьи, строку можно рассматривать как обыкновенный массив, состоящий из элементов типа char. Явным преимуществом строковых типов перед массивами является то, что некоторые алгоритмы обработки уже реализованы в виде стандартных процедур и функций. Одной из таких функций является функция pos(st1, st).

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

Решение. Очевидно, что эту задачу можно решить, пройдя всю строку и последовательно рассмотрев каждый элемент.

var st: string;
    i, n: integer;
begin
  readln(st);
  n := length(st);
  i := 1;
  while i < n do
    begin
      if (st[i] = ' ') and (st[i + 1] = ' ')
        then begin
               delete(st, i, 1);
               dec(i)
             end;
      inc(i)
    end
end.

Однако если воспользоваться уже реализованной функцией поиска подстроки в строке, то программа становится значительно короче и нагляднее. Воспользуемся функцией pos(st1, st), которая возвращает первое вхождение подстроки в строку.

var st: string;
begin
  readln(st);
  while pos(' ', st) <> 0 do
  delete(st, pos(' ', st), 1)
end.

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

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

Форматирование строки

16. Ученик ввел строку, в которой было не менее двух слов. Растянуть строку так, чтобы она занимала всю ширину экрана (80 символов). Сделать это равномерным добавлением пробелов между словами, то есть количество пробелов между разными словами не должно отличаться более чем на единицу.

Решение

const n = 80;
var st: string;
    k, i, gr, blanck, need, bl1, bl2, j: integer;
    b: boolean;
begin
  readln(st);
  blanck := 0;
  gr := 0;
  i := 1;
  b := false;
  {флаг распознавания группы пробелов}
  while i <= length(st) do
    begin
      while (st[i] <> ' ') and (i <= length(st)) do inc(i);
      while (st[i] = ' ') and (i <= length(st)) do
         begin
           inc(i);
           inc(blanck);
           {подсчет количества пробелов в строке}
           b := true
         end;
      if b then inc(gr);
      {подсчет количества групп пробелов между словами}
      b := false
     end;
  i := 1;
  need := n - length(st);
  {количество пробелов, которые нужно добавить}
  bl1 := (need + blanck) div gr;
  {количество пробелов, которые должны быть в одной группе}
  bl2 := (need + blanck) mod gr;
  {количество групп, в которых должно быть на один пробел больше,
      чем в остальных}
  gr := 0;
  while i < n do
    begin
      while st[i] <> ' ' do inc(i);
      blanck := 0;
      while st[i] = ' ' do begin inc(i);
      inc(blanck)
    end;
  inc(gr);
  if gr <= bl2 then j := bl1 – blanck + 1
               else j := bl1 – blanck;
  {количество пробелов, добавляемых в очередную группу}
  for k := 1 to j do
     begin
       insert(' ', st, i);
       {добавляем пробелы до нужного количества}
       inc(i)
     end;
  if j < 0 then
         begin
           delete (st, i - abs(j), abs(j));
           {удаляем лишние пробелы}
           i := i - abs(j)
         end
   end;
   writeln(st)
end.

17. Написать программу, которая форматирует строку по центру. Например, при длине строки 20 символов строка “while a < b do” должна быть превращена в строку “___while a < b do___” (для наглядности пробелы заменены символом подчеркивания).

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

Частота встречаемости символов в строке

В общем случае задачи на подсчет частоты встречаемости символов в тексте решаются методом введения дополнительных данных (метод подсчета). Примеры таких задач приведены в статье “Ступеньки понимания: решаем задачи на массивы”, газета “Информатика” № 7/2008.

17. Подсчитать количество цифр в строке.

Решение

var s:string; q:char; kol,i:integer;
begin
   write('Введите строку');
   readln(s);
   kol := 0;
   for i := 1 to length(s) do
       if s[i] in ['0' .. '9'] then kol := kol + 1;
   writeln(kol:3);
end.

3. Задачи для самостоятельного решения

18. Слова в строке разделяются пробелами. Зашифровать текст таким образом, чтобы каждое слово текста было записано в обратном порядке.

Решение. В решении задачи используется метод барьерных элементов.

var s,s1:string;
    t: char;
    a, i, j, b, p: integer;
begin
  write('st ==> ');
  readln(s);
  s := s + ' '; {Добавили барьерный элемент}
  i := 1; a := length(s);
  repeat
    if s[i] <> ' ' then
      begin
        s1 := ''; p := i;
        while s[i] <> ' ' do
          begin
            s1 := s1 + s[i];
            i := i + 1;
          end;
        b := length(s1);
        for j := 1 to b div 2 do
           begin
             t := s1[j]; s1[j] := s1[b - j + 1];
             s1[b – j + 1] := t
           end;
        delete(s, p, b);
        insert(s1, s, p);
      end
          else i := i + 1
   until i >= length(s);
   writeln(s)
end.

19. В строке записано предложение, слова в котором разделяются пробелами. Сформировать новую строку, в которой слова исходной строки будут записаны в обратном порядке. Например, из строки МАМА МЫЛА РАМУ сделать РАМУ МЫЛА МАМА.

Решение. Алгоритм решения этой задачи состоит в последовательном выделении очередного слова исходной строки и дописывании его в начало новой строки через пробел.

var st, st_new, temp: string [80];
    p, i: integer;
begin
  readln (st);
  st := st + ' ';
  i := 1;
  st_new := '';
  while i <= length(st) do
    begin
      while st[i] = ' ' do inc(i);
      {пропуск пробелов}
      p := i;
      while st[i] <> ' ' do inc(i);
      st_new := temp + ' ' + st_new
    end;
    writeln(st_new)
end.

20. Проверить, является ли строка палиндромом.

Решение

var st: string [80]; f: boolean;
    i ,dl: integer;
begin
  readln (st);
  f := true;
  i := 1;
  dl := length(s);
   while (i <= dl) and f do
     begin
       f := st[i] = s[dl – i + 1];
       {if st[i] <> s[dl – i + 1] then f := false;}
       inc(i)
     end;
   writeln(f)
end.

21. (Палиндром, газета “Информатика” № 1/2008). Дана строка, состоящая из заглавных латинских букв (не обязательно различных). Требуется написать программу, которая из данных букв составит палиндром наибольшей длины, а если таких палиндромов несколько, то первый в алфавитном порядке. Для составления палиндромов можно переставлять буквы, а также удалять некоторые буквы.

Напомним, что палиндром – это строка, которая читается одинаково как справа налево, так и слева направо.

Решение задачи приведено в этом же номере газеты.

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

Пример. Входная строка: 22 + 8/2.

Результат: 15 (а не 26!).

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

var s, tmp: string;
    i, code, dl: integer;
    res, op1: real;
    zn: char;
procedure op(st: string; var i: integer; var tmp: string);
var b: boolean;
begin {данная процедура определяет операнд}
  tmp := ''; {инициализация пустой строки}
  n := length(st);
  b := true;
  while (st[i] in ['0'..'9', '+', '-', 'E', 'e', '.'])
           and (i <= n) and b do
           {определим операнд}
     begin
       if (st[i] in ['+', '-']) and
           (st[i - 1] in ['0' .. '9'])
                 then b := false;
       tmp := tmp + st[i];
       inc(i)
     end;
  if (length(tmp) > 1) and
      (st[i - 1] in ['+', '-']) then
     begin
       tmp := copy(tmp,1,length(tmp) - 1);
       dec(i)
     end
   end;
  {в том случае, если школьники не умеют работать с процедурой,
    ее текст можно записать два раза непосредственно в программе.
   Тогда в условии задачи нужно поставить ограничение на количество
    операндов в записи выражения}
begin
  readln(s);
  i := 1; op1 := 0;
  code := 0;
  dl := length(s);
  op(str, i, tmp);
  val(tmp, res, code);
  while (i <= dl) and (code = 0) do
    begin
      zn := s[i];
      inc(i);
      op(s, i, tmp);
      val(tmp,op1, code);
      if code = 0 then
         case zn of
         '+': res := res + op1;
         '-': res := res - op1;
         '*': res := res * op1;
         '/': res := res / op1;
         end
    end;
  if code = 0 then writeln(res: 10: 5)
  mm          else writeln('ошибка в записи выражения')
end.

23. Проверить, входит ли в строку слово, введенное с клавиатуры. Строчные и заглавные буквы не различаются.

Пример: Слово “камыш” входит в строку “Шумел камыш, деревья гнулись”, но не входит в строку “камышовый кот”.

24. Дана строка латинского текста. Составить программу шифровки текста, пользуясь простым правилом: каждая буква заменяется на следующую по алфавиту, при этом буква 'z' заменяется на букву 'a'.

Решение

var st: string; f: boolean;
    i ,i:integer;
begin
  readln (st);
  for i := 1 to length(st) do
    if st[i] <> 'z' then st[i] := succ(st[i])
              else st[i] := 'a';
   writeln (st);
end.

25. Шифр Цезаря реализует кодирование фразы путем “сдвига” всех букв фразы на определенное число k (в оригинальном шифре Цезаря k = 3). Если буква кодируемой фразы имеет в алфавите позицию j, то она в “шифровке” будет заменяться буквой, находящейся в алфавите на позиции j + k.

Напишите программу, которая кодирует текст шифром Цезаря. Исходный текст составлен из латинских букв со стандартным следованием букв в алфавите. Считаем, что пробел стоит в алфавите на нулевом месте. Для шифрования используем циклический сдвиг вправо относительно номера буквы в алфавите. Число k вводится с клавиатуры.

Пример. Пусть k = 3, исходная фраза “i remember that september”. Результат шифрования: Lcuhphpehucwkdwcvhswhpehu.

26. Вывести на экран таблицу умножения в шестнадцатеричной системе счисления в виде следующей таблицы:

27. Введена строка. Проверить, является ли она правильным идентификатором в Pascal. Идентификатор считается правильным, если он состоит только из латинских букв, цифр и знака “_” и не начинается с цифры.

28. Вводятся 2 строки. Найти слово минимальной длины, которое есть в обеих строках.

Решение. Будем решать задачу в предположении длины строк не более 80. Воспользуемся методом подсчета: в дополнительных массивах count_a и count_b (размерностью [1..80]) будем накапливать количество однобуквенных, двухбуквенных, трехбуквенных и т.д. слов в строке a и b соответственно.

Затем для каждой пары count_a[i] <> 0 и count_b[i] <> 0 сравним до первого совпадения все i-буквенные слова строки a и b. Если нашлось совпадающее слово, то оно и будет искомым решением, в противном случае увеличиваем i на единицу и повторяем предыдущий шаг.

29. Дополнить строку до минимального палиндрома.

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

Решение

var kol, i: integer;
    s: string;
begin
  readln (s);
  kol := 0; i := 1;
  while i < length (s) do
   if s[i] = '(' then
      begin
        kol := kol + 1;
        while s[i] <> ')' do delete (s, i, 1);
        delete (s, i, 1)
      end
       else i := i + 1;
   writeln ('Всего было ', kol, 'скобок');
   writeln ('После удаления получена строка ', s)
end.