Структуры данных. Строки. Методические указания. по «Практикуму на ЭВМ» для студентов 1 курса дневного и вечернего отделений факультета математики, механики и компьютерных наук

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Федеральное государственное образовательное учреждение высшего профессионального образования «ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»

АМЕЛИНА Н.И., РУСАНОВА Я.М. СТРУКТУРЫ ДАННЫХ. СТРОКИ

МЕТОДИЧЕСКИЕ УКАЗАНИЯ по «Практикуму на ЭВМ» для студентов 1 курса дневного и вечернего отделений факультета математики, механики и компьютерных наук

Ростов-на-Дону 2007 3

Методические указания разработаны сотрудниками кафедры прикладной математики и программирования: кандидатом технических наук, доцентом Я.М. Русановой и старшим преподавателем Н.И. Амелиной.

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

Печатается в соответствии с решением кафедры прикладной математики и программирования факультета математики, механики и компьютерных наук ЮФУ, протокол № 9 от 31мая 2007г.

4

СОДЕРЖАНИЕ

1 Основные понятия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2 Посимвольная обработка строк . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

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

13

4 Обработка слов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 Задачи. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

Индивидуальные задания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 Задание 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

Задание 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

30

Задание 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

Приложение. Процедуры и функции обработки строк . . . . . . . . . . 35 ЛИТЕРАТУРА . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

37

1 ОСНОВНЫЕ ПОНЯТИЯ

Строка – это последовательность символов произвольной длины (от 0 до 255). Символы хранятся в памяти компьютера в виде кодов. Соответствие между символами и их кодами называется кодировкой, а таблица соответствия между символами и кодами – кодовой таблицей. Определение строкового типа string устанавливает максимальное количество символов, которое может содержать строка. Например, string[20] устанавливает максимальное количество символов в строке – 20, а если количество символов в квадратных скобках не указано, то оно считается равным 255: type slovo=string[20]; var Sl : slovo; Str : string[80]; S,S1,S2 : string; Тип string без указания типа является базовым строковым типом и все другие производные строковые типы совместимы с ним.

Длина строки – это фактическое количество символов, хранящихся в строке. Длина строки может изменяться в ходе работы программы, но не может превышать определенный при описании размер. В языке Pascal в нулевом элементе строки хранится символ, код которого равен длине строки. Значение текущей длины строки можно получить двумя способами: – определяя код нулевого символа ord(S[0]), – используя стандартную функцию length(S). К символам строки можно обращаться по индексу:

S[i] – i-ый символ строки S. 6

Например, фрагмент программы, приведенный ниже, позволяет найти сумму всех цифр, входящих в строку S : sum := 0; for i:=1 to ord(S[0]) do if S[i] in [’0’..’9’] then sum := sum + (ord(S[i])-ord(’0’)); Для строк применимы операции конкатенации и сравнения. Операция конкатенации (+) используется для сцепления нескольких строк в одну: var S1,S2 : string; C : char; . . . . . . . . . S1:=’Строка’; S2:=’ABC’; C:=’ ’; S1:=S1+C+S2; В результате строка S1 будет содержать значение ’Строка ABC’. Для сравнения строк применяются операции отношения:

= , < > , < , > , <= , >= . Сравнение происходит посимвольно слева направо в соответствии с кодировкой символов. При сравнении строк разной длины считается, что отсутствующие символы в более короткой строке имеют код меньше кода любого другого символа, например, ’ABC’ больше ’AB’.

7

2 ПОСИМВОЛЬНАЯ ОБРАБОТКА СТРОК Пример 1. Дана строка. Получить новую строку, содержащую символы исходной строки в обратном порядке. Задачу можно решить с помощью операции конкатенации. Очередной символ S[i] исходной строки S добавляется к результирующей строке Sr слева, что и обеспечивает размещение символов в обратном порядке. program S_1_1; var S,Sr: string; i: integer; begin writeln (’Введите строку’); readln (S); Sr := ’’; for i := 1 to ord(S[0]) do Sr := S[i]+Sr; writeln(Sr) end. Более эффективный способ решения задачи состоит в том, что результирующая строка заполняется посимвольно, как обычный массив. program S_1_2; var S,Sr: string; i,n: integer; begin writeln (’Введите строку’); readln (S); n := ord(S[0]); Sr[0]:= S[0]; {или Sr[0]:=chr(n);} 8

for i := 1 to n do Sr[i] := S[n-i+1]; writeln(Sr) end. Следует обратить внимание на использование одного из операторов

Sr[0]:=S[0] или Sr[0]:=chr(n). Таким образом устанавливается длина строки Sr равной длине строки S, так как в языке Pascal информация о текущей длине строки хранится в ее символе с нулевым индексом. Ниже приводится еще один вариант решения, в котором преобразованию подвергается исходная строка. Решение оформлено в виде процедуры S13( S ). Строка S является и входным, и выходным параметром. procedure S13(var S: string); var i, n: integer; C: char; begin n := ord(S[0]); for i := 1 to n div 2 do begin C := S[i]; S[i]:= S[n-i+1]; S[n-i+1]:= C end end; Контрольный пример Входные данные:

S=’строка для теста’

Выходные данные: S=’атсет ялд акортс’ 9

Пример 2. Дана строка, состоящая из строчных латинских букв, цифр, пробелов и знаков равенства. Для каждой цифры посчитать, сколько раз она встречается в строке. Решение оформлено c использованием процедуры S21( S, A). Входные параметры:

строка S.

Выходные параметры: массив А для хранения числа вхождений соответствующей цифры. Параметр для количества элементов в массиве не предусмотрен, так как количество элементов массива для данной задачи фиксировано и равно количеству цифр – 10. program S_2_1; type mas = array[’0’..’9’] of integer; {каждый элемент массива типа mas предназначен для хранения числа вхождений соответствующей цифры от 0 до 9} var S: string; Res: mas; j: char; procedure S21(var S: string; var A: mas); var n, i: integer; j: char; begin n := ord(S[0]); for j := ’0’ to ’9’ do A[j] := 0; for i := 1 to n do {если символ S[i] принадлежит множеству цифр} if S[i] in [’0’..’9’] then 10

A[S[i]] := A[S[i]]+1 end; begin writeln (’Введите строку’); readln (S); S21(S, Res); for j := ’0’ to ’9’ do writeln(’символ ’,j,’ встречается ’,Res[j],’ раз(а)’) end. В случае если тип данных множество еще не известен, проверку факта, что символ является цифрой, можно произвести следующим образом: if (S[i] >= ’0’) and (S[i] <= ’9’) then Контрольный пример Входные данные: S=’a=1 b=27 ccc=2227’ Выходные данные: A=(0,1,4,0,0,0,0,2,0,0) Результаты работы программы: символ 0 встречается 0 раз(а) символ 1 встречается 1 раз(а) символ 2 встречается 4 раз(а) символ 3 встречается 0 раз(а) символ 4 встречается 0 раз(а) символ 5 встречается 0 раз(а) символ 6 встречается 0 раз(а) символ 7 встречается 2 раз(а) символ 8 встречается 0 раз(а) символ 9 встречается 0 раз(а)

11

Упражнения 1) Измените вывод в программе S_2_1 таким образом, чтобы выводились значения только для тех цифр, которые встречаются в строке S. 2) Для каждой строчной латинской буквы определите, сколько раз она встречается в строке. Пример 3. Дана строка. Напечатать в алфавитном порядке все различные латинские строчные буквы этой строки. Задача имеет красивое и короткое решение. Для его реализации в качестве основного организуется цикл по всем латинским строчным буквам, так как в таблице символов (ACSII или Unicode) они упорядочены по алфавиту. program S_3_1; var n, k, i: integer; S: string; begin writeln (’Введите строку’); readln (S); n := ord(S[0]); for i := ’a’ to ’z’ do begin k := 1; while (k<=n) and (S[k]<>i) do k := k+1; if k <= n then write(i,’ ’) end; writeln end. 12

Выход из цикла while (k<=n) and (S[k]<>i) do происходит, если закончились символы строки или найден символ, совпадающий с символом i. По умолчанию компилятор языка Pascal проверяет первое условие и если оно истинно, то только тогда проверятся второе. Если неизвестен порядок проверки условий, то необходимо обезопасить решение от выхода за границу строки (k уже больше n, но проверяется S[k]<>i). Тогда можно использовать логическую переменную flag. program S_3_2; var n, k, i: integer; s: string; flag: boolean; {признак отсутствия буквы в строке} begin writeln (’Введите строку’); readln (S); n := length(S); for i := ’a’ to ’z’ do begin k := 1; flag := true; while (k<=n) and flag do if S[k] = i then flag := false else k := k+1; if not flag then write(i,’ ’) end; writeln end. 13

Пример 4. Даны строки S, S1 и символ C. Вставить в строку S перед каждым символом C строку S1. Решение оформлено в виде процедуры S41( S, S1, C ). Входные параметры: строки S, S1, C. Выходные параметры: строка S. procedure S41(var S, S1: string; C: char); var i, j, k, n: integer; begin k:= ord(S1[0]); n:= ord(S[0]); i := 1; while i <= n do{повторять, пока не закончилась строка S} begin if S[i]=C then begin {сдвиг вправо элементов от очередного символа C до конца строки S} for j:=n downto i do S[j+k] := S[j]; n := n+k; S[0] := chr(n); {увеличить длину строки} {вставить на освободившееся место символы строки S1} for j:= 1 to k do S[i+j-1] := S1[j]; i := i+k end; i := i+1 end end; 14

3 ИСПОЛЬЗОВАНИЕ СТАНДАРТНЫХ ПРОЦЕДУР И ФУНКЦИЙ Пример 5. Дана строка. Напечатать в алфавитном порядке все различные латинские прописные буквы этой строки. Для решения задачи используется не посимвольная обработка строки S, как в примере 3, а стандартная функция pos (см. Приложение). program S_5_1; var k, i: integer; S: string; begin writeln (’Введите строку’); readln (S); for i := ’A’ to ’Z’ do begin k := pos(i,S); if k > 0 then write(i,’ ’) end; writeln end. Пример 6. Даны строки S, S1, S2. Заменить в строке S все вхождения подстроки S1 подстрокой S2. Решение оформлено в виде процедуры S61( S, S1, S2). Входные параметры: строки S, S1, S2. Выходные параметры: строка S. 15

procedure S61(var S, S1, S2: string); var n, k: integer; begin n := length (S1); k := pos (S1, S); {k – позиция первого вхождения S1 в S} while k <> 0 do {повторять, пока S1 входит в S} begin {удалить в строке S с k-ой позиции n символов} delete (S, k, n); {вставить строку S2 в строку S с k-ой позиции} insert (S2, S, k); k := pos (S1, S) end end; Способ решения, реализованный в процедуре S61, предполагает, что заменяемая строка S1 не содержится в строке S2. В противном случае получим либо зацикливание, либо просто неверное решение. Способ решения, реализованный в процедуре S62, корректно решает поставленную задачу при любых исходных данных. Результат формируется в новой строке Sr. Входные параметры: строки S, S1, S2. Выходные параметры: строка Sr. procedure S62(var S, S1, S2, Sr: string); var n, k: integer; begin n := length (S1); Sr:=’’; k := pos (S1, S); {k – позиция первого вхождения S1 в S} 16

while k <> 0 do {повторять, пока S1 входит в S} begin {добавить в Sr все символы S до первого вхождения S1} Sr := Sr+copy(S,1,k-1); {удалить из S первое вхождение S1 и все символы до него} delete (S, 1, k+n-1); Sr := Sr+S2; {добавить S2 в строку Sr вместо S1} k := pos (S1, S) end; Sr := Sr+S {добавить в строку Sr остаток строки S} end; Пример 7. Даны строки S, S1 и символ C. Вставить в строку S перед каждым символом C строку S1. Эта задача может быть решена с использованием посимвольной обработки строки S, как в процедуре S41( S, S1, C ) примера 4. Другой вариант решения задачи использует стандартные процедуры и функции обработки строк (см. Приложение) и оформлен в виде процедуры

S71( S, S1, Sr, C ). Результат формируется в новой строке Sr. Входные параметры: строки S, S1, C. Выходные параметры: строка Sr. procedure S71(var S, S1, Sr: string; C: char); var k: integer; begin Sr:=’’; k := pos (C, S); {k - позиция первого вхождения C в S} 17

while k <> 0 do {повторять, пока C входит в S} begin {добавить в строку Sr все символы до первого вхождения C} Sr := Sr+copy(S,1,k-1); {удалить из S все символы до первого вхождения C и C} delete (S, 1, k); {вставить в строку Sr строку S1 и символ C} Sr := Sr+S1+C; k := pos (C, S) end; Sr := Sr+S; {добавить в строку Sr остаток строки S} end; Упражнения 1) Проверьте корректность выполнения кода фрагмента программы для удаления концевых пробелов в строке S: readln(S); n := length(S); while S[n]=’ ’ do n := n-1; S[0] := chr(n); для следующих тестовых данных а) S1= ’6.000asd’

(-символ пробела)

б) S2=’’ (ровно 32 пробела) 2) Исправьте код, чтобы он работал корректно для любых входных данных.

18

Пример 8. Дана строка S. Удалить «лишние» пробелы в строке, то есть удалить начальные, концевые пробелы, и внутри строки не должно быть несколько пробелов подряд. Первый вариант решения использует стандартные процедуры и функции (см. Приложение) и оформлен в виде процедуры S81( S, Sr ). Результат формируется в новой строке Sr. procedure S81(var S, Sr: string); var p:integer; begin Sr:=S; if Sr <>'' then begin p:=pos('

',Sr);

{повторять, пока есть два подряд идущих пробела} while p<>0 do begin delete(Sr,p,1); {удалить первый из двух пробелов} p:=pos('

',Sr)

end; {если первый символ Sr - пробел, то удалить его} if Sr[1]=' ' then delete(Sr,1,1); if Sr<>'' then {если последний символ Sr - пробел, то удалить его} if Sr[length(Sr)]=' ' then delete(Sr,length(Sr),1) end end; 19

Второй вариант решения оформлен в виде функции S82( S ) и использует посимвольную обработку строки S с формированием новой строки Sr : в строку

Sr копируется символ строки S, если он не является пробелом, либо он – пробел, но предыдущий символ таковым не был. function S82(var S: string): string; var Sr : string; i,j:integer;

{текущие индексы строк S и Sr }

flag: boolean; {признак того, что предыдущий символ является пробелом} begin Sr:=’’; flag: = true; j:=0; for i:=1 to ord(S[0]) do begin {если предыдущий символ или текущий символ – не пробел} if not flag or (S[i]<>’ ’) then begin j:=j+1; Sr[j]:=S[i] end; {flag = true, если предыдущий символ является пробелом} flag:= S[i]= ’ ’ end; {если последний символ – пробел, то удалить его} if Sr[j]= ’ ’ then j:=j-1; Sr[0]:=chr(j); S82:=Sr end; 20

4 ОБРАБОТКА СЛОВ Пример 9. Дана строка, состоящая из слов – последовательностей символов, отличных от пробела и разделённых произвольным количеством пробелов. В начале и в конце строки, состоящей из слов, может быть произвольное количество пробелов. Вывести на печать все слова в порядке их следования в строке. При выполнении заданий на анализ и преобразование слов главная проблема заключается в выделении каждого слова из исходной строки. Опишем алгоритм выделения слов. Ищется первый «непробел» в строке – это будет начало первого слова. Далее в цикле до конца строки повторяются следующие действия: – ищется конец слова (первый пробел после слова или конец строки), – пропускаются пробелы до первого «непробела» (начала следующего слова) или до конца строки. Приведем вариант программы без использования стандартных процедур и функций для работы со строками. program S_9_1; var n, k, i: integer; S, S1: string; {строка и слово} begin writeln (’Введите строку’); readln (S); n := ord(S[0]); i := 1; {пропуск пробелов – поиск начала первого слова} 21

while (i<=n) and (S[i]=’ ’) do i := i+1; while i<=n do {повторять, пока не конец строки S} begin k := i; {запомнить начало текущего слова} S1 := ’’; while (i<=n) and (S[i]<>’ ’) do begin S1 := S1+S[i]; i := i+1;

{ поиск конца текущего слова}

end; writeln(S1); {вывод слова} {пропуск пробелов – поиск начала следующего слова} while (i<=n) and (S[i]=’ ’) do i := i+1 end end. Формировать очередное слово можно не только с помощью операции конкатенации, но и используя функцию копирования строки. Пример 10. Дана строка, состоящая из слов (см. Пример 9). Посчитать количество слов в строке. При обработке слов в строке не всегда возникает необходимость в их выделении. В этом случае может фиксироваться конец слова: либо текущий символ Si отличен от пробела, а следующий Si+1 является пробелом, либо Si – последний символ строки.

22

program S_10_1; var S:string; k:integer; function S101(var S: string):integer; var i,n,k:integer; begin n:= ord(S[0]); k:=0; for i:=1 to n do if(S[i]<>' ')and((i=n)or(S[i+1]=' ')) then k:=k+1; S101:=k end; begin writeln ('Введите строку'); readln (S); k:=S10l(S); writeln('Количество слов в строке =',k) end. Другой вариант подсчета числа слов в строке реализован в виде функции

S102( S ). Здесь логическая переменная flag определяет начало слова: либо начало строки, либо первый символ, отличный от пробела, следующий после пробела.

23

function S102(var S: string):integer; var i,n,k:integer; flag:boolean; {признак начала строки или пробела} begin n:= ord(S[0]); k:=0;flag:=true; for i:=1 to n do if S[i]=' ' then flag:=true else if flag then begin k:=k+1; flag:=false end; S102:=k end;

24

ЗАДАЧИ 1.

Дана строка. Посчитать количество пробелов в строке.

2.

Дано натуральное число N и символ C. Сформировать и вывести строку длины N, которая состоит из символов C.

3.

Дано натуральное число N и символы C1 и C2. Сформировать и вывести строку длины N, которая состоит из чередующихся символов C1 и C2.

4.

Дано целое число N (от 1 до 26). Сформировать и вывести строку из первых

N строчных букв латинского алфавита. 5.

Дана строка. Сформировать и вывести строку, содержащую те же символы, между которыми вставлено по одному пробелу.

6.

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

7.

Дана строка и символы C1 и C2. Преобразовать строку, заменив в ней каждый символ C1 символом C2.

8.

Дана строка. Преобразовать строку, заменив все строчные латинские буквы одноименными прописными.

9.

Дана строка. Зашифровать текст в строке, циклически сдвигая его вправо.

10. Дано целое число N и строка S. Преобразовать строку S в строку длины N следующим образом: если длина строки S больше N, то отбросить последние символы, если длина строки меньше N, то в ее конец добавить точки. 11. Дана строка и символ C. Выяснить, встречаются ли в данной строке последовательность из трех стоящих рядом символом C. 12. Дана строка. Выяснить, является ли данная строка правильной записью идентификатора. 25

13. Дана строка, содержащая латинские буквы и скобки трех видов: "()", "[]", "{}". Если скобки расставлены правильно (то есть каждой открывающей соответствует закрывающая скобка того же вида), то вывести число 0. В противном случае вывести или номер позиции, в которой расположена первая ошибочная скобка, или, если закрывающих скобок не хватает, число –1. 14. Дана строка. Выяснить, является ли заданная строка палиндромом. Решить задачу двумя способами: 1)

в два прохода по строке;

2)

в один проход по строке.

Палиндром – слово или текст (в этом случае пробелы игнорируются), одинаково читающийся слева направо и справа налево (например, «казак» или «а луна канула»). 15. В заданной строке найти наибольшее количество цифр, идущих в нём подряд. 16. Дана строка, изображающая двоичную запись целого числа. Сформировать и вывести строку, изображающую десятичную запись этого же числа. 17. Дана строка, изображающая десятичную запись целого числа. Сформировать и вывести строку, изображающую двоичную запись этого же числа. 18. Дана строка. Вывести позицию первого вхождения заданного символа. Если символ отсутствует в строке, вывести сообщение об этом. 19. Дана строка. Вывести позицию первого вхождения заданной подстроки. Если подстрока отсутствует в строке, вывести сообщение об этом. 20. Дана строка. Вывести позицию последнего вхождения заданного символа. Если символ отсутствует в строке, вывести сообщение об этом. 21. Дана строка. Вывести позицию последнего вхождения заданной подстроки. Если подстрока отсутствует в строке, вывести сообщение об этом. 22. Даны строки S1 и S2. Проверить, имеются ли в строке S1 все символы, входящие в строку S2. 26

23. Дана строка, содержащая полное имя файла (полный путь, имя и расширение). Выделить из этой строки имя файла с расширением. 24. Дана строка, содержащая полное имя файла (полный путь, имя и расширение). Выделить из этой строки имя файла без расширения. 25. Дана строка, содержащая полное имя файла (полный путь, имя и расширение). Выделить из этой строки имя первого каталога. Если файл содержится в корневом каталоге, то вывести символ «\». 26. Дана строка, содержащая полное имя файла (полный путь, имя и расширение). Выделить из этой строки имя последнего каталога. Если файл содержится в корневом каталоге, то вывести символ «\». 27. Дана строка. Напечатать первые вхождения каждой буквы латинского алфавита. 28. Дана строка, содержащая слова из латинских букв, соседние слова отделены друг от друга запятой, за последним словом – точка. Найти количество букв в самом длинном слове. 29. Дана строка, содержащая запись вещественного числа в формате «мантисса – порядок» (например, 6.67E-001 или –2.3456E+003). Получить строку, содержащую число в формате с фиксированной точкой. 30. Дана строка, содержащая запись вещественного числа в формате с фиксированной точкой. Получить строку, содержащую число в формате «мантисса – порядок». 31. Дана строка. Удалить из нее все вхождения заданного символа. 32. Дана строка и два целых числа k и r (k < r). Удалить из нее все символы, расположенные между символами с номерами k и r. 33. Даны строки S, S1. Удалить последнее вхождение подстроки S1 в строке S. 34. Даны строки S, S1, S2. Вставить в строку S перед каждым вхождением строки S1 строку S2. 27

35. Даны строки S, S1, S2. Вставить в строку S после каждого вхождения строки

S1 строку S2. Указание к решению задач 36-45

Словом будем называть последовательность символов, отличных от пробела и разделённых произвольным количеством пробелов. В начале и в конце строки, состоящей из слов, может быть произвольное количество пробелов. 36. Дана строка, состоящая из слов. Получить новую строку из последних символов всех слов исходной строки. 37. Дана строка, состоящая из слов. Найти: 1)

номер первого по порядку слова, начинающегося с заданного символа;

2)

среднее арифметическое длин всех слов и слово, длина которого наиболее близка к среднему.

38. Дана строка, состоящая из слов. Проверить, совпадают ли в нем первое и последнее, второе и предпоследнее и т.д. слова. 39. Дана строка, состоящая из слов. Вывести слова, в которых нет повторяющихся символов. 40. Дана строка, состоящая из слов. Преобразовать все слова по правилу: 1)

заменить в слове все последующие вхождения его первого символа на символ «.» (количество пробелов между словами не изменять);

2)

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

41. Дана строка, состоящая из слов. Вывести: 1)

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

2)

те слова, которые не нарушают лексикографический (алфавитный) порядок в строке.

28

42. Дана строка, состоящая из слов. Изменить порядок следования слов на обратный без использования дополнительных строк. 43. Дана строка, состоящая из слов. 1)

удалить все вхождения k-го по счету слова;

2)

оставить только первое вхождение первого слова;

3)

оставить только последнее вхождение k-го по счету слова;

4)

поменять местами два слова с заданными номерами;

5)

оставить только первое вхождение каждого слова;

6)

оставить только последнее вхождение каждого слова;

7)

удалить слова, встречающие более одного раза;

8)

для каждого из слов указать, сколько раз оно встречается среди слов строки.

44. Даны две строки, состоящие из слов. Объединить строки в новую строку, чередуя слова из первой и второй строк. Если одна из строк длиннее другой, то все оставшиеся слова добавьте в конец новой строки. В новой строке начальных и конечных пробелов нет, между словами по одному пробелу. 45. Даны две строки, состоящие из слов. Для них найти 1)

множество всех слов, встречающихся в каждой строке;

2)

самое длинное общее слово обеих строк;

3)

самое короткое слово первой строки, которого нет во второй.

29

ИНДИВИДУАЛЬНЫЕ ЗАДАНИЯ Задание 1 При выполнении заданий необходимо применить только посимвольную обработку строк. 1.

Дана строка. Посчитать общее число латинских букв (строчных и прописных), входящих в строку.

2.

Дана строка. Посчитать количество символов, отличных от цифр и пробела.

3.

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

4.

Дана строка, содержащая буквы, цифры и знаки арифметических операций «+», «-», «*», «/». Выяснить, каких символов в строке больше: букв, цифр или знаков.

5.

Дана строка, содержащая текст. Зашифровать текст, циклически сдвигая его влево.

6.

Дано целое число N (от 1 до 26). Сформировать строку из N последних прописных букв латинского алфавита в обратном порядке.

7.

Дана строка. Вывести строку, содержащую те же символы, между которыми вставлено по N символов «*».

8.

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

9.

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

30

10. Дана строка, содержащая слова из латинских букв; соседние слова отделены друг от друга запятой, за последним словом – точка. Определить количество слов, которые оканчиваются заданной буквой. 11. Дана строка и символы C1 и C2 . Выяснить, имеется ли в строке пара соседствующих символов C1 и C2 или C2 и C1. 12. В заданной строке найти наибольшее количество латинских букв, идущих в нём подряд. 13. Даны строка S и символ C. Найти номер первого символа строки, для которого этот символ и следующий совпадают с заданным символом C. 14. Дана строка, изображающую десятичную запись целого числа. Сформировать и вывести строку, изображающую восьмеричную запись этого же числа. 15. Дана строка, изображающую десятичную запись целого числа. Сформировать и вывести строку, изображающую шестнадцатеричную запись этого же числа. 16. Дана строка, изображающую двоичную запись целого числа. Сформировать и вывести строку, изображающую восьмеричную запись этого же числа (без перевода в десятичную систему). 17. Дана строка, изображающую двоичную запись целого числа. Сформировать и вывести строку, изображающую шестнадцатеричную запись этого же числа (без перевода в десятичную систему). 18. Дана строка, изображающую восьмеричную запись целого числа. Сформировать и вывести строку, изображающую двоичную запись этого же числа (без перевода в десятичную систему). 19. Дана строка, изображающую шестнадцатеричную запись целого числа. Сформировать и вывести строку, изображающую двоичную запись этого же числа (без перевода в десятичную систему). 20. Сформировать и вывести строку, содержащую следующую последовательность цифр 122333 ... 99...9. 31

21. Сформировать и вывести строку, содержащую следующую последовательность цифр 988777 ... 11...1. 22. Сформировать и вывести строку, содержащую следующую последовательность цифр 123...923...9 ... 899. 23. Сформировать и вывести строку, содержащую следующую последовательность цифр 987...187...1 ... 211. 24. Дана строка. Выяснить, является ли строка правильной записью положительного целого числа в десятичной системе счисления. 25. Дана строка. Выяснить, является ли строка правильной записью произвольного целого числа в десятичной системе счисления. Задание 2 Задания выполнять в двух вариантах: 1) с использованием стандартных процедур и функций для работы со строками; 2) используя посимвольную обработку строк. 1.

Дано целое число N и строка S. Преобразовать строку S в строку длины N следующим образом: если длина строки S больше N, то отбросить первые символы, если длина строки меньше N, то в ее начало добавить точки.

2.

Даны целые числа N1 и N2 и строки S1 и S2. Получить из этих строк новую строку, содержащую первые N1 символов строки S1 и последние N2 символов строки S2 в указанном порядке.

3.

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

4.

Дана строка. Удалить из нее все четные вхождения заданного символа.

32

5.

Дана строка S и символ C. Удалить из нее все символы, расположенные между первым и последним вхождением заданного символа C.

6.

Дана строка S и символ C. Удалить из нее все символы, расположенные между предпоследним и последним вхождением заданного символа C.

7.

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

8.

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

9.

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

10. Дан строка S и символ C. Утроить каждое вхождение символа C в строку S. 11. Даны строки S, S1, S2. Вставить в строку S перед первым и последним вхождением строки S1 строку S2. 12. Даны строки S, S1, S2. Вставить в строку S после первого и последнего вхождения строки S1 строку S2. 13. Даны строки S, S1, S2. Вставить в строку S перед k-м вхождением строки S1 строку S2. Если k-ое вхождение не обнаружено, то оставить строку без изменений. 14. Даны строки S, S1, S2. Вставить в строку S после k-го вхождения строки S1 строку S2. Если k-ое вхождение не обнаружено, то оставить строку без изменений. 15. Даны строки S, S1, S2. Заменить в строке S последнее вхождение строки S1 строкой S2. 16. Даны строки S, S1. Удвоить каждое вхождение строки S1 в строке S.

33

17. Дана строка. Заменить каждую точку многоточием. 18. Дана строка. Заменить каждую из групп стоящих подряд точек одной точкой. 19. Дана строка. Удалить символы, заключенные между первой и последней группами цифр. 20. Дана строка, содержащая слова из латинских букв, соседние слова отделены друг от друга запятой, за последним словом – точка. Удалить слова, в которых заданная буква встречается не менее, чем заданное число раз. 21. Дана строка, содержащая слова из латинских букв, соседние слова отделены друг от друга запятой, за последним словом – точка. Заменить слова, в которых заданная буква встречается заданное число раз, этой буквой. 22. Дана строка, содержащая слова из латинских букв, соседние слова отделены друг от друга запятой, за последним словом – точка. Удалить слова, в которых количество букв четное. 23. Дана строка, содержащая слова из латинских букв, соседние слова отделены друг от друга запятой, за последним словом – точка. Удалить слова – палиндромы. 24. Дана строка, содержащая слова из латинских букв, соседние слова отделены друг от друга запятой, за последним словом – точка. Удалить самое короткое слово (первое и последнее, если их несколько). 25. Дана строка, содержащая слова из латинских букв, соседние слова отделены друг от друга запятой, за последним словом – точка. Удалить самое длинное слово (все, если их несколько).

34

Задание 3

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

Выдать слова, имеющие заданную длину, и посчитать их количество.

2.

Выдать слова, состоящие из нечетного количества символов, и посчитать их количество.

3.

Выдать слова, начинающиеся и оканчивающиеся одним и тем же символом, и посчитать их количество.

4.

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

5.

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

6.

Выдать слова, начинающиеся двумя любыми латинскими буквами, и посчитать их количество.

7.

Выдать слова, содержащие максимальное количество цифр, и посчитать их количество.

8.

Выдать слова, в которых доля цифр максимальна, и посчитать их количество.

9.

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

10. Выдать все слова максимальной длины. 11. Выдать все слова минимальной длины. 12. Найти первое из слов, содержащих не более заданного количества символов. 13. Найти последнее из слов, содержащих не менее заданного количества символов.

35

14. Выдать все слова, поменяв в каждом порядок следования символов на обратный. 15. Выдать слова, в которых буквы упорядочены по алфавиту. 16. Выдать слова, в которых латинские буквы чередуются с цифрами. 17. Преобразовать в строке все слова по правилу: перенести последний символ в начало слова. 18. Преобразовать в строке все слова по правилу: если слово нечетной длины, то удалить его первый символ. 19. Преобразовать в строке все слова по правилу: удалить из слова k-ый по счету символ. 20. Преобразовать в строке все слова по правилу: удалить из слова все последующие вхождения первого символа. 21. Преобразовать в строке все слова по правилу: удалить из слова все предыдущие вхождения k-ого по счету символа. 22. Преобразовать в строке все слова по правилу: оставить в слове только первые вхождения каждого символа. 23. Преобразовать в строке все слова по правилу: оставить в слове только последние вхождения каждого символа. 24. Удалить в строке каждое четное слово. 25. Удалить в строке все вхождения первого слова.

36

ПРИЛОЖЕНИЕ Процедуры и функции обработки строк Процедуры Процедура Delete procedure Delete(var S:string; p,k:integer); Удаляет из строки S подстроку из k символов, начиная с позиции p. Если номер первого удаляемого символа p больше длины строки, то символы не удаляются. Если символов в строке недостаточно, удаляется остаток символов. Процедура Insert procedure Insert(S1:string; var S:string; p:integer); Вставляет подстроку S1 в строку S, начиная с позиции p. Если получается строка слишком большой длины, то она усекается до 255 символов. Процедура Str procedure Str(X[:M[:N]]; var S:string); Преобразует выражение X вещественного или целого типа в строку S. Необязательные параметры M и N – форматы вывода целого типа. Процедура Val procedure Val(S:string; var X; var code:integer); Преобразует символьное представление числа ( строку S ) в значение переменной X вещественного или целого типа. В случае правильного представления числа в строке S параметр code принимает значение 0. Если представление числа в строке S неправильное, то параметр code принимает значение номера (позиции) неправильного символа в строке S; в этом случае содержимое X не меняется.

37

Функции Функция Concat function Concat (S1 [,S2,…,Sn]):string; Объединяет несколько строк в одну строку (при необходимости усекает строку до 255 символов). Функция Copy function Copy (S:string; p:integer; k:integer):string; Выделяет из строки S, начиная с позиции p, подстроку из k символов. Если номер первого удаляемого символа p больше длины строки, то возвращается пустая строка. Если символов в строке недостаточно, возвращается остаток строки. Функция Length function Length (S:string):integer; Возвращает текущую длину строки S. Функция Pos function Pos (S1,S:string):byte; Возвращает позицию первого вхождения подстроки S1 в строку S (номер первого символа строки S, с которого начинается последовательность символов S1) или 0, если подстрока S1 не входит в строку S. Функции для работы с символами: Функция UpCase function UpCase (C:char):char; Преобразует строчную латинскую букву в прописную. Если значением C является любой другой символ, то преобразования не происходит. function ord(C: char): byte Возвращает код символа C. function chr(X: byte): char Возвращает символ c кодом X. 38

ЛИТЕРАТУРА 1 Джонс Ж., Харроу К. Решение задач в системе Турбо Паскаль. – М.: Финансы и статистика, 1991. – 720с. 2 Задачи по программированию. / Абрамов С.А. и др. – М.: Наука, 1988. – 224 с. 3 Задачи по программированию. / Амелина Н.И. и др. – М.: Вузовская книга, 2000. – 104 с. 4 Касьянов В.Н., Сабельфельд В.К. Сборник заданий по практикуму на ЭВМ. Учебное пособие для вузов. – М.: Наука, 1988. – 272 с. 5 Методы программирования. Учебное пособие / Минакова Н.И., Невская Е.С., Угольницкий Г.А., Чекулаева А.А., Чердынцева М.И. – М.: Вузовская книга, 1999. – 280 с. 6 Пильщиков В.Н. Сборник упражнений по языку Паскаль. – М.: Наука, 1989. – 160 с.

39