программирование тусур. Программирование учебное пособие. Учебное пособие Томск Эль Контент

• Название: Учебное пособие Томск Эль Контент
• Анкор: программирование тусур
• Дата: 17.08.2022
• Размер: 0.93 Mb.
• Имя файла: Программирование учебное пособие.pdf
• Тип: Учебное пособие; #647947
• страница: 10 из 16

Глава 5. Массивы и строки
writeln(St); {печатается abcf}
St:=
'река Волга';
delete(St,1,5);
writeln(St); {печатается Волга}
Процедура insert(Source:string;var S:string;Index:integer)
осуществляет вставку строки Source в строку S, начиная с позиции Index.
Пример
S:=
'Золотойключик';
insert(
' ',S,8);
writeln(S); {печатается Золотой ключик}
Функция copy(S:string;Index:integer;Count:integer):string
Функция выделяет из строки S подстроку длиной Count символов, начиная с позиции Index. Если Index > length(S), то возвращается пустая строка.
Если Count + Index > length(S), то возвращается конец строки c позиции
Index
. Если Index > 255, то диагностируется ошибка при выполнении.
Пример copy(
'abcdefg',2,3) = 'bcd'
copy(
'abcdefg',4,10) = 'defg'
Функция concat(S1,S2,. . ., SN:string):string
Производит соединение последовательности строк, эта функция равносильна операции конкатенации «+».
Функция pos(Substr:string;S:string):integer
Функция обнаруживает первое появление в строке S подстроки Substr. Ре- зультат равен номеру той позиции, где начинается подстрока Substr. Если под- строки нет, то результат равен 0.
Пример pos(
'de','abcdef') = 4
pos(
'z','abcdef') = 0

5.3 Сортировка
103
Имеются две процедуры преобразования числовых значений в строковые, и на- оборот: Str и Val. Процедура Str при обращении к ней вида
Str(num, strnum);
где num — значение числового типа, а strnum — переменная строкового типа, при- сваивает переменной strnum строковое значение, представляющее собой сим- вольное изображение значения переменной num. В первом параметре функции
Str можно использовать спецификаторы формата (такие же, как для оператора write
).
Процедура Val выполняет обратное преобразование. Обращение к ней имеет вид:
Val(strnum, num, errcode);
Третий параметр в этой процедуре равен нулю при успешном выполнении преобразования. В том случае, когда первый параметр содержит символы, недо- пустимые при записи числа, значение параметра errcode равно номеру позиции с ошибочно заданным символом.
Пример var i, errcode: integer; s: string;
begin str(2000,s); writeln(
'Строковое значение ',s);
readln;
val(s, i, errcode);
if errcode
<> 0 then writeln('Ошибка ввода в позиции: ',
errcode)
else writeln(
'Числовое значение = ', i);
readln;
end.
В этом примере вначале выполняется преобразование целочисленного значения
2000 в строковое (обращение к процедуре Str), а затем, наоборот, строка символов
«2000» преобразуется в значение типа Integer (процедура Val).
5.3 Сортировка
5.3.1 Постановка задачи
Что такое сортировка? Пусть даны элементы a
1
, a
2
,. . ., a
n
и функция упорядоче- ния f (a
i
), которая возвращает целое или вещественное число. Сортировка означает перестановку этих элементов в таком порядке a
k1
, a
k2
,. . ., a
kn
, что f (a
k1
)
⩽ f (a
k2
)
⩽
⩽ . . . ⩽ f (a
kn
) (сортировка по неубыванию) или f (a
k1
)
⩾ f (a
k2
)
⩾ . . . ⩾ f (a
kn
) (сорти- ровка по невозрастанию).
Что можно сортировать?

104
Глава 5. Массивы и строки
• Числа: f (a
i
)=a
i
• Литеры: f (a
i
)=ord(a
i
).
• Значения перечислимого типа: f (a
i
)=ord(a
i
) (см. раздел 6.1.1).
• Массивы и строки — использовать лексикографический порядок.
• Записи.
Мы будем сортировать массивы, в частности массив a.
type index=1..n;
var a:array[index] of element;
В качестве элементов массива рассматриваются любые данные, для которых можно ввести отношение порядка (естественное или какое-то особенное). При реализации алгоритма сортировки для какого-то особенного порядка удобно в ка- честве отношения «больше» между элементами использовать значение специально введенной для этого булевской функции greater(x,y)=f(x)К алгоритмам сортировки предъявляется требование экономии па- мяти: т. е. переупорядочивание элементов нужно выполнять на том же самом месте, не использовать вспомогательных массивов.
Сортировка простыми включениями
Этот метод обычно используют игроки в карты.
• Элементы (карты) условно разделяются на готовую последовательность a
1
,
a
2
,. . ., a
i
−1
и входную последовательность a
i
,. . ., a
n
• На каждом шаге, начиная с i = 2 и увеличивая i на 1, берут i-ый элемент входной последовательности и передают в главную последовательность,
вставляя его на подходящее место.
Алгоритм for i:=2 to n do begin x:=a[i];
{вставить x на подходящее место в a[1],a[2],
. . .,a[i
−1]
или оставить на месте}
end
В следующем примере каждой строке соответствует состояние массива после очередного шага цикла (выделен шрифтом выбираемый элемент):
44 55 12 42 94 18 06 67 44 55 12 42 94 18 06 67 12 44 55 42 94 18 06 67 12 42 44 55 94 18 06 67 12 42 44 55 94 18 06 67 12 18 42 44 55 94 06 67 06 12 18 42 44 55 94 67
06 12 18 42 44 55 67 94

5.3 Сортировка
105
Для этого алгоритма число сравнений в среднем равно n
2
/4 (в худшем случае равно n
2
/2 ). Число присваиваний (пересылок) — такое же.
Сортировка простым выбором
Метод:
• Выбирается наименьший элемент.
• Он меняется с первым элементом a[1].
• Эти операции повторяются с оставшимися n
− 1 элементами, потом с n − 2
элементами, пока не останется только один наибольший элемент.
В следующем примере каждой строке соответствует состояние массива после очередного шага цикла (выделен шрифтом выбираемый элемент):
44 55 12 42 94 18 06 67 06 55 12 42 94 18 44 67 06 12 55 42 94 18 44 67 06 12 18 42 94 55 44 67 06 12 18 42 94 55 44 67 06 12 18 42 44 55 94 67 06 12 18 42 44 55 94 67
06 12 18 42 44 55 67 94
Алгоритм:
for i:=1 to n
−1 do begin
{присвоить k индекс наименьшего элемента из a[i],a[i+1],
. . .,a[n]}
{поменять местами a[i] и a[k]}
end
Для этого алгоритма число пересылок в среднем равно n ln n, наихудшее —
n
2
/4. Число сравнений равно (n
2
− n)/2.
Рассмотрим конкретное применение алгоритма простого выбора.
Задача. Дана вещественнозначная матрица a с n строками и m столбцами.
Определим для каждой строки a
i
функцию f
(a
i
) = a
i1
− a
i2
+ a
i3
− . . . + (−1)
m
+1
a
im
Переставить строки матрицы a по неубыванию значений функции f .
const n=3; m=4;
type index=1..n;
element = array[1..m] of real;
mas = array[index] of element;
function f(s:element):real;
var i:integer; y:real;
begin y:=0;
for i:=1 to m do if i mod 2 = 0 then y:=y
−s[i]
else y:=y+s[i];

106
Глава 5. Массивы и строки
f:=y end;
procedure sort(var a:mas);
var i,j,k:index;
x:element;
begin for i:=1 to n
−1 do begin k:=i; x:=a[i];
for j:=i+1 to n do if f(a[j])< f(x) then begin k:=j; x:=a[j] end;
a[k]:=a[i]; a[i]:=x end;
end;
var a:mas;
begin
{ввод матрицы a}
sort(a);
{печать матрицы a}
end.
Сортировка простым обменом («метод пузырька»)
Метод:
Будем представлять массив в виде столбца элементов — первый элемент масси- ва является самым верхним. Сравниваем и обмениваем два соседних элемента до тех пор, пока не будут рассортированы все элементы. На каждом шаге, двигаясь снизу вверх, меняем все подходящие пары. «Легкие» элементы «всплывают» вверх после каждого прохода.
44 06 06 06 06 06 55 44 12 12 12 12 12 55 44 18 18 18 42 12 55 44 42 42 94 42 18 55 44 44 18 94 42 42 55 55 06 18 94 67 67 67 67 67 67 94 94 94
Алгоритм:
for i:=2 to n do for j:=n downto i do
{если a[j] и a[j
−1] не в нужном порядке, то их меняем местами}
Число перемещений в среднем равно 3 n
2
/4, в худшем случае — 3 n
2
/2. Число сравнений равно (n
2
− n)/2.

Контрольные вопросы по главе 5
107
Сортировка слиянием
Слияние обозначает объединение двух или более упорядоченных последова- тельностей в одну упорядоченную последовательность. Можно, например, слить две последовательности — (503, 703, 765) и (087, 512, 677), получив (087, 503, 512,
677, 703, 765).
Простой способ сделать это — сравнить два наименьших элемента, вывести наименьших из них (или оба — если они равны) и повторить эту процедуру.
Начав с
503, 703, 765 087, 512, 677
получим
503, 703, 765
=> 087 512, 677
затем
703, 765
=> 087, 503 512, 677
и т. д. Необходимо позаботиться о действиях на случай, когда исчерпается одна из последовательностей.
Общий объем работы, выполняемый алгоритмом слияния, пропорционален сумме длин исходных последовательностей.
Контрольные вопросы по главе 5 1. Ответьте на следующие вопросы:
А. Может ли массив содержать один элемент? А ни одного?
Б. Можно ли во время выполнения программы изменить размер массива
(количество элементов в нем)?
В. Верно ли, что тип элементов массива может быть любым?
Г. Может ли типом индекса массива быть тип integer или real?
2. Какие операции над массивами (как едиными объектами) допустимы в Пас- кале?
3. Для решения каких из следующих задач нужны массивы, а в каких задачах можно обойтись и без них?
А. Дано 50 чисел. Найти их среднее арифметическое.
Б. Дано 50 чисел. Определить, сколько среди них отличных от последнего числа.

108
Глава 5. Массивы и строки
В. Дано сто чисел. Напечатать сначала все отрицательные из них, а потом все остальные.
Г. Дано число a. Определить первый отрицательный член последователь- ности x
1
, x
2
, x
3
,. . ., где x
1
= a, x
n
+1
= tg
(x
n
).
4. Есть ли какое-нибудь преимущество у символьных массивов по сравнению со строками?
5. Попробуйте для массива, состоящего из 5 элементов, написать алгоритм,
отличный от всех рассмотренных выше.
Рекомендуемая литература к главе 5
[1]
Немнюгин С. А. Turbo Pascal / С. А. Немнюгин. — СПб. : Питер, 2001. —
496 г.
[2]
Фаронов В. В. Турбо Паскаль 7.0: Практика программирования / В. В. Фа- ронов. — М. : Нолидж, 2000. — 416 с.
[3]
Вирт Н. Алгоритмы + структуры данных = программы / Н. Вирт. — М. :
Мир, 1985. — 405 с.
[4]
Кнут Д. Искусство программирования / Д. Кнут. — 2-е изд. — М. : Вильямс,
2004. — Т. 3 : Сортировка и поиск. — 822 с.

Глава 6
ПЕРЕЧИСЛИМЫЙ ТИП, МНОЖЕСТВА,
ФАЙЛЫ
6.1 Перечислимый тип
6.1.1 Определение перечислимого типа
Скалярные стандартные и ограниченные типы — интуитивно понятная трак- товка типа как множество традиционных (целых, вещественных или символьных)
значений из определенного диапазона.
Перечислимые типы вводят некоторое простое обобщение такой трактовки посредством абстрагирования от «физической» природы значений.
Иными словами, можно определить новый тип путем явного перечисления всех
его возможных значений, причем каждое такое значение будет определяться
только именем.
Пример
Переменная программы, представляющая состояния светофора — введение перечислимого типа из трех значений red, green, yellow.
Синтаксис:
<перечислимый тип> ::= (<идентификатор> {, <идентификатор>})

110
Глава 6. Перечислимый тип, множества, файлы
Пример type color=(red,yellow,green);
week=(monday, tuesday, wednesday, thursday, friday,
saturday, sunday);
var v:color;
d:(left,up,right,down);
Boolean также является перечислимым типом: Boolean = (false, true).
Имена из списка перечислимого типа считаются константами соответствую- щего перечислимого типа. Эти идентификаторы должны быть уникальны. Недопу- стимо описание двух и более перечислимых типов с совпадающими константами.
Значения перечислимого типа упорядочены (в соответствии с описанием), по- рядковый номер начинается с 0. Применимы функции ord, pred, succ. К значе- ниям перечислимого типа применяются операции сравнения (сравниваются поряд- ковые номера). Переменные перечислимого типа могут использоваться в качестве параметра цикла.
Пример var d:week;
for d:=monday to sunday do S;
Допускается образование ограниченных типов из перечислимых по обычным правилам.
Пример type workweek = monday..friday;
Значения перечислимого типа нельзя использовать для непосредственного вво- да и вывода с помощью операторов read и write.

6.1 Перечислимый тип
111
6.1.2 Оператор варианта
Оператор варианта — обобщение условного оператора.
case v of red: write(
'красный');
yellow: write(
'желтый');
green: write(
'зеленый');
end;
writeln(
'цвет');
Синтаксис:
<оператор варианта> ::=
case
<выражение> of <альтернатива>{;<альтернатива>} end |
case
<выражение> of <альтернатива>{;<альтернатива>}<ветвь else> end
<альтернатива> ::= <константы> : <оператор>
<константы> ::= <константа> {, <константы>}|
<константа> .. <константа> {, <константы>}
<ветвь else> ::= else <оператор>{;<оператор>}
Семантика оператора:
а) вычисляется значение выражения — «переключателя»;
б) выбирается оператор, «помеченный» вычисленной константой;
в) выполняется оператор.
Если нет соответствующей константы, то выполняется ветвь else или ничего не выполняется.
При использовании оператора варианта должны выполняться сле- дующие правила:
1. Значение выражения — «переключателя», записанного по- сле служебного слова case, должно принадлежать дискрет- ному типу (целый, символьный, ограниченный, перечисли- мый, булевский).
2. Все константы, предшествующие операторам альтернатив,
должны иметь тип, совпадающий с типом выражения.
3. Все константы в альтернативах должны быть уникальны;
диапазоны не должны пересекаться.
Пример case switch of
1..2,7: S1;
3,4,10..20: S2;

112
Глава 6. Перечислимый тип, множества, файлы
5,8: S3
else S4
end;
Пример type month=(jan,feb,mar,apr,may,jun,jul,aug,sep,oct,nov,
dec);
var m:month;
d:28..31;
По значению m присвоить переменной d число дней в месяце:
case m of apr,jun,sep,nov: d:=30;
feb: d:=29 else d:=31
end;
6.2 Множественный тип
6.2.1 Определение множественного типа
Чтобы ввести в язык Паскаль вычислительную структуру множеств, использу- ют множественный тип. Значения множественного типа, так же, как и массивы,
строятся из нескольких значений одного (базового) типа. Однако в отличие от массивов значение множественного типа может содержать любое количество раз-
личных элементов базового типа — от нуля элементов (пустое множество) до всех возможных значений базового типа. Иными словами, возможными значениями пе-
ременных множественного типа являются все подмножества значений базового
типа.
Множественный тип задается с помощью двух служебных слов — set и of —
и следующего за ним базового типа.
Пример type digits = set of 1..5;
var s:digits;
Переменная s в качестве значений может принимать следующие множества целых чисел: пустое множество, {1},. . ., {5}, {1, 2}, . . ., {4, 5}, {1, 3, 5}, . . ., {4, 5, 3, 2}, . . .,
{1, 2, 3, 4, 5} (всего 32 различных множества).

6.2 Множественный тип
113
• Все значения базового типа в множестве должны быть раз-
личны.
• Порядок «расположения» элементов в множестве никак не
фиксируется.
Каким может быть базовый тип множества?
• символьным,
• перечислимым,
• ограниченным.
Базовый тип должен содержать не более 256 значений. Если базовый тип —
ограниченный целый, то значения должны быть в диапазоне от 0 до 255.
Пример type elemColor = (red,yellow,blue);
color = set of elemColor;
В Паскале допускаются явные изображения значений множественного типа:
• пустое множество изображается [];
• в общем случае изображение строится из списка элементов множества,
разделенных запятыми, и весь список заключается в квадратные скобки.
Пример
[1,2,5]
[red,yellow]
В качестве элементов в изображении множества допускаются выражения, тип которых должен совпадать с базовым типом. Кроме того, можно указывать диа- пазоны значений. Так, например, следующие два множества равны: [1,3..5]
и [1,3,4,5]. Следующие изображения представляют одно и то же множество:
[1..3]
, [1,2,3],[1,2,3,1],[3,3,1,1,2,2,2,3].

114
Глава 6. Перечислимый тип, множества, файлы
Пример type setofchar = set of char;
digits = set of 0..100;
var mychars: setofchar;
mydig1,mydig2:digits;
x,y:0..100;
mychars:=[
'a'..‘z’,'’'..'9',' '];
mydig1:=[];
mydig2:=mydig1;
mydig1:=[x..x+10,0,y-1,y+1];
6.2.2 Операции с множествами
Множества языка Паскаль обладают свойствами математических множеств.
В частности, над ними можно выполнять те же операции.
Пусть A, B и C — переменные, принадлежащие одному множественному типу.
Тогда с помощью присваиваний мы можем выполнить известные операции над множествами.
Объединение множеств — бинарная, коммутативная и ассоциативная операция:
С:=A+B
Пересечение множеств — бинарная, коммутативная и ассоциативная операция:
C:=A*B
Разность множеств — бинарная операция: C:=A
−B.
Пример
[1,3]+[2,4] = [1..4]
[1..10]*[5..15] = [5..10]
[1,2]*[3,4] = []
[1..10]
− [5..15] = [1..4]
Как добавить элемент во множество? Для этого можно использовать объедине- ние множеств. Пример:
mydig1:=mydig1+[5];
Альтернативой оператору S := S + [x] является оператор Include(S,x).
Имеется и обратная процедура Exlude исключения элемента из множества. У этой

6.2 Множественный тип
115
процедуры два параметра, первый указывает множество, а второй — исключаемый элемент.
Проверить принадлежность элемента x множеству A можно с помощью бинар- ной булевской операции x in A.
Пример
2 in [1..10,21] = true,
5 in [1,2,x,10] = true тогда и только тогда, когда x = 5.
Использование постоянных множеств для проверок:
• (ch='a') or (ch='b') or (ch='x') or (ch='y') эквивалентно ch in
[
'a','b','x','y'];
• ('0'Проверка на равенство, неравенство и включения множеств проводятся с по- мощью операций:
• Равенство множеств — бинарная булевская операция A=B.
• Неравенство множеств — бинарная булевская операция A<>B.
• Множество A входит во множество B — бинарная булевская операция
A<=B (B>=A)
Операции < и > для множеств не используются.
Пример
Значение выражения [1,2,3] = [1,2] равно false.
Значение выражения [1,2,3] >= [1,2] равно true.
Значение выражения [s]<=[1..10] равно true, т. и т. т., когда 1
⩽ s ⩽ 10.
Пример
Задача. Состоят ли строки s[1] и s[2] из одних и тех же символов?
var s:array[1..2] of string;
a:array[1..2] of set of char a[1]:=[];a[2]:=[];
for i:=1 to 2 do for j:=1 to length(s[i]) do

116