Как найти строки информатика

Умение решать задачи – такое же
практическое искусство, как умение плавать или
бегать.
Ему можно научиться только путем подражания или
упражнения.
Д. Пойа

В статье представлены задачи различных типов:
подсчет частоты появления символа в строке;
поиск подстроки в строке, замена найденной
подстроки на другую строку; выделение слов из
строки, нахождение числа слов в строке,
нахождение минимальной (максимальной) длины
слова в строке; сравнение и сортировка строк и др.

Все приведенные программы написаны на языке
программирования PascalABC.

Задача 1.

С помощью функции копирования и операции
конкатенации составить из частей слова
“информатика” слово “торт”.

program novslovo;

uses crt;

var s, ns: string;

begin

     s:=’информатика’;

     ns:=copy(s,8,1)+copy(s,4,2)+copy(s,8,1);

     writeln(ns);

end.

Задача 2.

Подсчитать, сколько раз среди символов
заданной строки встречается буква “а”.

program kolbukv_a;

uses crt;

var s: string;

      i, k: integer;

begin

     write(‘Введите строку: ‘);

     readln(s);

     k:=0;

     for i:=1 to length(s) do

          if s[i]=’а’ then k:=k+1;

     writeln(‘Буква “а” встречается ‘, k, ‘
раз(а)’);

end.

Задача 3.

Найти долю пробелов в строке A.

program dolya;

uses crt;

var a: string;

     i, k: integer;

     d: real;

begin

     write(‘Введите строку: ‘);

     readln(a);

     k:=0;

     for i:=1 to length(a) do

          if a[i]=’ ‘ then k:=k+1;

     d:=k/length(a);

     writeln(‘Доля пробелов в строке ‘, d);

end.

Задача 4.

Заменить все буквы “а” на буквы “б” в
заданной строке.

program zamena_ab;

uses crt;

var s: string;

      i: integer;

begin

     write(‘Введите строку: ‘);

     readln(s);

     for i:=1 to length(s) do

          if s[i]=’а’ then
s[i]:=’б’;

     writeln(s);

end.

Задача 5.

Из заданной строки получить новую, повторив
каждый символ дважды.

program udvsimv;

uses crt;

var s, ns: string;

      i, j, l: integer;

begin

     write(‘Введите строку: ‘);

     readln(s);

     l:=length(s);

     j:=1;

     for i:=1 to l do begin

          ns[j]:=s[i];

          ns[j+1]:=s[i];

          j:=j+2;

     end;

     for i:=1 to 2*l do write(ns[i]);

end.

Задача 6.

Дано слово. Вывести слово, содержащее те же
символы, но расположенные в обратном порядке.

program slovonaoborot;

uses crt;

var s: string;

      i: integer;

begin

     write(‘Введите слово: ‘);

     readln(s);

     for i:=length(s) downto 1 do write(s[i]);

end.

Задача 7.

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

program palindrom;

uses crt;

var s: string;

      i, l, m, k: integer;

begin

     write(‘Введите слово: ‘);

     readln(s);

     l:=length(s);

     m:=l div 2;

     k:=0;

     for i:=1 to m do

          if s[i]<>s[l+1-i]
then k:=1;

     if k=1 then writeln(‘Слово “’, s, ‘” не
палиндром’)

                else
writeln(‘Слово “’, s, ‘” палиндром’);

end.

Задача 8.

Строка X состоит из нескольких предложений,
каждое из которых кончается точкой,
восклицательным или вопросительным знаком.
Определить количество предложений в строке X.

program kolpredl;

uses crt;

var x: string;

      i, k: integer;

begin

     write(‘Введите строку: ‘);

     readln(x);

     k:=0;

     for i:=1 to length(x) do

          if (x[i]=’.’) or (x[i]=’!’)
or (x[i]=’?’) then k:=k+1;

     writeln(‘В строке ‘, k, ‘ предложений’);

end.

Задача 9.

Проверить правильность расстановки скобок в
формуле. Расстановку считать правильной, если
число открывающих скобок равно числу
закрывающих скобок.

program skobki;

uses crt;

var f: string;

      i, ko, kz: integer;

begin

     write(‘Введите формулу: ‘);

     readln(f);

     ko:=0; kz:=0;

     for i:=1 to length(f) do begin

          if f[i]='(‘ then ko:=ko+1;

          if f[i]=’)’ then kz:=kz+1;

     end;

     if ko=kz then writeln(‘Правильная
расстановка скобок’)

                    else
writeln(‘Неправильная расстановка скобок’);

end.

Задача 10.

Проверить правильность расстановки скобок в
формуле. Учитывать порядок скобок.

Способ 1

program skobki_1;

uses crt;

var f: string;

      i, k: integer;

begin

     write(‘Введите формулу: ‘);

     readln(f);

     i:=1; k:=0;

     repeat

          if f[i]='(‘ then k:=k+1;

          if f[i]=’)’ then k:=k-1;

          i:=i+1;

     until (k<0) or (i>length(f));

     if k=0 then writeln(‘Правильная
расстановка скобок’)

                else
writeln(‘Неправильная расстановка скобок’);

end.

Способ 2

program skobki_2;

uses crt;

var f: string;

      i, k, z: integer;

begin

     write(‘Введите формулу: ‘);

     readln(f);

     k:=0; z:=0;

     for i:=1 to length(f) do begin

          if f[i]='(‘ then k:=k+1;

          if f[i]=’)’ then k:=k-1;

          if k<0 then z:=1;

     end;

     if (k=0) and (z=0) then

          writeln(‘Правильная
расстановка скобок’)

          else

          writeln(‘Неправильная
расстановка скобок’);

end.

Задача 11.

В заданной строке подсчитать количество букв
латинского алфавита.

program kolbukvlat;

uses crt;

var s: string;

      i, k: integer;

begin

     write(‘Введите строку символов: ‘);

     readln(s);

     k:=0;

     for i:=1 to length(s) do

          if (s[i]>=’A’) and
(s[i]<=’Z’) or (s[i]>=’a’) and (s[i]<=’z’) then

               k:=k+1;

     writeln(‘В строке “’, s, ‘” ‘, k, ‘
латинских букв’);

end.

Задача 12.

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

program kolcifr;

uses crt;

var s, c: string;

      i, j, k: integer;

begin

     write(‘Введите строку символов: ‘);

     readln(s);

     c:=’0123456789′;

     k:=0;

     for i:=1 to length(s) do

          for j:=1 to 10 do

               if
s[i]=c[j] then k:=k+1;

     writeln(‘В строке “’, s, ‘” ‘, k, ‘ цифр’);

end.

Задача 13.

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

program udalprobel;

uses crt;

var s, ns: string;

      i, k: integer;

begin

     write(‘Введите строку: ‘);

     readln(s);

     k:=0;

     for i:=1 to length(s) do

          if s[i]<>’ ‘ then
begin

               k:=k+1;

               ns[k]:=s[i];

          end;

     for i:=1 to k do write(ns[i]);

end.

Задача 14.

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

program udalbukv;

uses crt;

var s, ns: string;

      i, k: integer;

begin

     write(‘Введите строку: ‘);

     readln(s);

     k:=0;

     for i:=1 to length(s) do

          if (s[i]<‘A’) or
(s[i]>’Z’) and (s[i]<‘a’) or (s[i]>’z’) then begin

               k:=k+1;

               ns[k]:=s[i];

          end;

     for i:=1 to k do write(ns[i]);

end.

Задача 15.

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

program kolfragm;

uses crt;

var t, f: string;

      i, k: integer;

begin

     write(‘Введите текст: ‘);

     readln(t);

     write(‘Введите фрагмент: ‘);

     readln(f);

     k:=0;

     for i:=1 to length(t) do

          if copy(t, i, length(f))=f
then k:=k+1;

     writeln(‘Фрагмент “’, f, ‘” встречается
в тексте ‘, k, ‘ раз(а)’);

end.

Задача 16.

Проверить, является ли частью данного слова
слово “сок”. Ответ должен быть “да” или “нет”.

program chastslova;

uses crt;

var s: string;

     i, f: integer;

begin

     write(‘Введите слово: ‘);

     readln(s);

     f:=0;

     for i:=1 to length(s) do

          if copy(s, i, 3)=’сок’
then f:=1;

     if f=1 then writeln(‘да’)

               else
writeln(‘нет’);

end.

Задача 17.

В заданной строке всюду “1999” заменить на
“2000”.

program zamena_1999;

uses crt;

var a: string;

      i: integer;

begin

     write(‘Введите строку: ‘);

     readln(a);

     for i:=1 to length(a) do

          if copy(a,i,4)=’1999′ then
begin

               delete(a,
i, 4);

               insert(‘2000’,
a, i);

          end;

     writeln(a);

end.

Задача 18.

Ввести с клавиатуры строку, содержащую фамилию,
имя и отчество. Слова в строке разделять одним
пробелом. Получить новую строку, содержащую
фамилию и инициалы.

program fio;

uses crt;

var s, f, i, o: string;

      p: integer;

begin

     write(‘Введите фамилию, имя и
отчество: ‘);

     readln(s);

     p:=pos(‘ ‘, s);

     f:=copy(s, 1, p-1);

     delete(s, 1, p);

     p:=pos(‘ ‘, s);

     i:=copy(s, 1, 1);

     delete(s, 1, p);

     o:=copy(s, 1, 1);

     s:=f+’ ‘+i+’.’+o+’.’;

     writeln(s);

end.

Задача 19.

Подсчитать количество слов в исходной строке.
Слова считать отделенными друг от друга одним
пробелом.

program kolslov;

uses crt;

var s: string;

      i, k: integer;

begin

     write(‘Введите строку: ‘);

     readln(s);

     s:=s+’ ‘;

     k:=0;

     for i:=1 to length(s) do

          if s[i]=’ ‘ then k:=k+1;

     writeln(‘Количество слов в строке ‘, k);

end.

Задача 20.

Подсчитать количество слов в исходной строке.
Слова считать отделенными друг от друга одним
или несколькими пробелами.

program kolslov;

uses crt;

var s: string;

      i, k, f: integer;

begin

     write(‘Введите строку: ‘);

     readln(s);

     s:=s+’ ‘;

     k:=0;

     f:=0;

     for i:=1 to length(s) do begin

          if (s[i]<>’ ‘) and
(f=0) then f:=1;

          if (s[i]=’ ‘) and (f=1)
then begin

               f:=0;

               k:=k+1;

          end;

     end;

     writeln(‘Количество слов в строке ‘, k);

end.

Задача 21.

Проверить цепочку слов на совпадение первой
буквы следующего слова с последней буквой
предыдущего слова.

program igra_v_slova;

uses crt;

var s: string;

      i, f: integer;

begin

     write(‘Введите слова через пробел: ‘);

     readln(s);

     f:=0;

     for i:=2 to length(s)-1 do

          if s[i]=’ ‘ then

               if
s[i-1]<>s[i+1] then f:=1;

     if f=0 then writeln(‘Совпадают’)

               else
writeln(‘Не совпадают’);

end.

Задача 22.

Определить наименьшую длину слова в заданной
строке. Слова считать отделенными друг от друга
одним или несколькими пробелами.

program mindlina;

uses crt;

var s: string;

      i, lw, min: integer;

begin

     write(‘Введите строку: ‘);

     readln(s);

     s:=s+’ ‘;

     min:=length(s);

     lw:=0;

     for i:=1 to length(s) do begin

          if s[i]<>’ ‘ then

               lw:=lw+1

               else
if (min>lw) and (lw>0) then begin

                    min:=lw;

                    lw:=0;

                    end

                    else

                    lw:=0;

     end;

     writeln(‘Наименьшая длина слова ‘, min);

end.

Задача 23.

Ввести с клавиатуры 10 слов и вывести их на экран
в алфавитном порядке.

program sort_slov;

uses crt;

const n=10;

var s: array[1..n] of string;

      pp: string;

      i, j: integer;

begin

     writeln(‘Введите слова:’);

     for i:=1 to n do

          readln(s[i]);

     for i:=1 to n-1 do

          for j:=i+1 to n do

               if
s[i]>s[j] then begin

                    pp:=s[i];

                    s[i]:=s[j];

                    s[j]:=pp;

               end;

     writeln(‘Список слов по алфавиту:’);

     for i:=1 to n do

          writeln(s[i]);

end.

Алгоритмы поиска в строке

Постановка задачи поиска в строке

Часто приходится сталкиваться со специфическим поиском, так называемым поиском строки (поиском в строке). Пусть есть некоторый текст Т и слово (или образ) W. Необходимо найти первое вхождение этого слова в указанном тексте. Это действие типично для любых систем обработки текстов. (Элементы массивов Т и W – символы некоторого конечного алфавита – например, {0, 1}, или {a, …, z}, или {а, …, я}.)

Наиболее типичным приложением такой задачи является документальный поиск: задан фонд документов, состоящих из последовательности библиографических ссылок, каждая ссылка сопровождается «дескриптором», указывающим тему соответствующей ссылки. Надо найти некоторые ключевые слова, встречающиеся среди дескрипторов. Мог бы иметь место, например, запрос «Программирование» и «Java». Такой запрос можно трактовать следующим образом: существуют ли статьи, обладающие дескрипторами «Программирование» и «Java».

Поиск строки формально определяется следующим образом. Пусть задан массив Т из N элементов и массив W из M элементов, причем 0<M≤N. Поиск строки обнаруживает первое вхождение W в Т, результатом будем считать индекс i, указывающий на первое с начала строки (с начала массива Т) совпадение с образом (словом).
Пример. Требуется найти все вхождения образца W = abaa в текст T=abcabaabcabca.

Образец входит в текст только один раз, со сдвигом S=3, индекс i=4.

Алгоритм прямого поиска

Идея алгоритма:
1. I=1,
2. сравнить I-й символ массива T с первым символом массива W,
3. совпадение → сравнить вторые символы и так далее,
4. несовпадение → I:=I+1 и переход на пункт 2,

Условие окончания алгоритма:
1. подряд М сравнений удачны,
2. I+M>N, то есть слово не найдено.

Сложность алгоритма:
Худший случай. Пусть массив T→{AAA….AAAB}, длина │T│=N, образец W→{A….AB}, длина │W│=M. Очевидно, что для обнаружения совпадения в конце строки потребуется произвести порядка N*M сравнений, то есть O(N*M).

Недостатки алгоритма:
1. высокая сложность — O(N*M), в худшем случае – Θ((N-M+1)*M);
2. после несовпадения просмотр всегда начинается с первого символа образца и поэтому может включать символы T, которые ранее уже просматривались (если строка читается из вторичной памяти, то такие возвраты занимают много времени);
3. информация о тексте T, получаемая при проверке данного сдвига S, никак не используется при проверке последующих сдвигов.

Алгоритм Д. Кнута, Д. Мориса и В. Пратта (КМП-поиск)

Алгоритм КМП-поиска фактически требует только порядка N сравнений даже в самом плохом случае.
Пример.
(Символы, подвергшиеся сравнению, подчеркнуты.)

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

Идея КМП-поиска – при каждом несовпадении двух символов текста и образа образ сдвигается на все пройденное расстояние, так как меньшие сдвиги не могут привести к полному совпадению.

Особенности КМП-поиска:
1. требуется порядка (N+M) сравнений символов для получения результата;
2. схема КМП-поиска дает подлинный выигрыш только тогда, когда неудаче предшествовало некоторое число совпадений. Лишь в этом случае образ сдвигается более чем на единицу. К несчастью совпадения встречаются значительно реже чем несовпадения. Поэтому выигрыш от КМП-поиска в большинстве случаев текстов весьма незначителен.

Алгоритм Р. Боуера и Д. Мура (БМ-поиск)

На практике алгоритм БМ-поиска наиболее эффективен, если образец W длинный, а мощность алфавита достаточно велика.

Идея БМ-поиска – сравнение символов начинается с конца образца, а не с начала, то есть сравнение отдельных символов происходит справа налево. Затем с помощью некоторой эвристической процедуры вычисляется величина сдвига вправо s. И снова производится сравнение символов, начиная с конца образца.

Этот метод не только улучшает обработку самого плохого случая, но и даёт выигрыш в промежуточных ситуациях.
Почти всегда, кроме специально построенных примеров, БМ-поиск требует значительно меньше N сравнений. В самых же благоприятных обстоятельствах, когда последний символ образца всегда попадает на несовпадающий символ текста, число сравнений равно (N / M), в худшем же случае – О((N-M+1)*M+ p), где p – мощность алфавита.

Алгоритм Рабина-Карпа (РК-поиск)

Пусть алфавит D={0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, то есть каждый символ в алфавите есть d–ичная цифра, где d=│D│.

Пример. Пусть образец имеет вид W = 3 1 4 1 5
Вычисляем значения чисел из окна длины |W|=5 по mod q, q — простое число.

23590(mod 13)=8, 35902(mod 13)=9, 59023(mod 13)=9, …
k1=314157(mod 13) – вхождение образца,
k2=673997(mod 13) – холостое срабатывание.

Из равенства ki= kj (mod q) не следует, что ki= kj (например, 31415=67399(mod 13), но это не значит, что 31415=67399). Если ki= kj (mod q), то ещё надо проверить, совпадают ли строки W[1…m] и T[s+1…s+m] на самом деле.
Если простое число q достаточно велико, то дополнительные затраты на анализ холостых срабатываний будут невелики.
В худшем случае время работы алгоритма РК — Θ((N-M+1)*M), в среднем же он работает достаточно быстро – за время О(N+M).

Пример: Сколько холостых срабатываний k сделает алгоритм РК, если
q= 11, 13, 17. Пусть W={2 6}

26 mod 11=4 → k =3 холостых срабатывания,
26 mod 13=0 → k =1 холостое срабатывание,
26 mod 17=9 → k =0 холостых срабатываний.

Очевидно, что количество холостых срабатываний k является функцией от величины простого числа q (если функция обработки образца mod q) и, в общем случае, от вида функции для обработки образца W и текста Т.

Информатика. Учебник для 9 класса (по учебнику К. Ю. Полякова, Е.А. Еремина, базовый уровень) 

§19. Символьные строки.

Что такое символьная строка?

Ключевые слова:

• символьная строка	
• длина строки	
• сцепление строк	
• срез строки (подстрока)
• удаление символов
• вставка символов
• поиск подстроки

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

Символьная строка — это последовательность символов.

Такой тип данных в алгоритмическом языке называется литерным и обозначается лит, а в Паскале называется строковым и обозначается string.

Используя дополнительные источники, выясните, что означают слова «литера» и «литерный».

Используя дополнительные источники, выясните значение английского слова string.

Вот пример объявления строки:

лит s                              var s: string;

Новое значение записывается в строку с помощью оператора присваивания:

s:=’Вася пошёл гулять’                              s:=’Вася пошёл гулять’;

или оператора ввода с клавиатуры:

ввод s                              readln(s);

Обратите внимание, что при вводе строк в Паскале нужно использовать оператор readln (англ. read line — читать до конца строки) вместо read.

Существуют стандартные функции, которые определяют длину строки (количество символов в ней). В алгоритмическом языке такая функция называется длин, а в Паскале — length (в переводе с англ. — длина). В этом примере в целочисленную переменную п записывается длина строки s:

n:=длин (s)                              n:=length (s);

Напишите полную программу, которая вводит строку с клавиатуры и выводит на экран её длину. Проверьте, как эта программа реагирует на строку с пробелами.

Сравнение строк

Строки можно сравнивать между собой так же, как числа. Например, можно проверить равенство двух строк:

ввод S

если s=’sEzAm’ то

вывод ‘Слушаюсь и повинуюсь!’

иначе

вывод ‘Пароль неправильный’

все

Та же программа на языке Паскаль:

readln (s);

if s=’sEzAm’ then

write(‘Слушаюсь и повинуюсь!’)

else

write ( ‘Пароль неправильный’);

Запишите в тетради, как нужно объявить в этой программе переменную s.

Можно также определить, какая из двух строк больше, какая — меньше. Если строки состоят только из русских или только из латинских букв, то меньше будет та строка, которая идёт раньше в алфавитном порядке. Например, слово «паровоз» будет меньше, чем слово «пароход»: они отличаются в пятой букве и «в» < «х». Это можно проверить экспериментально, например, с помощью такой программы:

Но откуда компьютер «знает», что такое алфавитный порядок? Оказывается, при сравнении используются коды символов (вспомните материал учебника для 8 класса). В современных кодировках и русские, и английские буквы расположены в алфавитном порядке, т. е. код буквы «в» меньше, чем код буквы «х».

С помощью программы сравните пары слов и сделайте выводы:

пар — парк                              Пар — пар                              steam — Пар

Steam — steam                        5Steam — Steam

He используя программу, сравните пары слов:

парта — парк                              ПАрта — Парк                              СПАМ — Spam

ПОЧТА — spam                         П04та — ПОЧта                            почТА — Post

55-66                                        9 — 128

Посимвольная обработка строк

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

s[4]:=   ‘а’                              s[4]:= ‘а’;

Приведём программу, которая вводит строку с клавиатуры, заменяет в ней все буквы «э» на буквы «е» и выводит полученную строку на экран:

В цикле

мы перебираем все символы строки с первого до последнего, и если очередной символ — буква «э», делаем замену:

Вспомните, чем отличается запись s=’e’ от записи s: = ‘e’.

Запишите решение этой задачи, используя цикл пока (while).

Операции со строками

Оператор + используется для «сложения» (объединения, сцепления) строк, эта операция иногда называется конкатенацией. Например:

s1: = ‘Привет’

s2: = ‘Вася’

s:=s1 + ‘,’ + s2 + ‘!’

Здесь и далее считаем, что в программе объявлены строковые (литерные) переменные s, s1 и s2.

Запишите в тетради, какое значение будет иметь переменная s после выполнения этого фрагмента программы. Проверьте ответ с помощью компьютера.

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

Для того чтобы выделить часть строки (подстроку), в алгоритмическом языке применяется операция получения среза (англ. slicing). Например, s[3:7] означает «символы строки s с 3-го по 7-й включительно». В Паскале для этого используется функция сору, она принимает три параметра: имя строки, номер начального символа и количество символов. Оба следующих фрагмента копируют в строку s1 символы строки s с 3-го по 7-й (всего 5 символов):

s:=f1234567891                              s:=’123456789′;

s1:=s [3:7]                              s1:=copy(s,3,5);

Запишите в тетради, какое значение будет иметь переменная si после выполнения этого фрагмента программы. Проверьте ответ с помощью компьютера.

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

s:=’123456789′                              s: = ‘123456789 ‘ ;

удалить (s, 3, 6)                              delete (s, 3, 6) ;

Запишите в тетради, какое значение будет иметь переменная s после выполнения этого фрагмента программы. Проверьте ответ с помощью компьютера.

При вставке символов процедуре передают вставляемый фрагмент, имя исходной строки и номер символа, с которого начинается вставка:

s:= 11234567891                              s:= ‘123456789’;

вставить(1 ABC 1, s, 3)                              insert(1 ABC 1, s, 3);

Запишите в тетради, какое значение будет иметь переменная s после выполнения этого фрагмента программы. Проверьте ответ с помощью компьютера.

Используя только операции выделения подстроки и «сложения» строк, постройте из строки

s: = *информатика!

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

Приведите несколько способов построения строки

‘А. Семёнов’

из строки

s: = ‘Семёнов Андрей’

Какой из них лучше? Как вы сравнивали эти способы?

Поиск в символьных строках

Существуют функции для поиска подстроки (и отдельного символа) в строке. Им нужно передать образец для поиска и строку, в которой надо искать:

Функция позиция возвращает целое число — номер символа, с которого начинается образец (буква «с») в строке s. Если образец встречается в строке несколько раз, функция находит первый из них. В языке Паскаль функция pos (от англ. position — позиция, расположение) работает точно так же.

Выясните экспериментально, какое значение возвращает функция позиция (pos), если образец для поиска не найден в строке.

Как можно найти вторую букву «с» с начала строки?

Вводится строка, в которой сначала записана фамилия человека, а затем через пробел — его имя, например ‘Семёнов Андрей’.

Преобразования «строка ? число»

Иногда символьная строка, которая передаётся программе, содержит запись числа. С таким значением нельзя выполнять арифметические операции, потому что это символы, а не число.

Чему будут равны значения переменных п и s после выполнения этих команд? Как нужно объявить эти переменные в программе?

n:= 12 + 34;

s: = ’12’ + ’34’;

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

лит_в_цел — переводит строку в целое число;

лит_в_вещ — переводит строку в вещественное число.

Разберём такой пример:

лит s, цел N, лог ОК

s:=’123′

N:= лит_в_цел(s, OK) | N = 123

если не ОК то

вывод ‘Ошибка!’

все

Строку не всегда можно преобразовать в число (например, если в ней содержатся буквы). Поэтому функция лит_в_цел использует второй параметр — логическую переменную ОК. Функция записывает в эту переменную логическое значение да («истина»), если операция закончилась успешно, и нет (ложь), если произошла ошибка.

Изучите приведённый фрагмент программы и выясните, как объявляется логическая переменная.

А вот пример использования функции лит_в_вещ:

лит s, вещ X, лог ОК

s:=’123.456′;

Х:=лит_в_вещ(s, ОК) | Х= 123.456

если не ОК то

вывод ‘Ошибка!’

все

Какие из этих строк можно преобразовать в целое число, какие — в вещественное?
а) ’45’;
б) ‘5р.’;
в) ‘14.5’;
г) ’14;5′;
д) ‘tu154’;
е) ’543.0’;
ж) ’(30)’.

Обратное преобразование (из числа в строку) возможно всегда:

N:=123

s:=цел_в_лит(N) | s=’123′

X:=123.456

s:=вещ_в_лит(X) I s=’123.456′

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

В языке Паскаль строка преобразуется в число (целое или вещественное) с помощью процедуры val:

var r: integer;

• • •

s : = ‘123’;

val(s, N, r); {N=123}

s:=’123.456′;

val (s, X, r); {X=123.456}

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

Преобразование числа в строку выполняет процедура str:

n : = 123;

str(N, s); {s=’123′}

х:=123.456;

str (X, s); {s=’1.234560E+002′}

str(X:10:3, s); {s=’ 123.456′}

По умолчанию вещественные числа записываются в научном формате (‘1.234560Е+002’ означает 1,23456•10²). В последней строке примера используется форматный вывод: запись Х:10:3 означает «вывести число в 10 позициях с тремя знаками в дробной части».

Выводы

• Символьная строка — это последовательность символов.
• Длина строки — это количество символов в строке.
• Подстрока — это часть символьной строки.
• При обращении к отдельному символу строки его номер записывают в квадратных скобках.
• Знак « + » при работе со строками означает объединение строк.
• Для обработки символьных строк используют вспомогательные алгоритмы стандартной библиотеки — процедуры и функции. Процедура изменяет переданную ей строку, а функция возвращает результат — новое значение, не изменяя исходную строку.
• Функции поиска подстроки возвращают номер символа, с которого начинается подстрока, или 0 в случае неудачи.
• Строку можно преобразовать в число для того, чтобы затем выполнять с ним вычисления. Число можно преобразовать в символьную строку.

Нарисуйте в тетради интеллект-карту этого параграфа.

Вопросы и задания

1. Во многих языках программирования можно использовать массивы символов, т. е. массивы, каждый элемент которых — один символ. Чем отличается строка от массива символов?

2. Чем отличается действие оператора + для чисел и для символьных строк?

3. Можно ли обойтись без стандартной функции для вставки подстроки? Если да, то чем её можно заменить?

4. Как определить, что при поиске в строке образец не найден?

5. Как бы вы искали первый символ «с» с конца строки?

6. Выполните по указанию учителя задания в рабочей тетради.

Оглавление

§18. Игровые стратегии.

§19. Символьные строки.

§20. Обработка массивов.

Сегодня посмотрим одно из самых интересных заданий из ЕГЭ по информатике 2023. Будем решать 24 задание. В этом задании нужно работать с файлами.

Все решения задач из задания 24 ЕГЭ по информатике 2023 будут приведены на языке программирования Python (Питон).

Поехали!

Задача (Самая простая)

Текстовый файл состоит не более чем из 10⁶ символов A, B и C. Определите максимальное количество идущих подряд символов B. Для выполнения этого задания следует написать программу. Ниже приведён файл, который необходимо обработать с помощью данного алгоритма.

Решение:

Решим данную задачу на языке Python.

f=open('24_1.txt')
s=f.read()
k=0
kmax=0

for i in range(0, len(s)):
    if s[i]=='B':
        k=k+1
        kmax=max(k, kmax)
    else:
        k=0

print(kmax)
    

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

С помощью команды .read() зачитываем в переменную s всё содержимое файла.

Переменная k — это текущий счётчик символов «B». Задача переменной kmax сохранить максимальное значение k.

С помощью цикла for перебираем все символы из строки s. Переменная i пробегается по номерам всех симолов. Счёт символов начинается в строке с нуля. В начале берём нулевой символ, потом первый и т.д. Конструкция for i in range(0, len(s)) позволяет пройтись по всем символам строки до конца.

Если нам встретился нужный символ «B», то мы счётчик прибавляем на 1. Это значит, что мы подсчитываем текущую цепочку. Если будет стоять 3 символа «B» подряд, значит, счёт k покажет значение 3. Как только встретится дургой символ, то это означает, что цепочка прервалась и счётчик переводится в первоначальное положение 0.

При любом увеличении счётчика происходит анализ этого счётчика на максимальность. Функция max выбирает максимальное значение из старого значения kmax и нового показания счётчика k. Если счётчику k удалось победить kmax, то его значение будет считаться максимальным на данный момент времени.

В ответ идёт значение kmax. Это и есть длина максимальной цепочки. В этой задачке ответ получается 11.

Ответ: 11

Закрепим это простое задание из ЕГЭ по информатике 2023.

Задача (Простая, закрепление)

Текстовый файл состоит не более чем из 10⁶ символов X, Y и Z. Определите максимальное количество идущих подряд символов, среди которых нет символа Z. Для выполнения этого задания следует написать программу.

Решение:

Решение похоже на предыдущее.

f=open('24_2.txt')
s=f.read()
k=0
kmax=0

for i in range(0, len(s)):
    if s[i]!='Z':
        k=k+1
        kmax=max(k, kmax)
    else:
        k=0

print(kmax)
    

Если нет символов «Z», то подсчитываем, иначе сбрасываем.

Задача (Обращаемся к соседу)

Текстовый файл состоит не более чем из 10⁶ символов X, Y и Z. Определите максимальное количество идущих подряд символов, расположенных в алфавитном порядке (возможно с повторением симолов). Для выполнения этого задания следует написать программу.

Решение:

f=open('24_2.txt')
s=f.read()
k=1
kmax=0

for i in range(0, len(s)-1):
    if s[i]<=s[i+1]:
        k=k+1
        kmax=max(k, kmax)
    else:
        k=1

print(kmax)
    

В ответе получается 15. Символы можно сравнивать между собой с помощью знаков «>» или меньше «<» ( а так же «>=» или «<=»), причём это сравнение происходит в алфавитном порядке. Например, символ «B» будет больше, чем «A» и т.п. Теперь нам нужно уже обратится к соседу, уже важна связь между соседними символами. Раз мы обращаемся к следующему символу, то должны пробегать до len(s)-1, иначе куда мы будем обращаться, когда дойдём до последнего символа?

В самом начале цепочки мы анализируем два символа, а к счётчику прибавляем всего лишь 1. Чтобы это учесть, в начале счётчику (переменной k) присваиваем 1. Затем, по мере продвижения по цепочке, мы добавляем в наш анализ 1 новый символ, и к счётчику добавляется одна 1. Дальше уже таких проблем нет.

Раз мы присвоили в переменную k единицу, то и сбрасывать в ветке else мы тоже должны на 1. Эти значения обычно взаимосвязаны.

Если мы обращаемся к соседнему символу, как правило, счётчик и сброс устанавливаются в 1. Это не стопроцентная истина, но иметь ввиду это нужно.

Ответ: 15

Задача (Обращаемся к соседу, закрепление)

Текстовый файл состоит не более чем из 10⁶ символов арабских цифр (0, 1, …,9). Определите максимальное количество идущих подряд цифр, среди которых каждые две соседние различны. Для выполнения этого задания следует написать программу.

Решение:

f=open('24_3.txt')
s=f.read()
k=1
kmax=0

for i in range(0, len(s)-1):
    if s[i]!=s[i+1]:
        k=k+1
        kmax=max(k, kmax)
    else:
        k=1

print(kmax)
    

Если соседи различны, мы подсчитываем, иначе сбрасываем.

Ответ: 120

Задача (Обращаемся к соседу, ещё сложнее)

Текстовый файл состоит не более чем из 10⁶ символов арабских цифр (0, 1, …,9). Определите максимальное количество идущих подряд нечётных цифр, расположенных в неубывающем порядке. Для выполнения этого задания следует написать программу.

Решение:

f=open('24_3.txt')
s=f.read()
k=1
kmax=0

for i in range(0, len(s)-1):
    if s[i]<=s[i+1] and s[i] in '13579' and s[i+1] in '13579' :
        k=k+1
        kmax=max(k, kmax)
    else:
        k=1

print(kmax) 

Здесь опять можно применить знаки сравнения прям к символам. Удобно проверить принадлежность к нечётным цифрам конструкцией s[i] in ‘13579’. Нечётной цифрой должна быть как текущая, так и следующая.

Ответ: 8

Решим ещё одну тренировочную задачу из ЕГЭ по информатике 2023.

Задача (Обращаемся к соседу, ещё сложнее, закрепление)

Текстовый файл состоит не более чем из 10⁶ символов 1, 2, 3, A, B, С. Определите максимальное количество идущих подряд символов, среди которых никакие две буквы и никакие две цифры не стоят рядом. Для выполнения этого задания следует написать программу.

Решение:

f=open('24_4.txt')
s=f.read()
k=1
kmax=0

for i in range(0, len(s)-1):
    if (s[i] in '123' and s[i+1] in 'ABC') or (s[i] in 'ABC' and s[i+1] in '123') :
        k=k+1
        kmax=max(k, kmax)
    else:
        k=1

print(kmax) 

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

Ответ: 20

Задача (Исключаем строку из 2-х символов, демо 2022)

Текстовый файл состоит из символов P, Q, R и S.

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

Решение:

Напишем решение на языке Python.

f=open('24_5.txt')
s=f.read()
k=1
kmax=0

for i in range(0, len(s)-1):
    if s[i]=='P' and s[i+1]=='P':
        k=1
    else:
        k=k+1
        kmax = max(k, kmax)

print(kmax)

Подсчитываем символы, пока не встретилась комбинация двух P подряд. Как только встретилась данная комбинация, сбрасываем счётчик на 1. Здесь мы сбрасываем счётчик на значение 1, чтобы учесть один символ, которые находится в самой комбинации PP. И в начале мы тоже устанавливаем счётчик в значение 1 по этой же причине.

Мы проходим в цикле for до длины строки минус один. Значение 1 в счётчике при сбросе и в начале программы так же компенсирует и тот момент, что мы не подсчитываем последний символ!

При изменении счётчика, сохраняем максимальное значение в переменной mx

Если бы у нас была вместо PP другая комбинация, состоящая к примеру из 5 символов, то мы бы тогда в начале и при сбросе писали в счётчик значение 5-1=4.

Здесь тоже работает негласное правило, обращаемся к соседу, значит, счётчик устанавливаем в 1.

В этой задаче получается ответ 188.

Ответ: 188

Задача (Исключаем подстроку из 3-х символов)

Текстовый файл состоит из символов арабских цифр(0, 1, …,9).

Определите максимальное количество идущих подряд символов
в прилагаемом файле, среди которых нет трёх символов 0, стоящих рядом.
Для выполнения этого задания следует написать программу.

Решение:

Напишем решение на языке Python.

f=open('24_6.txt')
s=f.read()
k=2
kmax=0

for i in range(0, len(s)-2):
    if s[i]=='0' and s[i+1]=='0' and s[i+2]=='0':
        k=2
    else:
        k=k+1
        kmax = max(k, kmax)

print(kmax)

Чтобы понять это решение, нужно посмотреть предыдущую задачу. Мы здесь обращаемся к двум соседям, значит, счётчик устанавливаем в 2. Так же проходим в цикле до len(s)-2. Нежелательная строка может состоять не только из одинаковых символов. Может быть строка «XYYZ», к примеру.

Ответ: 7684

Задача (Не более одного символа Z)

Текстовый файл состоит не более чем из 10⁶ символов X, Y и Z. Определите максимальное количество идущих подряд символов, среди которых символ Z встречается не более одного раза.

Решение:

В нашей цепочке один раз можно встретиь символ Z, а два раза уже нельзя. Здесь мы применим функцию .split(). Как работает эта фнкция? Напишем тестовую программу.

s='sadqttqtreq'
a=s.split('q')
print(a)

Результат данной программы будет следующим:

[‘sad’, ‘tt’, ‘tre’, »]

Команда split «разрезает» строку по символу «q». В результате мы получаем массив с кусочками этой строки.

Решение нашей задачи.

f=open('24_7.txt')
s=f.read()
a=s.split('Z')
k=0
kmax=0

for i in range(0, len(a)-1):
  k = len(a[i]) + 1 + len(a[i+1])
  kmax = max(k, kmax)

print(kmax)

Разрезаем нашу строку по символу «Z». Пробегаемся уже по массиву a. Цепочка-кандидат это текущий кусочек (a[i]), символ Z (1) и следующий кусочек (a[i+1]).

Каждого кандитата проверяем сразу на максимальность.

Ответ: 43

Задача (Не более двух символов Z)

Текстовый файл состоит не более чем из 10⁶ символов X, Y и Z. Определите максимальное количество идущих подряд символов, среди которых символ Z встречается не более двух раз.

Решение:

Решение аналогично предыдущему.

f=open('24_7.txt')
s=f.read()
a=s.split('Z')
k=0
kmax=0

for i in range(0, len(a)-2):
  k = len(a[i]) + 1 + len(a[i+1]) + 1 + len(a[i+2])
  kmax = max(k, kmax)

print(kmax)

Ответ: 50

Задача (Звенья)

Текстовый файл состоит не более чем из 10⁶ символов X, Y и Z. Определите максимальную длину цепочки символов, состоящей из повторяющихся фрагментов XYZ. Цепочка должна начинаться с символа X и заканчиваться символом Z. Например, для строки ZZZXYZXYZXZZZ длина цепочки равна 6: XYZ+XYZ

Решение:

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

f=open('24_8.txt')
s=f.read()
s=s.replace('XYZ', '1')
k=0
kmax=0

for i in range(0, len(s)):
    if s[i]=='1':
        k=k+1
        kmax=max(k, kmax)
    else:
        k=0

print(kmax*3)

Мы с помощью команды replace заменили звенья на «1» (на символ, которого точно нет в файле). Теперь задача свелась к самой простой, которую мы рассматривали в начале статьи. Нужно просто подсчитать количество идущих поряд единиц.

В ответе нас просили указать количество символов, а не звеньев, поэтому переменную kmax умножаем на 3.

Ответ: 66

Задача (Звенья, закрепление)

Текстовый файл состоит не более, чем из 10⁶ символов из набора A, B, С. Найдите максимальное количество идущих пар символов AC или AB. Искомая подстрока может включать только пары AB, только пары AC или содержать одновременно как пары AC, так и пары AB.

Решение:

f=open('24_9.txt')
s=f.read()
s=s.replace('AB', '1')
s=s.replace('AC', '1')
k=0
kmax=0

for i in range(0, len(s)):
    if s[i]=='1':
        k=k+1
        kmax=max(k, kmax)
    else:
        k=0

print(kmax)

Здесь нам подходит звено, как и AB, так и AC. В ответе нужно указать количество пар, поэтому не на что умножать переменную kmax не нужно.

Ответ: 19

Задача (Звенья, основная волна 20.06.22)

Текстовый файл состоит из символов A, B, C, D и O. Определите максимальное количество идущих подряд пар символов вида согласная + гласная в прилагаемом файле. Для выполенения этого задания следует написать программу.

Решение:

f=open('24_10.txt')
s=f.read()
s=s.replace('BA', '1')
s=s.replace('CA', '1')
s=s.replace('DA', '1')
s=s.replace('BO', '1')
s=s.replace('CO', '1')
s=s.replace('DO', '1')
k=0
kmax=0

for i in range(0, len(s)):
    if s[i]=='1':
        k=k+1
        kmax=max(k, kmax)
    else:
        k=0

print(kmax)

Ответ: 174

Задача (Звенья, последнее звено неполное)

Текстовый файл состоит не более чем из 10⁶ символов X, Y и Z. Определите максимальную длину цепочки вида XYZXYZXYZ… (составленной из фрагментов XYZ, последний фрагмент может быть неполным). Для выполнения этого задания следует написать программу. Ниже приведён файл, который необходимо обработать с помощью данного алгоритма.

Решение:

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

Пусть в начале показания счётчика равно нулю. Если мы находим нужный нам символ в нужной последовательности, то прибавляем к счётчику 1. Если последовательность сбивается, то ставим счётчик в ноль.

На рисунке представлен данный алгоритм. В нижней строке указано показание счётчика в момент анализа символа.

На данном рисунке максимальная длина цепочки нужных символов равна 9.

Видим, что для символа X, когда он находится на своём месте, остаток от деления значения счётчика на 3 равен 0.

Для символа Y, когда данный символ находится на своём месте, остаток от деления значения счётчика на 3 равен 1.

Для символа Z, когда данный символ находится на своём месте, остаток от деления значения счётчика на 3 равен 2.

Мы смотрим остаток от деления на 3, потому что у нас длина звена равна трём (XYZ).

Таким образом, мы и наш анализ очередного символа привяжем к показанию счётчика:

f=open('24_11.txt')
s=f.read()
k=0
kmax=0

for i in range(0, len(s)):
    if (s[i]=='X' and k%3==0) or  (s[i]=='Y' and k%3==1) or (s[i]=='Z' and k%3==2):
        k=k+1
        kmax = max(k, kmax)
    else:
        if s[i]=='X': k=1
        else: k=0


print(kmax)

Важный момент: Если нужную цепочку прервал символ X, то нужно счётчик сразу выставить в 1, иначе может произойти такая ошибка:

Т.е. первые три нужных символа в цепочке алгоритм не засчитал.

Поэтому мы не просто сбрасываем счётчик в ноль, а прописываем условие:

if s[i]=='X': k=1
else: k=0

Ответ: 13

Задача (Полезный приём)

Текстовый файл 24-157.txt состоит не более чем из 10⁶ символов и содержит только заглавные буквы латинского алфавита (ABC…Z). Определите символ, который чаще всего встречается в файле между двумя одинаковыми символами. Например, в тексте CCBAABABCBC есть комбинации ABA, BAB, BCB и CBC. Чаще всего – 2 раза – между двумя одинаковыми символами стоит B, в ответе для этого случая надо написать B2 (без пробелов и других разделителей). Если таких символов несколько, выведите тот, который стоит раньше в алфавите.

Решение:

f=open('24-157.txt')
s=f.read()
a=[0]*150

for i in range(0, len(s)-2):
    if s[i]==s[i+2]:
        a[ord(s[i+1])] = a[ord(s[i+1])] + 1

ch=''
mx=0
for i in range(0, 150):
    if a[i]>mx:
        mx=a[i]
        ch=chr(i)


print(ch, mx)

Здесь мы заводим массив a. Индексы этого массива — это коды ANSI всех букв латинского алфавита (ABC…Z). Ведь, как мы знаем, каждая буква кодируется определённым числом (кодом ANSI). Вот часть этой таблицы.

Например, буква A кодируется кодом 65. Коды увеличиваются в алфавитном порядке на 1. Буква Z кодируется числом 90. Таким образом, 150 ячеек точно хватит для нашего алфавита. Здесь берём с запасом, потому что на экзамене можно точно не вспомнить коды, но достаточно запомнить, что 150 ячеек вполне хватит для заглавных и строчных букв латинского алфавита.

Значит, ячейка 65 отвечает за букву A, ячейка 66 отвечает за букву B и т.д. Если мы встретили букву между двумя одинаковыми буквами, то её ячейка увеличивается на 1.

Функция ord() превращает символ в код ANSI.

После того, как мы прошли всю строку и собрали информацию о наших буквах, нужно пройти массив a и найти наибольшее число в нём.

Здесь мы уже не пользуемся функцией max, а используем условие, потому что нужно кроме максимального числа тянуть ещё один параметр — сам код (переменную i). Функция chr() превращает код ANSI обратно в символ.

Ответ: W1608

Задача (Строки различной длины)

Текстовый файл 24-164.txt состоит не более чем из 10⁶ символов и содержит только заглавные буквы латинского алфавита (ABC…Z). Текст разбит на строки различной длины. Необходимо найти строку, содержащую самую длинную цепочку стоящих подряд одинаковых букв. Если таких строк несколько, надо взять ту, которая в файле встретилась раньше. Определите, какая буква встречается в этой строке чаще всего. Если таких букв несколько, надо взять ту, которая стоит раньше в алфавите. Запишите в ответе эту букву, а затем – сколько раз она встречается во всем файле.

Пример. Исходный файл:

ZZQABA
ZALAAC
QRAQUT

В этом примере в первой и второй строках наибольшая длина цепочек одинаковых буквы равна 2 (ZZ в первой строке, AA во второй), в третьей – 1. Берём первую строку, т.к. она находится в файле раньше. В этой строке чаще других встречаются буквы Z и A (по 2 раза), выбираем букву A, т. к. она стоит раньше в алфавите. В ответе для этого примера надо записать A6, так как во всех строках файла буква A встречается 6 раз.

Решение:

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

f=open('24-164.txt')
kmax=0
count=0
n=-1
for s in f.readlines():
    count=count+1
    k=1
    for i in range(0, len(s)-1):
       if s[i]==s[i+1]:
           k=k+1
           if k>kmax:
               kmax=k
               n=count
       else:
           k=1

print(n)

Получается строка под номером 162. Переменная count считает строки по порядку. В переменную n сохраняем номер нужной строки. Опять пользуемся условием, а не функцией max, т.к. здесь нужно и обновлять kmax, и сохранять значение n. У нас условие строгое k>kmax, значит, сохранится первая строка с наибольшей искомой цепочкой.

f=open('24-164.txt')

count=0
a=[0]*150

for s in f.readlines():
    count=count+1
    k=1
    if count==162:
        for i in range(0, len(s)):
            a[ord(s[i])] = a[ord(s[i])] + 1
       
ch=''
mx=0
for i in range(0, 150):
    if a[i] > mx:
        mx=a[i]
        ch=chr(i)

print(ch)

Теперь нас интересует только строка под номером 162. Далее используем приём из прошлой задачи. Заводим массив a из 150 ячеек и используем таблицу кодов ANSI. Так определяем какая буква встретилась чаще всего в строке под номером 162. Получается буква K.

f=open('24-164.txt')
s=f.read()
print(s.count('K'))

Осталось найти количестов букв K во всём файле. Для этого используем функцию .count()

Ответ: K36582