Лабораторная работа №10
Разработка алгоритмов и программ обработки строк. Использование множеств для решения задач
Цель работы: научиться составлять алгоритмы и программы обработки строк, научиться использовать множества для решения задач.
Теоретические сведения
Copy (st,p,n) – из строки st копируется n символов в память, начиная с позиции p.
Delete (st,p,n) – Из строки st удаляется n символов, начиная с p.
Insert(st1,st2,p) – Вставить строку st1 в st2, начиная с позиции p.
Length (st) – Вычисляет длину строки st.
Pos (st1,st2) – Находит позицию первого появления строки st1 в строке st2.
Str(n,st) – Процедура перевода цел. переменной n в строку st.
Val(st,n,m) – Процедура переводит содержимое строки st в целочисленную переменную n, причем m – номер ошибочного символа.
UpCase (Ch) — преобразует строчную букву в прописную. Обрабатывает буквы только латинского алфавита.
Concat (Strl,Str2,...,StrN) — выполняет сцепление строк Strl, Str2,..,StrN в том порядке, в каком они указаны в списке параметров. Сумма символов всех сцепленных строк не должна превышать 255.
d:=copy(a,x,y) функция, возвращает копию из y (integer) знаков части строки a (string), начиная с позиции x (integer). Формат: d:=copy(a,x,y). Результат записывается в переменную d, например:
a:='бегемот';
d:=copy(a,5,3);
writeln(d);
результат - мот
delete(a,x,y) процедура, удаляет y (integer) знаков части строки a (string), начиная с позиции x (integer). Формат: delete(a,x,y). Результат записывается в переменную а, например:
a:='антрекот';
delete(a,1,5);
writeln(а);
результат - кот
insert(a,b,x) процедура, вставляет строку a (string) в строку b (string), в позицию x (integer). Формат: insert(a,b,x). Результат записывается в переменную b, например:
b:='коледж';
a:='л'
insert(a,b,3);
writeln(b);
результат - колледж
x:=pos(a,b) функция, возвращает номер позиции, с которой располагается подстрока а (string), в строке b (string). Формат: x:=pos(a,b). Результат записывается в переменную x, например:
b:='колледж';
a:='л'
x:=pos(a,b);
writeln(b);
результат – 3
x:=length(a) функция, возвращает длину строки а (string). Например:
a:='школа';
x:=length(a);
writeln(x);
результат 5.
x:=ord(a) функция, возвращает цифровой код символа а (char). Например:
a:='Й';
x:=ord(a);
writeln(x);
результат 137
a:=chr(x) функция, возвращает символ а (char) по его цифровому коду. Например:
х:=137;
a:=chr(x);
writeln(а);
результат - Й.
| Значение Str | Выражение | Результат |
| 'абвгде' 'река Волга' | Delete(Str, 4, 2); Delete(Str, 1, 5); | 'абве' 'Волга' |
| Значение St | Выражение | Результат |
| 'ABCDEFG' 'ABCDEFG' | Copy(St, 2, 3) Copy(St, 4, 10) | 'BCD' 'DEFG' |
| Значение St | Выражение | Результат |
| '123456789' 'System 370' | Length(St) Length(St) |
| Значение Str1 | Выражение | Результат |
| 'abcdef ' 'abcdef' | Pos('de',Strl) Pos('r',Strl) |
| Значение Ch | Выражение | Результат |
| 'd' | UpCase(Ch) | 'D' |
| Выражение | Результат |
| Concat('AA','XX','Y') Соnсаt('Индекс','394063') | 'AAXXY' 'Индекс 394063' |
Множества
Объединение
1) [‘A’, ‘F’]+[‘B’, ‘D’] = [‘A’, ‘F’, ‘B’, ‘D’];
2) [1..3, 5, 7, 11] + [3..8, 10, 12, 15..20] = [1..8, 10..12, 15..20]
Пусть S1:=[1..5, 9], a S2:=[3..7, 12]. Тогда если S:=S1 + S2, то S=[1..7, 9, 12].
Пусть А1:=[‘a’..’z’]; A1:=A1 = [‘A’]. Тогда A1=[‘A’, ‘a’..’z’].
Пересечение
1) [‘A’, ‘F’]*[‘B’, ‘D’] = [ ], так как общих элементов нет;
2) [1..3, 5, 7, 11]*[3..8, 10, 12, 15..20] = [3, 5, 7];
3) если S1:=[1..5, 9] и S2:=[3..7, 12], a S:=S1 * S2, то S=[3..5].
Разность
1) [‘A’, ‘F’] - [‘B’, ‘D’] = [‘A’, ’F’ ], так как общих элементов нет;
2) [1..3, 5, 7, 11] - [3..8, 10, 12, 15..20] = [1, 2, 11];
3) если S1:=[1..5, 9] и S2:=[3..7, 12], a S:=S1 - S2, то S=[1, 2, 9];
4) A1:=[‘A’..’Z’]; A1:=A1 - [‘A’]. Тогда А1=[‘B’..’Z’].
Логическая операция определения принадлежности элемента множеству обозначается служебным словом in. Результат операции имеет значение true, если элемент входит в множество, и false в противном случае.
Примеры.
1) Выражение 5 in [3..7] имеет значение true, так как 5 принадлежит [3;7];
2) Выражение ‘a’ in [‘A’..’Z’] имеет значение false, так как маленькой латинской буквы «а» нет среди больших латинских букв.
Задания:
1. Слова и фразы, которые можно читать справа налево и слева направо. Такие слова или фразы называются перевертыши или палиндромы. Например, ШАЛАШ, РОТОР.
Данная программа проверяет, является ли слово палиндромом. При вводе выражения пробелы не вводить.
program palindrom;
uses crt;
var q:integer;
a,b,c:string;
begin
clrscr;
writeln('Введите слово - палиндром ');
readln(a);
for q:=1 to length(a) div 2 do {проверка до середины слова}
begin
b:=copy(a,q,1); {очередная буква слева}
c:=copy(a,length(a)+1-q,1); {соответствующая буква справа}
if b<>c then
write('Это не палиндром!!!');
end;
write('Правильно.');
end.
Исправьте программу.
2. Если выражение состоит из нескольких слов, то нужно, чтобы компьютер анализировал наличие пробелов. Это реализовано в следующей программе:
program palindrom2;
uses crt;
var q:integer;
a:string;
begin
clrscr;
write('Введите фразу ');
readln(a);
{==========Алгоритм удаления пробелов===========}
for q:=1 to length(a) do
if copy(a,q,1)=' ' then delete(a,q,1);
{============================================}
for q:=1 to length(a) div 2 do
begin
if copy(a,q,1)<>copy(a,length(a)+1-q,1) then
write('Это не палиндром, вот пример палиндрома: "аргентина манит негра"');
end;
write('Правильно.');
end.
Исправьте программу.
3. Составить программу выделения следующих множеств из множества целых чисел от 1 до 30:
- множество чисел, кратных 2;
- множество чисел, кратных 3.
Program Example_1;
Const n=30;
Type mn=set Of 1..n;
Var n2, n3:mn;
{n2 — множество чисел, кратных 2, n3 — кратных 3}
k:Integer;
Procedure Print(m:mn);
Var i:Integer;
Begin
For i:=1 To n Do
If i In m Then Write(i:3);
Writeln;
End;
Begin
n2:=[ ]; n3:=[ ];
{ начальное значение множеств}
For k:=1 To n Do { формирование n2 и n3}
Begin
{если число делится на 2, то заносим его в n2}
If k Mod 2=0 Then n2:=n2+[k];
{если число делится на 3, то заносим его в n3}
If k Mod 3=0 Then n3:=n3+[k];
End;
{вывод множеств}
Writeln (' числа, кратные 2');
Print(n2);
Writeln (' числа, кратные 3');
Print(n3);
Readln;
End.
На основании представленной программы составьте программу для выделения следующих множеств:
- множество чисел, кратных 6;
- множество чисел, кратных 2 или 3.
quot;Решето Эратосфена". Составить программу поиска простых чисел в промежутке [1;n]. число n вводиться с клавиатуры.
Решение
Простым называется число, которое не имеет других делителей, кроме единицы и самого этого числа. Для решения этой задачи воспользуемся методом "решета Эратосфена", идея которого заключается в следующем: сформируем множество М, в которое поместим все числа заданного промежутка. Затем последовательно будем удалять из него элементы, кратные 2, 3, 4 и так далее, до [n/2] (целая часть числа). После такого "просеивания" в множестве М останутся только простые числа.
Program Example_3;
Var m:Set Of Byte;
i, k, n: Integer;
Begin
Writeln('введите размер промежутка (до 255)');
Readln(n);
m:=[2..n];{начальное значение}
For k:=2 To n Div 2 Do
{перебираем все делители}
For i:=2 To n Do
{если число кратное делителю k и отлично от него}
If (i Mod k=0) And (i<>k) Then m:=m-[i];
{Распечатаем оставшиеся элементы}
For i:=1 To n Do If i In m then Write (i:3);
Readln;
End.
4. Из числовых переменных, равных 4, 7, 9 с помощью строковых функций получить число 794 и вывести его на экран.
5. Из слова "ВЕЛИКОЛЕПНЫЙ" с помощью строковых функций получить слова: ВЕЛИК, КОЛ, ЛИК, ЛЕВ, ВЕК, вывести их на экран и определить их длину.
6. Из диапазона целых чисел m..n выделить множество чисел делящихся без остатка или на k, или на р (k, р –простые).
7. Дан текст из строчных латинских букв, за которым следует точка. Напечатать все буквы, входящие в текст по одному разу.
***. Даны три множества Х1, Х2, Х3, содержащие целые числа. Введите их с клавиатуры. Мощность каждого равна 10. Сформируйте новое множество Y=(Х1+Х2)-(Х3*Х2). Выведите на экран множество Y и его мощность. Проверьте, есть ли во множестве числа кратные 5.
