Стандартные задачи школьного курса оиивт

Язык Паскаль позволяет обрабатывать не только числа, но и символы, слова, тексты. (Как это не парадоксально звучит, сегодня электронно-вычислительные машины заняты по большей части обработкой нечисловой информации!) В то же время, смысл человеческих слов, конечно, не доступен компьютеру, так что под строковой величиной (словом) в системе Turbo-Pascal понимается любой набор символов алфавита, взятый в апострофы.

Например, 'а', 'А', 'азбука’, 'абвг', 'w', 'W', 'way', 'abcdef', 'a1', '1', '1+1=', '123 456' - строковые константы. (Пробел такой же символ, как и все остальные!)

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

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

VAR Z:STRING[25];

T:STRING[15];

Y:STRING[20]; .

(Число, указанное в квадратных скобках после служебного слова STRING, в известной мере определяет количество символов в значении строковой переменной. Так, значением слова Z может быть слово, содержащее не более 25 символов, а в слове Т не может быть более 15 букв, соответственно в Y - 20.)

Количество символов в слове часто называется длиной слова. Для вычисления длины слова (скажем X) в Паскале пользуются функцией LENGTH(Х), возвращающей количество символов в строковой переменной X. Например, length('солнце')=6, а в результате выполнения последовательности операторов

X:='SUN'; Y:=length(X)

значение переменной Y станет равным трем.

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

Функция COPY(S,Pos,Len) ("вырезка") применяется для получения подстроки длиной Len символов строки S, причем подстрока "вырезается", начиная с позиции Pos.

Простейший пример, иллюстрирующий применение функций COPY и LENGTH, выглядит так.

Задача 2.1.1. Составьте программу, выясняющую, совпадают ли первая и последняя буквы слова X.

program z211 (input, output);

var x:string[10];

begin

writeln(Введите слово ‘);readln(x);

if copy(x,1,1)=copy(x,length(x),1)

then writeln('первая и последняя буквы совпадают')

else writeln('первая и последняя буквы не совпадают')

end.

Функция CONCAT(S1,S2,...,SN) возвращает строку, полученную слиянием (конкатенацией) строк S1, S2,..., SN.

Пример.

program p211 (input, output);

var x,y,z: string[10];

begin

readln(x); readln(y);

z:=concat(x,y); writeln('z=',z)

end.

Running

конь

як

z=коньяк

Решение следующей задачи иллюстрирует применение трех названных выше функций.

Задача 2.1.2. Составьте программу циклической перестановки букв слова X, при которой последняя буква становится первой, 1-я - 2-й, i-я - i+1-й.

Комментарий. Элементарный анализ условия задачи показывает, что программа ее решения должна преобразовывать слово СТОЛ в слово ЛСТО, ЛАМПА - АЛАМП и т.д. Легко также увидеть, что подобное преобразование можно осуществить, "отрезав" последнюю букву слова X и "приклеив" ее в начало. Именно такой подход реализуется в следующей программе.

program z212 (input, output);

var x:string[10];

begin

writeln(‘Введите слово’);readln(x);

x:=concat(copy(x,length(x),1),copy(x,1,length(x)-1));

writeln(x)

end.

Функция POS(SubStr,S) используется в процессе поиска номера символа, начиная с которого подстрока SubStr, входит в строку S.

Пример.

program p212 (input, output);

var x,y:string[10];

n:integer;

begin

readln(x); readln(y);

n:=pos(x,y); writeln('n=',n)

end.

Running Комментарий. 12345

яр маляр

маляр яр

n=4

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

Процедура DELETE в общем виде записывается так:

DELETE(S,Pos,Len),

и при ее выполнении из строки S, начиная с позиции Pos, удаляется подстрока длиною Len символов (см. задачу 2.1.3).

Задача 2.1.3. Составьте программу, удаляющую первый символ слова X.

program z213 (input, output);

var x:string[10];

begin

writeln(‘Введите слово’);readln(x);

delete(x,1,1);

writeln('x=',x)

end.

Running

маляр

x=аляр

Процедура INSERT, записываемая в общем виде следующим образом:

INSERT(S1,S2,Pos),

позволяет вставить строку S1 в строку S2, начиная с позиции Pos. При этом, если Pos>Length(S2), то результатом выполнения процедуры будет слияние строк S1 и S2 и присваивание полученного значения переменной S2.

Так, в результате выполнения фрагмента программы:

S1:='обеда'; S2:='по'; insert(S1,S2,3)

переменная S2 примет значение 'победа'.

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

Задача 2.1.4. Составьте программу удваивающую каждую букву слова X.

Комментарий. Очевидно, что программа решения данной задачи слово ХОД должна преобразовывать в слово ХХООДД, ЛЕС - ЛЛЕЕСС и т.д. В том случае, когда вводимое с клавиатуры слово состоит ровно из одного символа, также легко видеть, что оператор X:=X+X по существу является решением нашей задачи. Нетрудно понять и то, что значением выражения

copy(X,i,1)+copy(X,i,1)

является удвоенная i-ая буква слова X. Таким образом, перебирая каждую букву слова X, возможно с помощью оператора

Y:=Y+copy(X,i,1)+copy(X,i,1)

получить требуемое слово. Именно эта идея и реализована в приведенной программе.

program z214 (input, output);

var x,y:string [30];

i:integer;

begin

writeln('Введите слово '); readln(x);

y:='';

for i:=1 to length(x) do

y:=y+copy(x,i,1)+copy(x,i,1);

x:=y; writeln('преобразованное слово ',x)

end.

Задача 2.1.5. Составьте программу обращения слова X (программу, пребразующую слово X в слово, записанное теми же буквами, но в обратном порядке).

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

program z215_1 (input,output);

var x,y:string[30];

i:integer;

begin

writeln('Введите слово '); readln(x);

y:='';

for i:=1 to length(x) do

y:=copy(x,i,1)+y;

{Замена оператора y:=copy(x,i,1)+y на оператор y:=y+copy(x,i,1) приводит к тому, что в результате выполнения программы y становится равным x. От перемены мест слагаемых результат конкатенации меняется!}

x:=y; writeln ('Обращенное слово ',x)

end.

Что же касается второго варианта решения рассматриваемой задачи, то приводимая ниже программа помимо всего прочего является удачной иллюстрацией применения оператора FOR/DOWNTO:

program z215_2 (input,output);

var x,y:string[30];

i:integer;

begin

writeln('Введите слово '); readln(x);

y:='';

for i:=length(x) downto 1 do

y:=y+copy(x,i,1);

x:=y; writeln ('Обращенное слово ',x)

end.

Нетрудно заметить, что в программах z214, z215_1, z215_2 мы вводили промежуточную переменную, сводя тем самым исходную задачу преобразования вводимого с клавиатуры слова к задаче образования нового слова, удовлетворяющего тем или иным условием. Этот прием широко используется при решении различных задач, связанных с обработкой строковых величин, например, и такого типа:

Задача 2.1.6. Составьте программу, вычеркивающую из слова X все буквы "a".

Комментарий. Идея, реализованная в приводимой ниже программе может быть кратко сформулирована так: из исходного слова x в промежуточное слово y поочередно дописываются все буквы слова x за исключением букв "а" (после чего слово x заменяется на окончательное значение промежуточной величины y).

program z216 (input,output);

var x,y:string[45];

i:integer;

begin

writeln('Введите слово ');

readln(x);

y:='';

for i:=1 to length(x) do

if copy(x,i,1)<>'a'

then y:=y+copy(x,i,1);

x:=y; writeln('Измененное слово - ',x)

end.

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

Задача 2.1.7. Составьте программу, вычеркивающую из слова X буквы "a", стоящие на нечетных местах.

program z217 (input,output);

var x,y:string[45];

i:integer;

begin

writeln('Введите слово ');

readln(x);

y:='';

for i:=1 to length(x) do

if (copy(x,i,1)<>'a') or (i mod 2=0)

then y:=y+copy(x,i,1);

x:=y; writeln('Измененное слово: ',x)

end.

Разумеется, при решении ряда задач обработки строковых величин, воспользовавшись процедурами INSERT, DELETE, можно попытаться обойтись без введения промежуточной переменной - именно это и делается в первом варианте (программа z218_1) решения приводимой ниже задачи о замене букв. Однако, как показывает практика, названный прием достаточно универсален, и потому мы также сочли необходимым привести второй вариант (программа z218_2) решения названной задачи, которая формулируется так.

Задача 2.1.8. Составьте программу, меняющую в слове Х все буквы "а" на буквы "б".

Вариант 1.

program z218_1 (input,output);

var x:string[45];

i:integer;

begin

writeln('Введите слово ');

readln(x);

for i:=1 to length(x) do

if copy(x,i,1)='a'

then

begin

delete(x,i,1);

insert('б',x,i)

end;

writeln('Измененное слово: ',x)

end.

Вариант 2.

program z218_2 (input,output);

var x,y:string[30];

i:integer;

begin

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

readln(x);

y:='';

for i:=1 to length(x) do

if copy (x,i,1)='a'

then y:=y+'б'

else y:=y+copy(x,i,1);

x:=y; writeln('Измененное слово ',x)

end.

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

Задача 2.1.9. Составьте программу подсчета количества букв "а" в слове Х.

Комментарий. Задачи, в которых так или иначе требуется организовать подсчет (какого-угодно рода), весьма нередки в программировании, поэтому приведем популярное изложение идеи, что используется при составлении таких программ.

Вообразите себе, что в Вашем распоряжении имеется человек, абсолютно не умеющий считать, а Вы, тем не менее должны проинструктировать его так, чтобы с его помощью получить решение, скажем, такой задачи: "Сколько человек воспользовалось автобусом 1-го маршрута на остановке "О" в течение рабочего дня". Ясно, что в этом случае можно вручить этому человеку пустой ящик, кучу камешков, и объяснить ему, что как только он увидит пассажира, входящего в автобус 1-го маршрута, ему следует бросать по одному камешку в ящик. После этого останется сосчитать количество камешков в ящике.

Описанная процедура и реализована в программе z219, в которой роль ящика играет переменная p, а команда p:=p+1 выступает эквивалентом бросанию камешка в ведро.

program z219 (input,output);

var x:string[45];

i,p:integer;

begin

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

readln(x);

p:=0;

for i:=1 to length(x) do

if copy(x,i,1)='a'

then p:=p+1;

writeln('Количество букв в слове Х - ',p)

end.

Следующая задача - модификация только что рассмотренной.

Задача 2.1.10. Составьте программу вычисления суммы мест, на которых в слове X стоит буква "а".

program z2110 (input,output);

var x,y:string[30];

s,i:integer;

begin

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

readln(x);

s:=0;

for i:=1 to length(x) do

if copy (x,i,1)='a'

then s:=s+i;

if s=0

then writeln ('В слове нет букв "а"')

else writeln ('Сумма мест равна ',s)

end.

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

Задача 2.1.11. Составьте программу, выясняющую, имеется ли в слове X буква "a".

Вариант 1.

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

program z2111_1 (input,output);

var x,y:string[30];

p,i:integer;

begin

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

readln(x);

p:=0;

for i:=1 to length(x) do

if copy (x,i,1)='a'

then p:=p+1;

if p>0

then writeln ('Имеется "а"')

else writeln ('Букв "а" в слове нет')

end.

Вариант 2.

Комментарий. Идея, реализованная в этом варианте программы, широко эксплуатируется в программировании и заключается в том, что при ответе на вопрос "да или нет?" (в нашему случае - "есть ли в слове буква 'а'?") изначально в зависимости от условия задачи фиксируется тот или иной ответ (в нашем случае - "в слове нет букв 'а'"), а затем осуществляется проверка истинности этого ответа. Если зафиксированный ответ оказывается ложным, то он меняется на противоположный (в рассматриваемом случае - "имеется буква "а").

program z2111_2 (input,output);

var x,z:string[30];

i:integer;

begin

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

readln(x);

{изначально фиксируется ответ}

z:='нет букв "а"';

for i:=1 to length(x) do

if copy (x,i,1)='a'

{ответ меняется на противоположный}

then z:='имеется буква "а"';

writeln(z)

end.

Вариант 3.

Комментарий. Третий вариант решения исходной задачи представляет собой модификацию программы z2111_2, в соответствии с которой проверка наличия в слове X буквы "а" производится лишь до тех пор, пока не будет найдена первая по порядку буква "а" (в предыдущем варианте вне зависимости ни от чего каждая буква слова сравнивается с "а"). Легко видеть, что окончание проверки после того, как в слове Х найдена первая по порядку буква "а", достигается за счет использования оператора безусловного перехода для выхода из цикла.

program z2111_3 (input,output);

label 1;

var x,z:string[30];

i:integer;

begin

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

readln(x);

z:='нет букв "а"';

for i:=1 to length(x) do

if copy (x,i,1)='a'

then

begin

z:='имеется буква "а"';

goto 1

end;

1:write(z)

end.

В рассмотренной программе мы впервые использовали "плохой" оператор goto - "плохой" в том смысле, что его частое применение в программах считается дурным тоном среди профессиональных программистов. Тем не менее, этот оператор очень часто оказывается полезен, и потому приведем его общий вид:

GOTO <имя метки>,

где имя метки должно быть указано в разделе описания меток, начинающегося служебным словом label (аналогично тому, как это сделано в программе z211_3).

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

Задача 2.1.12. Составьте программу, определяющую, какая из букв "а" или "б" встречается в слове Х раньше.

program z2112 (input,output);

label 1;

var x, z: string[30];

i: integer;

begin

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

readln(x);

z:='нет ни "а", ни "б"';

for i:=1 to length(x) do

if (copy (x,i,1)='а') or (copy (x,i,1)='б')

then