Строки
| Вид материала | Методические указания |
- Домашнее задание 3 по дисциплине "Программирование на языке высокого уровня, 25.78kb.
- Абаева Л. Л. Культ гор и буддизм в Бурятии, 10.07kb.
- Требования к оформлению электронных версий документов оформление тезисов, 198.21kb.
- Доклад печатается шрифтом "Times New Roman", 35.06kb.
- § внутренняя политика александра I в 1801-1806, 306.63kb.
- Матрицы и операции над ними Определение. Матрицей, 49.36kb.
- Программа вычисления суммы элементов двумерного массива const, 28.23kb.
- Тема урока. Вершины музыкальной классики: новаторство П. И. Чайковского, 56.32kb.
- Я, Лабарна, вельможа посольств табарны Нессы и Хатуссы Тахурваили пишу эти строки., 816.56kb.
- Int needle len = strlen(needle), 25.05kb.
Оглавление
Оглавление 3
ВВедение 4
1 Строки 5
1.1 Определение и представление в памяти 5
1.2 Стандартные операции над строками 6
1.3 Поиск подстроки в строке 7
1.4 Операция вставить 12
1.5 Операция удалить 16
1.6 Обработка слов в строке 18
1.7 Обработка последовательности строк 20
1.8 Общие задания 24
1.9. Индивидуальные задания 24
2 Записи 28
2.1 Определение и представление в памяти 28
2.2 Типизированные константы-записи 31
2.3 Обработка элементов записи типа Person 32
2.4 Сортировка массива записей по различным ключам 34
2.5 Задания 37
Литература 45
ВВедение
Методические указания предназначены для студентов, изучающих программирование с использованием алгоритмического языка Pascal.
В методических указаниях подробно и последовательно рассмотрены две темы: строки и записи.
Основу методических указаний составляют примеры программ, позволяющие на практике изучить синтаксис языка, приёмы построения эффективных алгоритмов. По каждой теме имеются индивидуальные задания, упражнения для закрепления материала.
Первый раздел методических указаний содержит описание структуры данных – строка. Дается определение строки, представление строки в памяти компьютера и рассматриваются основные операции над строками. Кроме того, приводятся решения типовых задач обработки строковых данных. Второй раздел содержит описание структуры данных – запись. Также дается определение записи, представление записи в памяти компьютера. Запись – универсальная структура. Она дает возможность определять составные, или комбинированные типы данных. Методические указания содержат задачи обработки табличных данных. Предполагается, что таблица находится в текстовом файле. Описываются алгоритмы ввода элементов из текстового файла, вывода на экран, простая обработка табличных данных. Методические указания содержат список индивидуальных заданий для студентов по теме записи.
Большое количество самостоятельных заданий и готовых программ даёт возможность использовать методические указания в качестве учебного пособия. Методические указания могут быть использованы и как самоучитель.
1 Строки
1.1 Определение и представление в памяти
Строка, или цепочка литер (символов), – это конечная последовательность символов, принадлежащих конечному множеству символов, или алфавиту.
Строки хранятся в памяти ВМ в двоичном коде: каждому символу ставится в соответствие некоторое неотрицательное число, называемое кодом символа (код символа занимает один байт, то есть восемь двоичных разрядов).
Синтаксис описания переменных строкового типа:
type < имя типа> = string;
var <идентификатор> : <имя типа>;
или без описания типа:
var <идентификатор> : string;
Максимальная длина строки составляет 255 символов.
Например, S – переменная строкового типа. Описание будет иметь вид:
var S : string;
В конкретных задачах бывает невыгодно использовать максимальную длину строки, равную 255 символам. Язык Pascal предусматривает явное изменение в программе максимальной длины строки, а именно:
var name : string[10];
В этом случае максимальная длина строки name составляет 10 символов. Текущая длина строки name может меняться от 0 до10.
Например, после выполнения оператора
name = ‘Иван’;
строка name будет иметь длину, равную 4.
Если количество символов, определяющих строковое значение, превышает максимальную длину строки, то лишние символы игнорируются справа.
Например, после выполнения оператора
name = ‘Иван Иванович’;
строка получит значение ‘Иван Ивано’.
Строка представляет собой массив символов, поэтому к любому символу строки можно обратиться по индексу. Например, обращение name[1] указывает на символ ‘И’.
По нулевому индексу автоматически записывается текущая длина строки в символьном представлении. Значение длины строки можно получить, используя стандартную функцию ORD или LENGTH:
L := ORD(name[0]); или L := LENGTH(name);
Значение длины строки можно изменить, используя стандартную функцию CHR:
name[0] := CHR(4);
тогда строка будет иметь значение ‘Иван’.
1.2 Стандартные операции над строками
Над строковыми данными допустимы операции:
конкатенация (сцепление строк) +;
сравнение =,< >, < , >, <=, >=.
Сравнение выполняется посимвольно слева направо. Строки равны, если их длины равны и элементы строк посимвольно совпадают.
В языке Pascal для работы со строками имеются стандартные процедуры и функции.
Перечислим заголовки функций:
function ORD(c : char) : integer;
возвращает числовое значение символа c;
function CHR(n : integer) : char;
возвращает значение символа, соответствующее числу n;
function CONCAT(s1, s2, …, sn : string) : string;
возвращает конкатенацию заданных строк, а именно: s1 + s2 + … + sn;
function COPY(s:string;L:integer;N:integer) : string;
возвращает подстроку длины N, начинающуюся с позиции L в строке s;
если L > LENGTH(s), то результатом будет пробел;
если L >255, то возникнет ошибка выполнения;
function POS(s1, s : string) : integer;
возвращает индекс первого вхождения подстроки s1 в s;
если подстрока не найдена, возвращает значение 0.
Перечислим заголовки процедур.
procedure DELETE(var s : string;L:integer;N: integer);
удаляет из строки s подстроку длины N, начиная с позиции L;
procedure INSERT(s1:string;var s:string;L:integer);
вставляет подстроку s1 в строку s, начиная с позиции L;
procedure STR( x : <числовой тип>;var s : string);
преобразует числовое значение x в строку символов s;
procedure VAL(s:string; var x:<числовой тип>;
var cod: integer);
преобразует строку символов s в числовое значение x;
если преобразование прошло успешно, то cod=0;
если обнаружена ошибка (например, символ не является цифрой), то cod будет содержать номер позиции первого ошибочного символа и в этом случае значение переменной x не определено.
Обработка строковых данных сводится к выполнению операций поиска (выборки) и операций редактирования (изменение, вставка, удаление).
1.3 Поиск подстроки в строке
Задача 1. Заменить в строке заданную группу символов на другую группу символов.
Входные данные: s – строка;
s1 – cтрока для поиска;
s2 – cтрока для замены.
Выходные данные: s – измененная строка.
Метод решения
Необходимо найти позицию подстроки s1 в s (индекс k);
пока k ≠ 0 выполнить операции:
1) delete(s, k, < количество символов в подстроке s1>);
2) insert(s2, s, k);
3) найти очередную позицию подстроки s1 в s (индекс k);
Для поиска позиции воспользуемся функцией pos.
Решение задачи представим в виде процедуры.
procedure CHANGE(s1, s2 : string; var s : string);
var k, n : integer;
begin
n:=length(s1);
k:=pos(s1, s);
while k<>0 do
begin
delete(s, k, n);
insert(s2, s, k);
k:=pos(s1, s)
end
end;
Приведенный алгоритм решения задачи с использованием стандартных операций является кратким и понятным. Оценим сложность этого алгоритма.
Циклический процесс с заголовком
while k<>0 do
определяется количеством повторений s1 в s.
Операции delete соответствует циклический процесс, а именно, сдвиг символов строки s влево на длину подстроки s1. Операции insert тоже соответствует циклический процесс, а именно, сдвиг символов строки s вправо на длину подстроки s2.
Сложность сдвигов определяется длиной строки s, то есть O( length(s) ).
Наконец, операции pos соответствует более сложный циклический процесс. Н. Вирт в книге « Алгоритмы и структуры данных» предлагает несколько вариантов реализации этой операции: прямой поиск, алгоритм Кнута Мориса и Пратта и алгоритм Боуера и Мура.
Поиск подстроки в строке является типичным для любых систем обработки текстов, поэтому понятна заинтересованность в поиске эффективного алгоритма для этой задачи. Остановимся на алгоритме прямого поиска, кратком, понятном и достаточно эффективном для небольших строк. Опишем алгоритм прямого поиска в виде функции Index1.
function Index1(s1,s:string):integer;
var L,K: integer; { длины строк s и s1 }
i,j: integer; { индексы для просмотра строк s и s1 }
begin
K:=length(s1);
L:=length(s);
i:=1; j:=1;
while (i<=L) and (j<=K) do
begin
j:=1 ; i:=i+1 ;
while (j<=K) and (s [i+j-1]=s1[j]) do j:=j+1;
end;
if (j>k) then Index1:=i
else Index1:=0
end;
По аналогии с алгоритмом поиска в матрице внутренний циклический процесс можно сделать неявным. Тогда сокращается количество проверок во внутреннем цикле. Алгоритм представим в виде функции Index2.
function Index2(s1, s : string):integer;
var L,K : integer; { длины строк s и s1 }
i,j: integer; { индексы для просмотра строк s и s1 }
begin
L:=length(s); K:=length(s1);
i:=1; j:=1;
while (i<=L) and (j<=K) do
begin
if s[i+j-1] <> s1[j] then
begin j:=1; i:=i+1 end;
if s[i+j-1] = s1[j] then
j:=j+1
end;
if j>K then Index:=i else Index:=0
end;
Сложность этого алгоритма определяется O(L*K).
Реализация алгоритма задачи 1 без использования стандартных операций будет не эффективна с точки зрения размера алгоритма, а значит, и с точки зрения понимаемости алгоритма.
Задача 2. Поиск заданного символа в строке.
Входные данные: s – строка;
с – заданный символ.
Выходные данные: Ind - индекс символа c в s или Ind =0, если символа нет в строке.
Метод решения
Определим, что нужно найти, используя формальный язык:
( i:1 i n : s[i]= c) or ( i:1 i n : s[i] c),
где n – длина строки.
Опишем алгоритм в идее функции Ind.
function Ind (s : string; c:char) : integer;
var n: integer; { длина строки s }
i: integer; { индексы для просмотра строки s }
begin
n:=length(s);
i:=1;
while (i<=n) and (s[i]<>c) do
i:=i+1;
if i<=n then Ind:=i else Ind:=0
end;
Другой вариант решения этой задачи можно представить с использованием функции pos:
var c : char;
S : string;
.. .. ..
Ind:= pos(c,s);
Такое использование функции pos крайне нежелательно.
Задача 3. В строке найти максимальную длину подстроки из одинаковых подряд идущих символов.
Входные данные: s – строка.
Выходные данные: p – максимальная длина.
Метод решения
Пусть s=’abb111cc’, тогда p=3.
В пустом массиве p=0.
Для каждого символа s[i] определим количество его повторений, то есть s[i]=s[j], начиная с j=i+1. Затем найдем p=max(p, j-i).
Алгоритм 1
p:=0; n:=length(s);
i:=1;
while i<=n do
begin
j:=i+1;
while (i<=n) and (s[i]=s[j]) do j:=j+1;
if p
i:=j
end;
Проверьте, что алгоритм 2 решает ту же самую задачу.
Алгоритм 2
p:=1;
n:=length(s);i:=1;
while i
begin
if s[i+1-p]= s[i+1] then p:=p+1;
i:=i+1
end;
1.4 Операция вставить
Задача4. Вставить заданный символ на k – тую позицию строки s.
Входные данные: s – строка;
k – заданная позиция;
c – заданный символ.
Выходные данные: измененная строка s.
Опишем алгоритм в виде процедуры Ins_Sim.
procedure Ins_Sim(c:char; k:integer; var s:string);
var i:integer;
n:integer; { длина строки }
begin
n:=length(s);
for i:=n downto k do
s[i+1]:=s[i]; {сдвиг вправо на одну позицию }
s[k]:=c;
s[0]:=chr(n+1) { длина строки увеличится на 1 }
end;
Задача 5. Вставить заданный символ перед каждой заданной буквой строки.
Входные данные: s – строка;
c – заданный символ;
b – заданная буква.
Выходные данные: измененная строка s.
Метод решения 1
Необходимо найти позицию символа b в s (индекс k), то есть выполнить операцию k :=Ind(b, s );
пока k ≠ 0 выполнить
1) Ins_Sim(c, k, s )
2) найти очередную позицию символа b в s: k :=Ind(b, s );
Опишем алгоритм в виде процедуры Change_Ins.
procedure Change_Ins(c, b : char; var s : string);
var k, n : integer;
begin
n:=length(s); k :=Ind(b, s );
while k<>0 do
begin
Ins_Sim(c, k, s);
k :=Ind(b, s )
end;
Метод решения 2
Представим метод решения без использования введенных операций, но с использованием дополнительной памяти.
Опишем алгоритм в виде процедуры Change_Ins_1.
procedure Change_Ins_1(c, b : char; var s : string);
var k, i, n : integer;
s1 : string; { дополнительная строка }
begin
n:=length(s); s1:=’’; { пустая строка }
for i:=1 to n do
if s[i] <> b then s1:=s1 + s[i]
else s1 + c + s[i];
s:=s1
end;
Замечание. Если не использовать дополнительную память, то символы строки s надо сдвигать вправо, что соответствует операции Ins_Sim.
Задача 6. Вставить в строку перед каждым вхождением слова ‘begin’ его номер в виде комментария.
Например, имеется строка:
begin x:=1; begin s:=2; begin end end end.
В результате должна получиться строка :
{1} begin x:=1; {2}begin s:=2; {3}begin end end end.
Входные данные : s – строка.
Выходные данные : s – изменённая строка.
Метод решения
Для каждого ‘begin’ находим его номер j, формируем вставляемую строку q=’{‘+j+’}‘ и вставляем её, используя стандартную операцию insert.
Вначале j=’1’, затем j:=succ(j);
i - позиция символа в строке s, начиная с которой в ней ведётся поиск слова ‘begin’, вначале i=1;
l - длина строки, в которой ведётся поиск, вначале l – длина всей строки;
k - номер начала первого вхождения слова в строку s с позиции i длины l, вначале k:=pos(w,s)..
Рассматриваемый алгоритм использует стандартные операции:
pos, insert, copy.
program Ins_Com;
const q1='{';
q2='}';
var s:string;
j :char;
q :string[3];
w:string;
i,k,n,l:integer;
begin
readln(s);
j:='1'; w:='begin';
n:=length(w);
i:=1;
k:=pos(w,s);
while k<>0 do
begin
q:= q1+j+q2;
insert(q,s,i+k-1);
j:=succ(j);
i:=i+k+n-1;
l:= length(s)-i+1;
k:=pos(w,copy(s,i,l));
end ;
writeln(s);
end.
Какие изменения нужно внести в программу, чтобы изменить слово, перед которым вставляется его номер? Какие изменения нужно внести в программу, чтобы номер вставлялся после заданного слова?
Замечание. Алгоритм решения этой задачи можно упростить, если вместо стандартной функции pos использовать функцию, которая ищет индекс вхождения слова W в строку s, начиная с позиции i. Опишем эту функцию Index
function Index(W,s:string; i:integer):integer;
var j:integer;
L,K:integer; {длины s и W}
begin
L:=length(s); K:=length(W);
j:=1; i:=i-1;
while (i<=L) and (j<=K) do
begin
j:=1 ; i:=i+1 ;
while (j<=K) and (s[i+j-1]=W[j]) do j:=j+1;
end;
if j>k then Index:=i else Index:=0
end;
Алгоритм решения задачи с использованием этой функции будет иметь следующий вид:
readln(s);
j:='1'; w:='begin';
n:=length(w);
k:=index(w, s,1); { поиск первого вхождения}
while k<>0 do
begin
q:= q1+j+q2;
insert(q,s,k);
j:=succ(j);
k:=index(s,w,k+n-1);{поиск следующего вхождения}
end ;
writeln(s);
1.5 Операция удалить
Задача 7. Удалить из строки все вхождения заданного символа.
Входные данные: s – строка;
c – заданный символ.
Выходные данные: измененная строка s.
Метод решения 1
Аналогичная операция рассматривалась с массивом ([1]).
Сформулируем алгоритм в виде процедуры Del_Sim.
proctdure Del_Sim(c:char; var s:string);
var i, k : integer;
begin
n:=length(s); k:=0;
for i:=1 to n do
if s[i]<>c then
begin
k:=k+1; s[k]:=s[i]
end;
s[0]:=chr(k)
end;
Метод решения 2
Сформулируем решение задачи с использованием стандартной операции Delete.
proctdure Del_Simvol(c:char; var s:string);
var i : integer;
begin
i:=1;
while i<=length(s) do
begin
if s[i]=c then Delete(s, i, 1);
i:=i+1
end
end;
Сложность первого алгоритма определяется величиной O(n), а сложность второго алгоритма определяется величиной O(n*n). Можно сделать вывод, что не всегда удобно пользоваться стандартными операциями.
Задача 8. Удалить из строки символ, следующий за заданным символом.
Входные данные: s – строка;
c – заданный символ.
Выходные данные: измененная строка s.
Метод решения 1
После каждого символа из s со значением c удалить следующий символ. Например: s = ‘abacca’; c = ‘a’. Измененная строка s = ‘aaca’.
Решение задачи без использования стандартной операции заключается в том, что анализ s[i] осуществляется с одновременным сдвигом его влево. Если же s[i] = c, то следующий символ пропускается i := i+1.
Алгоритм 1
n:=length(s);
k:=0;
i:=1;
while i<=n do
begin
k:=k+1; s[k]:=s[i];
if s[i]=c then i:=i+1;
i:=i+1
end;
s[0]:=chr(k)
Метод решения 2
Сформулируем метод решения с использованием стандартной операции Delete: при каждом сравнении s[i] = c происходит вызов операции Delete для удаления i+1- ого символа.
Алгоритм 2
i:=1;
while i< length(s) do
begin
if s[i]=c then Delete(s, i+1, 1);
i:=i+1
end;
Сравнивая алгоритмы, делаем вывод, что алгоритм 2 не эффективен.
1.6 Обработка слов в строке
Задача 9. Определить в строке количество слов, разделенных одним или несколькими пробелами.
Входные данные: s – строка.
Выходные данные: k – количество слов.
Метод решения
Признаком слова будем считать последний символ слова (не пробел) и следующий за ним пробел. Строка должна заканчиваться пробелом.
Например, s=’aa rrrr bbb ‘. Строка содержит 3 слова.
Опишем алгоритм в виде функции Count_Word.
function Count_Word(s : string):integer;
var i, k:integer;
begin
s:=s+’ ‘; { Строка должна заканчиваться пробелом }
k:=0; i:=1;
while i
begin
if (s[i]<>’ ‘) and (s[i+1]=’ ‘) then k:=k+1;
i:=i+1
end;
Count_Word:=k
End;
Задача 10. Строка представлена последовательностью слов, разделенных одним или несколькими пробелами, пробелы могут быть в начале и в конце строки. Выделить слово, обработать слово и подсчитать общее количество слов.
Входные данные: s – строка.
Выходные данные: sl – очередное слово;
k – количество слов.
Метод решения
Для всех символов строки выполнить:
1) пропустить пробелы;
2) пока не конец строки
2.1) счет количества слов;
2.2) выделение слова;
2.3) обработка слова.
Приведем два алгоритма решения задачи:
1) для выделения слова используется операция copy;
2) слово накапливается в дополнительной переменной sl.
Выделенное слово выдается на экран.
Алгоритм 1
k:=0;
n:=length(s);
i:=1;
while i<=n do
begin
while (i<=n) and (s[i]=’ ‘) do i:=i+1;
if i<=n then
begin
k:=k+1;
Ind:=I; { начало очередного слова}
while i<=n and s[i]<>’ ‘ do i:=i+1;
writeln(copy(s, Ind, i-Ind)
end
end;
writeln(‘k= ‘,k);
Алгоритм 2
k:=0; n:=length(s);
i:=1;
while i<=n do
begin
while (i<=n) and (s[i]=’ ‘) do i:=i+1;
if i<=n then
begin
k:=k+1;
sl:=’’;
while i<=n and s[i]<>’ ‘ do
begin
sl:=sl+s[i]; i:=i+1
end;
writeln(sl)
end
end;
writeln(‘k= ‘,k);
Сравним эти алгоритмы. В алгоритме 1 для получения слова выполняются два последовательных цикла: найти индекс и операция copy. В алгоритме 2 для получения слова – один циклический процесс. Значит алгоритм 2 эффективней.
1.7 Обработка последовательности строк
Задача 11. Каждая строка представляет собой последовательность слов, разделенных пробелами, и заканчивается точкой. Выдать слова, являющиеся палиндромами и не совпадающие с последним словом строки.
Входные данные: s – очередная строка из текстового файла.
Выходные данные: SL – очередное слово из строки, удовлетворяющее условию.
Метод решения
Будем считать, что последовательность строк находится в текстовом файле Str.txt.
Введем следующие операции:
Prov проверяет, является ли слово симметричным относительно середины (палиндромом) (например, топот, раар);
Last определяет последнее слово в строке;
Equel проверяет на равенство два слова.
Алгоритм анализа слов в строке представим в виде процедуры An_Slov.
Приведем заголовки операций:
procedure Last(S:string; var W:string;var k:integer);
где s – входная строка:
W – последнее слово строки s;
k – индекс последнего символа строки s, то есть s[1..k].
function Prov(W :string):boolean;
prov = true, если W – палиндром, иначе prov = false.
function Equel(s1,s2:string):boolean;
procedure An_Slov(S:string);
Алгоритм обработки слов в строке описан в пункте 1.6.
Опишем алгоритм решения задачи, используя введенные операции.
Алгоритм решения задачи
Пока не конец текстового файла, выполнить:
1) чтение очередной строки s;
2) вызов процедуры An_Slov(s).
Наконец, решение задачи представим в виде программы,
program Analiz;
var name,s:string;
procedure Last(S:string; var W:string;var k:integer);
var i,n:integer;
begin
n:=length(S);
W:='';
i:=n-1;
while (S[i]<>' ') do
begin
W:=S[i]+ W; i:=i-1
end;
k:=i;
end;
function Prov(W :string):boolean;
var n,i:integer;
begin
n:= length(W);
i:=1;
while (i<=n) and (W[i]=W[n]) do
begin
i:=i+1; n:=n-1
end;
Prov:=i>n;
end;
function Equel(s1,s2:string):boolean;
var i,n,m:integer;
begin
n:=length(s1);
m:=length(s2);
if n<>m then Equel:=false
else
begin
i:=1;
while (i<=n) and (s1[i]=s2[i]) do
i:=i+1;
Equel:=i>n;
end;
end;
procedure An_Slov(S:string);
var i,Ind:integer;
Slovo,W:string;
B:boolean; { для случая: если в строке нет слов, удовлетворяющих условию задачи }
begin
Last(S,W,Ind); { Ind – позиция последнего символа S }
writeln;
i:=1; B:=false;
while i<=Ind do
begin
while (i<=Ind) and (S[i]=' ' ) do i:=i+1;
if i<=Ind then
begin
Slovo:='';
while (i<=Ind) and ( s[i]<>' ') do
begin
Slovo:=Slovo+S[i]; i:=i+1;
end;
if Prov(Slovo)and(not Equel(Slovo,W)) then
begin
Write(Slovo, ' '); B:=true;
end;
end;
end;
if B=false then
writeln('Нет слов, удовлетворяющих условию задачи ');
writeln;
end;
begin
writeln('Введите имя файла');
readln(name);
assign(t,name);
reset(t);
while not eof(t) do
begin
readln(t,s);
writeln(' входная строка = ',s);
An_Slov(s);
end;
close(t);
readln;
end.
1.8 Общие задания
1. Напечатать true, если в заданной строке буква ‘а ‘встречается чаще, чем буква ‘b’, и false в противном случае.
2. Проверить, входит ли в заданную строку каждая буква заданного слова,
3. Проверить, правильно ли в заданной строке расставлены круглые скобки.
4. Определить, является ли заданная строка правильной записью целого числа (возможно со знаком).
5. Удалить из заданной строки
а) все цифры;
б) все знаки ’+’, непосредственно за которыми идёт цифра.
6. Заменить в тексте все пары ‘ph’ на букву’ f’.
7. Подсчитать, сколько раз каждая буква встречается в строке.
8. Подсчитать, сколько раз каждая цифра встречается в строке.
9. Значениями литерных переменных с1, с2, с3 являются цифры. Присвоить целой переменной к число, составленное из этих цифр (если с1=’8’, с2=’0’, с3=’5’, то к=805).
10. Дана строка. Найти символы, которые в строке встречаются
а) по одному разу; б) по два раза; в) по три раза;
г) больше пяти раз.
1.9. Индивидуальные задания
Задания содержат две задачи.
В первой задаче задаётся строка символов. Получить выходную строку (согласно условию) двумя способами: не используя стандартные функции и с использованием стандартных функций.
Во второй задаче дана строка, состоящая из слов, разделённых пробелами (пробелы могут быть также в начале и в конце строки). Требуется выполнить предложенные действия над словами. Вспомогательный массив слов разрешается использовать в заданиях 5, 20, 21, 22.
№1 1. Удалить символ перед каждым символом точка.
2. Напечатать симметричные слова.
№2. 1. Вставить символ ‘*’ перед каждым символом точка.
2. Напечатать те слова, которые содержат начальную букву слова ещё хотя бы один раз.
№3. 1. Вставить символы ‘**’ перед каждым символом точка.
2. Напечатать те слова, в которых буквы упорядочены по алфавиту.
№4. 1. Вставить символ ‘*’ перед каждыми двумя символами точка.
2. Напечатать те слова, в которых все буквы различные.
№5. 1. Вставить ‘..’ за каждым символом пробел.
2. Напечатать те слова, которые содержатся в строке по одному разу.
№6. 1. Каждые ‘..’ заменить на одну точку.
- Напечатать те слова, длина которых меньше длины первого слова.
№7. 1. Заменить подряд стоящие пробелы одним пробелом.
2. Напечатать слова в следующем порядке: первое слово и последнее слово, затем второе и предпоследнее и т.д.
№8. 1. Удалить все подстроки s1 (s1-задаётся).
2. Напечатать те слова, длина которых больше длины последнего слова.
№9. 1. Вставить подстроку s1 за каждым заданным символом c.
2. Напечатать те слова, количество гласных в которых больше количества согласных.
№10. 1. Перед каждым символом ‘.’ удалить к символов (если это возможно).
2. Напечатать те слова, в которых гласные чередуются с согласными.
№11. 1. После каждого символа вставить символ пробел.
2. Проверить, равны ли первое слово и последнее, второе и предпоследнее и т.д.
№12. 1. Перед каждым символом вставить символ пробел.
2. Найти номер слова со значением ‘then’, за которым следует слово ‘begin’.
№13. 1. В каждой подстроке ‘ab’ после символа ‘a’ вставить пробел.
2. Найти самое длинное слово и самое короткое слово.
№14. 1. В каждой подстроке ‘abc’ после символа ‘a’ вставить два пробела.
2. Найти слово, длина которого наиболее близка к средней длине слова.
№15. 1. Перед и после каждой подстроки ‘else’ вставить символы пробел.
- Найти слово, содержащее наибольшее количество согласных
№16. 1. Поместить 5 символов пробел в начало, в середину и конец строки.
2. Найти слова, у которых первая и последняя буквы одинаковые.
№17. 1. Удалить каждый 3-ий символ.
2. Найти последнее слово, длина которого больше заданной длины.
№18. 1. Удалить ‘;’ перед каждым ‘else’ (если эта ситуация имеется).
2. Найти слова, у которых первая и последняя – гласные буквы.
№19. 1. Удалить все комментарии.
2. Найти слова, содержащие повторяющиеся буквы.
№20. 1. После каждого ‘begin’ и перед каждым’end’вставить комментарий соответствия.
2. Напечатать слова в порядке возрастания их длин.
№21. 1.Заменить ‘read’ на ‘readln’.
2. Напечатать слова в порядке убывания их длин.
№22. 1. Заменить ‘writeln’ на‘write’.
2. Напечатать слова в алфавитном порядке.
№23. 1. Заменить ‘writeln(x)’ на ‘writeln(‘x= ’,x)’.
2.Напечатать слова, которые начинаются с заглавной буквы.
№24. 1. Перед каждым’begin’ вставить в виде комментария его порядковый номер.
- Проверить, содержит ли строка слова возрастающей длины.
№25. 1. Перед и после двух одинаковых символов вставить ’_’.
2. Напечатать слова, содержащие заданную букву.
№26. 1. Заменить слово ‘роза’ на слово ‘розалия’.
2. Найти слово, совпадающее с заданным словом.
№27. 1. Удалить три стоящие рядом точки.
2. Найти слово, за которым следует такое же слово.
2 Записи
2.1 Определение и представление в памяти
Запись – это конечное множество элементов, состоящее из компонент произвольного типа и представляющих единое целое. Элементами записи могут быть скалярные переменные, массивы, записи низших уровней, массивы записей.
Запись дает возможность определять составные, или комбинированные типы. Примерами из математики являются комплексные числа, состоящие из двух вещественных чисел, и вектор координат точек в двумерном или трехмерном, или n- мерном пространстве. Примером из обработки данных является описание сотрудников предприятия с помощью существенных характеристик таких, как имя и фамилия, дата рождения, должность, оклад или, например, информация о владельцах автомобиля, содержащая номер, марку машины, фамилию владельца, его адрес.
В математике такой составной тип называется декартовым произведением типов компонент. В обработке данных для обозначения подобной совокупности данных используется термин «запись» (record). Элементы записи называют полями.
В общем виде составной, или комбинированный тип, определяется следующим образом:
type T=record
s1 : T1;
s2 : T2;
. . .
sn : Tn
end;
Здесь T – имя комбинированного типа, s1, s2, . . .,sn – переменные типов T1, T2, . . ., Tn.
Например,
type Complex = record
Re : real;
Im : real
end;
type Person = record
fio: string[20];
birthdate: integer;
qulif: string[20];
oclad: longint
end;
Опишем переменные типа записи:
var z: Complex;
p: Person;
tabl: array [1..100] of Person;
Обращение к элементам записи осуществляется с использованием составных имен. Составное имя начинается с имени записи и содержит список имен полей, разделенных точками, которые входят в цепь, ведущую к требуемому элементу.
Например, к полям записи можно обратиться по именам:
z.Re, z.Im, p.fio, tabl[i].fio.
Для сокращения обозначений полей записи используется оператор присоединения:
with <переменная запись> do <оператор,использующий поля>
Пример выдачи на экран вещественной и мнимой частей комплексного числа z:
with z do writeln(Re:5:3, Im:5:3);
В оперативной памяти элементы записи располагаются последовательно в том порядке, в котором они описаны. Размер памяти записи складывается из длин ее полей.
Определим длину записи p: поле fio занимает 20 байт, поле birthdate – 2 байта, поле qulif – 20 байт, поле oclad – 4 байта, Но надо иметь в виду, что адрес переменной типа integer должен быть кратен 2, адрес переменной типа longint должен быть кратен 4. Такое выравнивание выполняется автоматически путем пропуска байт, поэтому длина приведенной записи будет равна 46 байтам, если начальный адрес кратен 2, и равен 48 байтам, если начальный адрес кратен 4.
Для того чтобы не было автоматического выравнивания, описание записи Person следовало бы выполнить так:
type Person = record
nom: longint;
fio: string[20];
birthdate: longint;
qulif: string[20];
oclad: longint
end;
В этом случае длина записи всегда будет равна 52 байтам без пропусков.
Следует отметить, что запись и массив имеют общее свойство: оба являются структурами с произвольным доступом к компонентам. Запись – более универсальная структура, так как не требует однородности типов ее компонент. С другой стороны, массив предоставляет большие возможности, так как выбор его компонент происходит по индексу, который может вычисляться, если он представлен выражением, тогда как выбор компонент записи – это фиксированные идентификаторы (имена полей), задаваемые в описании типа.
2.2 Типизированные константы-записи
Запись и массив записей можно инициализировать константными значениями.
Определение константы-записи имеет следующий вид:
< идентификатор> : <тип>= (<список значений полей>)
<список значений полей> :: <значение поля>|<список значений полей>;
<значение поля>
<значение поля>:: <имя поля>: <константа>
Приведем пример инициализации массива записей и вывода массива. Оператором присваивания передадим все значения константного массива записей не константному массиву того же типа.
program T_Const;
type zap=record
strana: string[20];
prodol: integer;
transport: string[20];
cena: real
end;
const v: array[1..3] of zap=(( strana: ‘Бельгия’; prodol:13;
transport: ‘автобус’; cena: 3456),
(strana: ‘Швеция’; prodol:13;
transport: ‘самолет’; cena: 5670),
( strana: ‘Финляндия’; prodol:20;
transport: ‘поезд’; cena: 4800));
var i: integer;
u: array[1..3] of zap;
begin
for i:=1 to 3 do
with v[i] do
writeln(strana.’ ‘,prodol.’ ‘.transport, ‘ ‘,cena);
u:=v;
for i:=1 to 3 do
with u[i] do
writeln(strana.’ ‘,prodol.’ ‘.transport, ‘ ‘,cena)
end.
2.3 Обработка элементов записи типа Person
Пусть в текстовом файле ‘Tabl.txt’ представлена таблица. Приведем несколько строк таблицы:
1 Иванов И.И. 1978 инженер 7000
2 Сидоров А.В. 1980 главный инженер 10000
3 Петров А.А. 1960 бухгалтер 8000
4 Владимиров А.С. 1979 инженер 7000
5 Александрова Е.Н. 1975 экономист 7000
Задача 1. Показать таблицу на экране.
Опишем алгоритм в виде процедуры SHOW.
type Person = record
nom: longint;
fio: string[20];
birthdate: longint;
qulif: string[20];
oclad: longint
end;
procedure SHOW(name:string);{имя текстового файла}
var t:TEXT;
p:Person;
begin
assign(t,name);
reset(t);
while not eof(t) do
with p do
begin
readln(t, nom, fio, birthdate, qulif, oclad);
writeln(nom:5, fio, birthdate:5, qulif, oclad:5)
end;
` close(t)
end;
Задача 2. Выдать на экран список сотрудников, оклад которых больше заданного оклада.
Опишем алгоритм в виде процедуры SELECT.
procedure SELECT (name:string; Oc:longint);
var t:TEXT;
p:Person;
begin
assign(t,name);
reset(t);
while not eof(t) do
with p do
begin
readln(t, nom, fio, birthdate, qulif, oclad);
if oclad> oc then
writeln(nom:5, fio, birthdate:5, qulif, oclad:5)
end;
` close(t)
end;
Описание типа Person для процедур задач 1 и 2 является глобальным.
Задача 3. Поместить таблицу в массив записей типа Person.
Опишем алгоритм в виде процедуры Create_Arr.
Опишем используемые типы:
const n_max=100;
type Person = record
nom: longint;
fio: string[20];
birthdate: longint;
qulif: string[20];
oclad: longint
end;
vect = array[1..n_max] of Person;
procedure Create_Arr (name:string;
var tabl:vect; var n:integer);
var t:TEXT;
p:Person;
begin
assign(t,name);
reset(t);
n:=0;
while not eof(t) do
begin
n:=n+1;
with p[n] do
readln(t, nom, fio, birthdate, qulif, oclad);
end;
close(t)
end;
2.4 Сортировка массива записей по различным ключам
Задача 4. Отсортировать массив записей в порядке возрастания значения каждого поля по очереди.
Входные данные: а – массив записей;
n - размер массива.
Выходные данные: изменённый массив записей.
Метод решения.
Используется метод обменной сортировки (метод пузырька), который приспособлен для сортировки по различным полям записей. С полями записи ассоциируются ключи сортировки, которые образуют перечислимый тип. Каждый ключ подразумевает свой критерий сортировки. Разветвление по ключу осуществляется оператором case.
Процедура сортировки имеет следующие параметры: n - размер массива, key – ключ сортировки, a – массив записей. Массив записей после сортировки по выбранному ключу изменяется.
Ниже приводится текст программы при заданной структуре записи.
Структура записи: фамилия (fio), номер курса студента (kurs) и средний балл (srb). С полями этой записи (fio,kurs,srb) ассоциируются ключи: k_fio, k_kurs, k_srb. Сортировка выполняется в порядке возрастания значения каждого поля (по очереди).
Program Sort_key;
Const nm=100;
Type rec=record
Fio : string[20];
Kurs : integer;
Srb : real
End;
Vector=array[1..nm] of rec;
Key_type_=(k_fio, k_kurs, k_srb);
Procedure sort(n: integer; key: key_type ; var a:vector);
Var i, j : integer;
f : boolean;
x: rec;
begin
for i:=n downto 2 do
for j:=1 to i-1 do
begin
case key of
k_fio : b:=a[j].fio>a[j+1].fio;
k_kurs : b:=a[j].kurs>a[j+1].kurs;
k_srb : b:=a[j].srb>a[j+1].srb;
end;
if b then
begin x:=a[j]; a[j]:=a[j+1]; a[j+1]:=x end
end
end;
procedure enter(var n:integer; var a:vector);
begin
readln(a[1].fio);
n:=1;
while a[n].fio<>’*’ do
begin
with a[n] do readln(kurs,srb);
n:=n+1;
readln(a[n].fio);
end;
n:=n-1
end;
procedure print(n:integer; const a:vector);
var i,j :integer;
begin
for i:=1 to n do
with a[i] do
begin
write(fio);
for j:=length(fio) to 20 do
write(‘ ‘);
writeln(‘ ‘,kurs,’ ‘,srb:4:2)
end
end;
var a : vector;
key : key_type;
n : integer;
begin
enter(n,a);
for key:=k_fio to k_srb do
begin
sort(n,key,a);
prinr(n,a);
writeln(‘------------------------------------‘)
end
end.
2.5 Задания
1. Напишите программу ведения банковских счетов на основании чеков. Структура исходной записи: фамилия клиента, номер счёта, текущее состояние счёта.
Структура сведений об операциях: номер счёта клиента, сумма прихода (положительная) или расхода (отрицательная).
Вводится массив структур первого и второго типа, выполняется по найденному номеру счёта операция для соответствующего клиента, печатаются сведения в записях и новое содержимое записи клиента.
Если окажется, что какой-либо чек выписан на сумму, превышающую остаток счёта, программа должна печатать соответствующее сообщение.
2. Напишите программу, которая начисляет еженедельную заработную плату на основании следующих данных: имя и фамилия служащего, табельный номер, число проработанных часов, почасовой тариф, количество иждивенцев. Массив данных вводится из текстового файла.
Рабочее время свыше 40 часов в неделю считается сверхурочным и оплачивается в полуторном размере.
Программа должна удерживать налог, взимаемый федеральным правительством в соответствии со следующей шкалой:
| Количество иждивенцев | Процент налогообложения , % |
| 0 | 16 |
| 1 | 12 |
| 2 | 9 |
| 3 | 6 |
| 4 и более | 5 |
Предусмотреть выдачу на печать отчёта, содержащего всю существующую информацию.
3. Национальное общество содействия потерпевшим убытки выделяет поощрительные стипендии студентам университетов, утративших возможность продолжать учёбу. Минимальный перечень требований, которым должен удовлетворять претендент на такую стипендию, следующий:
a) индекс доходов равен или ниже среднего,
б) возраст – свыше 30,
в) наличие собственной семьи (семейные имеют в анкетных данных признак 2, одинокие – 0),
г) курс – четвёртый или пятый.
Напишите программу, которая считывает фамилии студентов, перечень установленных требований и выдаёт на печать фамилии претендующих на поощрительные стипендии.
4. Фирма Щедрость установила следующие размеры платы за воду:
1) 0.004 долл. за литр для первых 100 л.,
2)0.003 долл. за каждый очередной литр.
Структура считываемых входных данных такова: фамилия потребителя, регистрационный номер потребителя, прежнее показание водомера, новое показание водомера.
Напишите программу, которая выдаёт на печать следующую информацию:
– фамилия потребителя,
– регистрационный номер потребителя,
– прежнее показание водомера,
– новое показание водомера,
– размер платы по первому тарифу,
– размер платы по второму тарифу,
– общую плату.
5. Опишите структуру tour (страна, продолжительность тура, транспорт, цена). Инициализируйте данные в массиве, состоящим из 7 элементов типа tour. Выведите на экран информацию о странах, стоимость билета в которые меньше введённого с клавиатуры числа. Если таких стран нет, то программа должна выдать соответствующее сообщение на экран.
6. Опишите структуру note (фамилия и имя, номер телефона, день рождения) Введите с клавиатуры данные в массив, состоящий из 19 элементов типа note. Поместите в другой массив информацию о людях, день рождения которых приходится на зимние месяцы. Выведите на экран полученный массив. Если таких нет (массив пуст), то программа должна выдать соответствующее сообщение на экран. Описать операции ввода и вывода структуры.
7. Массив записей содержит длины сторон треугольника и тип треугольника (разносторонний, равнобедренный, равносторонний). Длины вводятся, тип определяется и помещается в соответствующее поле. Выдать окончательный массив записей.
.
8. Структура записи: фио (фамилия, имя, отчество), персональные характеристики (цвет волос, рост, пол), статус (курс, группа), сессия (предмет, экзаменатор, оценка). Создать массив записей, напечатать его в виде списка и составить список рыжеволосых со всеми оценками 5.
9. Структура записи: фио (фамилия, имя, отчество), персональные характеристики (цвет волос, рост, пол), статус (курс, группа), сессия (предмет, экзаменатор, оценка). Создать массив записей, напечатать его в виде списка и составить список имеющих рост ниже 180см, блондинок.
10. Структура записи: фио (фамилия, имя, отчество), персональные характеристики (цвет волос, рост, пол), статус (курс, группа), сессия (предмет, экзаменатор, оценка). Создать массив записей, напечатать его в виде списка и составить список студентов со средней оценкой большей общей средней.
11. Структура записи: фио (фамилия, имя, отчество), персональные характеристики (цвет волос, рост, пол), статус (курс, группа), сессия (предмет, экзаменатор, оценка). Создать массив записей, напечатать его в виде списка и составить подсписки по цвету волос.
12.Структура записи: фио (фамилия, имя, отчество), персональные характеристики (цвет волос, рост, пол), статус (курс, группа), сессия (предмет, экзаменатор, оценка). Создать массив записей, напечатать его в виде списка и найти название предмета, который был сдан лучше всего.
13. Структура записи: ФИО студента, номер курса, место проживания (дома, в общежитии, на квартире). Составить списки по каждому месту проживания и список студентов 1 курса, проживающих в общежитии.
14. Структура записи: ФИО родителей, год рождения каждого ребёнка (в виде массива). Построить сводную ведомость для лиц, имеющих в текущем году детей в возрасте меньше 8 лет.
15. Массив содержит записи: название товара, цена, название магазина. Ввести массив и отсортировать записи по названию товара. Оказалось, что некоторые записи содержат ошибки в ценах. Исправления водятся с экрана, исправления содержат название товара и цену, исправления упорядочены по названиям товаров. Внести исправления в массив и выдать протокол исправлений в виде:
<Номер элемента> <цена> замена на <цена>
Выдать исправленный массив.
16. Список учеников содержит ф.и.о. каждого и степень занятости: 0 – нигде не занят, 1 – занимается в каком-либо кружке, 2 – занимается в двух кружках и т.д. Построить списки учеников разной степени занятости.
17. Сводка содержит название всех месяцев года и среднемесячную температуру воздуха для каждого месяца. Вычислить среднегодовую температуру Т. Составить сводку, содержащую название тех месяцев и их температур, среднемесячная температура которых принадлежит диапазону Т
( - задано). 18. Вводятся тройки чисел а,в,с –коэффициенты квадратных уравнений. Построить массив записей в виде а ,в, с и характеристика корней в виде текстовой информации ( вещественные различные, вещественные равные, комплексные).
19. Вводятся коэффициенты системы двух линейных уравнений с двумя неизвестными в виде матриц из двух строк и трёх столбцов. Построить массив записей. Каждая запись – это массив коэффициентов и текстовая информация о количестве решений системы (одно решение, множество решений, нет решения).
20. Создать массив записей вида: отдел, ф.и.о., сведения. Сведения состоят из полей: профессия, разряд, стаж в годах. Внести изменения в массив записей. Изменения вводятся в массив записей и содержат: отдел, ф.и.о., разряд. Выдать исходный массив записей и изменённый.
21. Создать массив записей, каждая запись которого имеет следующую структуру: наименование вида, наименование товара, дата выпуска, цена за единицу, количество единиц. Примеры записей:
Ткани ситец 10.11.1983 1.20 250
Канцтовары ручка шариковая 15.03.1980 0.25 100
В созданном массиве изменить цену (понизив её на 15% ) у тех товаров, для которых элемент структуры “наименование товара ” совпадает со значением вводимой переменной nametov и год выпуска раньше 1982 г. Сделать выборку всех товаров, относящихся к виду, название которого содержит переменная vidtov.
22. Создать программу, которая отслеживает денежные взносы в Обществе защиты нравственности. Она предлагает пользователю ввести количество взносов, затем имя и сумму взноса каждого спонсора. Информация должна храниться в массиве структур. Каждая структура содержит два элемента: массив символов имени и значение типа double – сумму взноса. После считывания всех данных программа отображает имена и суммы взносов всех спонсоров, которые внесли более $10000. В начале этого списка должен быть заголовок, указывающий, что следующие спонсоры являются почётными членами общества. После этого выводится список остальных спонсоров. Этот список должен быть после заголовка “Спонсоры”. Если в какой-либо категории отсутствуют спонсоры, программа выводит слово “нет”.
23. Вступив в Благотворительный орден программистов (БОП), вы можете быть известны на собраниях БОП под своим действительным именем, по названию должности или по секретному псевдониму БОП. Напишите программу, которая может перечислять членов ордена по действительным именам, по должностям, по секретным псевдонимам или по индивидуально заданным опциям. В основу программы положите следующую структуру:
Type bop =record
Fullname : string[strsize]; // настоящее имя
Title : string[strsize]; // должность
bopname : string[strsize]; // секретный //псевдоним bop
preference : integer; //0=fullname, 1=title, //2=bopname
end;
В программе создайте массив таких структур и инициализируйте его подходящими значениями. В цикле пользователь должен иметь возможность выбирать различные варианты:
a) отображение по имени,
b) отображение по должности,
c) отображение по секретному псевдониму,
d) отображение по индивидуально заданным опциям,
e) выход.
Учтите, что вариант “ отображение по индивидуально заданным опциям» означает не вывод значения элемента preference, а отображение данных членов ордена в соответствии с установленными для них опциями.
24. В королевстве Нейтронии, где денежной единицей является tvarp, установлены следующие ставки подоходного налога:
первые 5000 tvarp: 0%
следующие 10000 tvarp: 10%
следующие 20000 tvarp: 15%
свыше 35000 tvarp: 20%.
Например, некто, получающий 38000, должен был заплатить налог величиной
5000*0.00+10000*0.10+20000*0.15+300*0.20, или 4600 tvarp.
Напишите программу, которая использует цикл для ввода в массив структур величины дохода и имени (кто должен платить налог). Цикл прерывается, когда пользователь вводит отрицательное число или нечисловое значение в качестве величины дохода. На экране отобразить сумму налога для каждого элемента массива структуры.
25. Некоторая фирма выписывает счета своим заказчикам в последний день каждого месяца. Если счёт оказывается оплаченным до 10-го числа следующего месяца, заказчик получает скидку в размере 1% от суммы счёта, но не более 2 долл. В случае платежа от 10-го до 20-го числа следующего месяца с заказчика взимается полная сумма счёта. При оплате после 20-го числа следующего месяца с заказчика удерживается пени в размере 1% от суммы счёта, но не менее 1 долл.
Напишите программу, вычисляющую сумму необходимых платежей и выдающую на печать разность между фактически уплаченной суммой и суммой счёта. Выходные данные (все записи хранятся в массиве записей) имеют следующую структуру:
номер заказчика – 5 цифр,
дата выписки счёта – число, месяц и год,
дата фактического платежа – число, месяц и год,
сумма по счёту – XXX.XX,
уплаченная сумма – XXX.XX.
Литература
1. Невская Е.С., Чекулаева А.А Методические указания часть 1. УПЛ РГУ г. Ростов н/Д. 2006.
2. Минакова Н.И. Методы программирования. Учебное пособие / Н.И.Минакова, Е.С. Невская, Г.А. Угольницкий, А.А. Чекулаева, М.И. Чердынцева. – М.: Вузовская книга, 2000. –280 с. –ISBN 5-89522-038-X.
3. Невская Е.С., Чекулаева А.А., Чердынцева М.И. Искусство программи рования. – М.: Вузовская книга, 2002. – 240 с. – ISBN 5-9502-0003-9.