Сортировка выбором
Для начала рассмотрим алгоритм сортировки выбором.
Суть алгоритма заключается в следующем: находим наименьший элемент в массиве и меняем его местами с элементом, находящимся на первом месте. Далее процесс повторяется, но уже начиная со второй позиции в массиве и так далее, пока не отсортируем весь массив.
Алгоритм для сортировки массива из N элементов.
1. Начинаем сортировку с 1-го элемента: i:=1.
2. Находим номер j минимального элемента среди элементов от i до N.
3. Меняем местами элементы i и j.
4. Если i < N-1, то увеличиваем значение i на 1 и возвращаемся к шагу 2.
5. Конец алгоритма. Массив отсортирован.
Пример: алгоритм сортировки выбором массива str
for i := 1 to n-1 do
begin
min:=i;
for j := i+1 to n do
if str[ j ]<str[ min ] then min := j;
if i<>j then
begin
t := str[ min ];
str[ min ] := str[ i ];
str[ i ] := t;
end;
end;
В лучшем случае (если исходная последовательность уже упорядочена) алгоритм произведет (N-1)*(N+2)/2 сравнений и 0 пересылок данных. В остальных же случаях количество сравнений останется прежним, а вот количество пересылок элементов будет равным 3*(N-1).
Сортировка вставкой
Сортировка вставкой позволяет упорядочить данные по мере их поступления. В этом случае при вводе каждого нового значения можно опираться на тот факт, что все предыдущие элементы уже образуют отсортированную последовательность. Таким образом, каждый очередной элемент продвигается назад до тех пор, пока не окажется на месте.
Алгоритм для сортировки массива из N элементов.
1. Начинаем сортировку со 2-го элемента: i:=2.
2. Запоминаем в отдельную переменную temp значение i-го элемента.
3. Начинаем поиск места нового элемента с позиции j=i-1.
4. Если j>0 и j-ый элемент больше temp, то помещаем j-ый элемент на позицию j+1, уменьшаем значение j на 1 и возвращаемся к шагу 4.
5. Помещаем значение temp на позицию j+1.
6. Если i < N, то увеличиваем значение i на 1 и возвращаемся к шагу 2.
7. Конец алгоритма. Массив отсортирован.
Пример: алгоритм сортировки вставкой массива str
for i := 2 to n do
begin
temp := str[ i ];
j := i-1;
while (j>=1) and (str[ j ]>temp) do
begin
str[j+1] := str[j];
dec(j);
end;
str[j+1] := temp;
end;
Пузырьковая сортировка
Еще одна простая сортировка, которая будет рассмотрена в данном параграфе, – это пузырьковая сортировка, которая относится к категории обменных. Здесь периодически просматривается массив и обмениваются, если нужно, близлежащие элементы – до тех пор, пока никаких обменов не потребуется.
Алгоритм для сортировки массива из N элементов.
1. Начинаем сортировку до N-го элемента: i:=N.
2. Начинаем просматривать элементы со 2-го: j:=2.
3. Если элемент j-1 больше элемента j, то меняем их местами.
4. Увеличиваем значение j на 1 (inc(j)).
5. Если j < i, то переходим к шагу 3.
6. Уменьшаем значение i на 1 (dec(i))
7. Если i > 1, то возвращаемся к шагу 2.
8. Конец алгоритма. Массив отсортирован.
Пример: алгоритм пузырьковой сортировки массива str
for i := n downto 2 do
for j:=2 to i do
if str[ j-1 ] > str[ j ] then
begin
t := str[ j-1 ];
str[ j-1 ] := str[ j ];
str[ j ] := t;
end;
Улучшенные сортировки
В отличие от простых сортировок, имеющих сложность ~N2, к улучшенным сортировкам относятся алгоритмы с общей сложностью ~N*logN.
Необходимо, однако, отметить, что на небольших наборах сортируемых данных (N<100) эффективность быстрых сортировок не столь очевидна: выигрыш становится заметным лишь при больших N. Следовательно, если необходимо отсортировать маленький набор данных, то выгоднее взять одну из простых сортировок.
Среди улучшенных сортировок можно выделить сортировки Шелла, пирамидальную и др.
Существует так называемая «Быстрая сортировка», имеющая среднюю сложность порядка N*logN, являющаяся усовершенствованием обменных сортировок. Реализация такой сортировки наиболее удобна в рекурсивном варианте.
Подробнее с указанными и другими видами сортировок можно познакомиться в специальной литературе.
Вопросы для самопроверки
1. В чем суть алгоритма бинарной сортировки данных?
2. В чем суть алгоритма пузырьковой сортировки данных?
3. В чем суть алгоритма сортировки данных вставкой?
4. Какие улучшенные алгоритмы сортировки данных Вы знаете?
§12. Строковый тип
Для хранения текста можно использовать массив символов. Однако для этих целей в языке Паскаль имеется специальный строковый тип – String.
Описание строковых переменных
Значением строкового типа является последовательность символов.
Строковый тип описывается с помощью ключевого слова String, после которого в квадратных скобках указывается длина строки. Длина строки может быть от 1 до 255 символов.
Пример: описание строковых переменных фиксированной длины
type
MyString: String[30];
var
s1: MyString;
s2: String[25];
Если квадратных скобок не следует, то описанная переменная является строкой переменной длины, в которую можно записать до 255 символов.
Пример: описание строковых переменных переменной длины
var s: String;
Тип String без указания длины совместим со всеми типами строк.
Особенностью строковых переменных является то, что к ним можно обращаться как к скалярным переменным, так и как к массивам. Во втором случае применяется конструкция "переменная с индексом", что обеспечивает доступ к отдельным символам строки. При этом нижняя граница индекса равна 1. Отдельный символ строки совместим с типом Char.
Пример: обращение к отдельным символам массива
var s: String;
…
s:=’Вася’;
s[3]:=’н’; { Итог: s=’Ваня’ }
В памяти ЭВМ строка занимает количество байтов, на единицу большее ее длины. Нулевой байт строки содержит ее длину.
Операции над строками
Для строк определены операции присваивания, слияния (конкатенации) и сравнения.
Для сравнения строк применяются все операции отношения. Сравнение строк происходит посимвольно, начиная с первого символа. Строки равны, если имеют одинаковую длину и посимвольно эквивалентны.
Строки могут быть элементами списка ввода–вывода, при этом записывается имя строки без индекса.
При вводе строковых переменных количество вводимых символов может быть меньше, чем длина строки. В этом случае вводимые символы размещаются с начала строки, а оставшиеся байты заполняются пробелами. Если количество вводимых символов превышает длину строки, лишние символы отбрасываются.
В программе переменную строкового типа можно:
ü заполнять, например readln(s);
ü выводить значение на экран – writeln(s);
ü присваивать в строковую переменную какой-либо текст – s:=’Вася’;
ü присваивать значение строки другой строковой переменной – s2:=s;
ü «склеивать» с другими строками (конкатенация) – s:=s2+’!!!’;
ü сравнивать строки – s=s2.
Инициализация строк может производиться и с помощью типизированных констант.
Пример: инициализация строк с помощью типизированных констант
const sName: String[9] = ‘IBM PC/AT’;
Процедуры и функции для работы со строками
Для работы со строками в языке программирования Паскаль включены процедуры и функции, которые обеспечивают редактирование и преобразование строк.
Length(s) | Возвращает длину строки s |
Delete(s, Index, Count) | Удаляет в строке s Count символов, начиная с позиции Index |
Insert(Substr, Dest, Index) | Вставляет в строку Dest подстроку Substr с позиции Index |
Pos(Substr, s) | Возвращает позицию подстроки Substr в строке s либо 0, если Substr не входит в s |
Copy(s, Index, Count) | Возвращает подстроку строки s, Count символов, начиная с позиции Index |
Пример: работа со строками
readln(s);
s:=s+‘,_’+s+’!!!’;
writeln(s);
Пример: вывод всех символов строки s по отдельности
readln(s);
for i:=1 to length(s) do writeln(s[i]);
Вопросы для самопроверки
1. Как описываются строки в языке Паскаль?
2. Чем различаются строки фиксированной и переменной длины?
3. Какие операции допустимы над строками?
4. Какие процедуры и функции для работы со строками Вы знаете?
5. Что возвращает функция Length(s)?
6. Назовите основные отличия строки от массива символов.
§13. Записи
Записи, как и массивы, являются структурами прямого доступа, однако, в отличие от последних, могут хранить элементы различных типов данных.
Таким образом, запись – это вектор, компоненты которого могут относиться к разным типам данных.
Объявление записи
Запись представляет собой совокупность ограниченного числа логически связанных компонент, принадлежащих к разным типам.
Компоненты записи называются полями, каждое из которых определяется именем. Поле записи содержит имя поля, вслед за которым через двоеточие указывается тип данных этого поля. Поля записи могут относиться к любому типу, допустимому в языке Паскаль. Имена полей должны быть уникальны в пределах записи, но могут совпадать с именами переменных, описанных за пределами записи.
Описание записи в языке Паскаль осуществляется с помощью служебного слова Record, вслед за которым описываются поля записи. Завершается описание записи служебным словом end:
record
<имя поля 1>: <тип данных поля 1>;
[ <имя поля 2>: <тип данных поля 2>; ]
[ … ]
[ <имя поля n>: <тип данных поля n>; ]
end;
Так же, как и при описании переменных в разделе var, если несколько полей имеют одинаковый тип, то их описания можно объединить.
Например, записная книжка содержит фамилии, инициалы и номера телефона, поэтому отдельную строку в записной книжке удобно представить в виде следующей записи:
Пример: записная книжка – описание в разделе type
type
TRow=Record
FIO: String[20];
TEL: String[7]
end;
var
str: TRow;
Так, выше описана запись, содержащая два поля – FIO и TEL.
Описание записей возможно и без задания имени типа (в таком случае запись описывается в разделе var непосредственно после имени переменной).
Пример: записная книжка – описание в разделе var
var
str: Record
FIO: String[20];
TEL: String[7]
end;
Обращение к записям
Обращение к записи в целом допускается только в операторах присваивания, где слева и справа от знака присваивания используются имена записей одинакового типа.
Пример: присваивание одной записи другой
var X, Y: TRow;
…
X:=Y;
Y:=X;
Во всех остальных случаях оперируют отдельными полями записей. Чтобы обратиться к отдельной компоненте записи, необходимо задать имя записи и через точку указать имя нужного поля. Такое имя называется составным.
Пример: обращение к полям записи
str.FIO, str.TEL
Компонентой записи может быть другая запись. В таком случае составное имя будет содержать не два, а большее количество имен.
Пример: запись как поле записи (окружность)
type
TPoint = record
x, y: real;
end;
TCircle = record
center: TPoint;
radius: real;
color: integer;
end;
var Circle: TCircle;
…
Circle. color:=0;
readln(Circle. radius);
Circle. center. x:=10;
Circle.center.y:=5.5;
Оператор присоединения WITH
Если в программе необходимо несколько раз подряд обратиться к полям одной записи, то это может оказаться неудобным.
Пример:
var Circle: TCircle;
…
Circle. color:= 0;
Circle. center. x:= 10;
Circle. center. y:= 5.5;
Circle. radius:= sqr(Circle. center. x)+ sqr(Circle. center. y);
Обращение к компонентам записи в таком случае можно упростить, если воспользоваться оператором присоединения with.
Оператор with позволяет заменить составные имена, характеризующие каждое поле, просто на имена полей, а имя записи определить в операторе присоединения:
WITH M DO OP;
Здесь М – имя записи, ОР – простой или составной оператор. Оператор ОР представляет собой область действия оператора присоединения, в пределах которой можно не использовать составные имена.
Пример: использование оператора with
var Circle: TCircle;
…
with Circle do
begin
color:= 0;
center. x:= 10;
center. y:= 5.5;
radius:= sqr(center. x)+ sqr(center. y);
end;
Если внутри оператора with требуется обратиться к глобальной переменной, которая имеет такое же имя, как и одно из полей записи, то перед ней нужно указать через точку имя программы (раздел program).
Если внутри оператора with для некоторого имени явно не указано имя записи, то компилятор пытается интерпретировать его в следующей последовательности:
1) если в записи есть поле с искомым именем, то поиск заканчивается;
2) если в записи поля с таким именем нет, а рассматриваемый оператор with является вложенным в другой оператор with, то поиск производится среди полей внешней записи;
3) если среди полей всех вложенных записей нет искомого имени, компилятор считает его глобальной переменной.
Записи с вариантами
Иногда содержимое отдельной записи зависит от значения одного из ее полей (например, одно из полей определяет тип оборудования, от которого может зависеть набор его характеристик). В языке Паскаль допускается описание записи, состоящей из общей и вариантной частей. Вариантная часть при этом задается с помощью конструкции
CASE P OF,
где Р – имя поля из общей части записи.
Возможные значения, принимаемые этим полем, перечисляются так же, как и в операторе выбора case. Однако вместо указания выполняемого действия, как это делается в операторе case, здесь указываются поля варианта, заключенные в круглые скобки. Описание вариантной части завершается служебным словом end.
Тип поля Р можно указать в заголовке вариантной части.
Пример: тип поля Р указан в заголовке вариантной части
case P: Integer of
Далее рассмотрим следующий пример: описать запись для хранения данных: имя, фамилия, дата рождения. Для граждан хранить место рождения, для иностранцев – страну, дату прибытия и дату отъезда.
Пример: описание записи с вариантной частью
record
firstName, lastName: string[40];
birthDate: Date;
case citizen: boolean of
True: (birthPlace: string[40]);
False: (country: string[20];
entryDate : Date;
exitDate : Date);
end;
Инициализация записи
Инициализация записей может осуществляться как программно, так и с помощью типизированных констант. В случае описания записи в виде типизированных констант в круглых скобках перечисляются имена полей и через двоеточие указываются их значения. Друг от друга поля отделяются точкой с запятой.
Пример: описание записи в виде типизированной константы
type
RecType = Record
x, y: Word;
ch: Char;
dim: Array[1..3] of Byte
end;
const
Rec: RecType = ( x: 127; y: 255;
ch: 'A';
dim: (2, 4, 8) );
Описание записей в виде обычных (нетипизированных) констант недопустимо.
Вопросы для самопроверки
1. Чем записи отличаются от массивов?
2. Как называются переменные, описываемые внутри записи?
3. Как описываются записи в языке Паскаль?
4. Как происходит обращение к полям записи?
5. Для чего служит оператор With?
§14. Множества
Множество (Set) – это структурированный тип данных, который позволяет хранить до 256 элементов. Основное отличие множества от массивов и строк заключается в том, что его элементы не упорядочены.
Таким образом, множества используют там, где важен сам факт наличия того или иного элемента, вне зависимости от его позиции.
Например, множества подойдут тогда, когда нам нужно знать, какие студенты группы присутствовали на лекции. При этом нам не важно, в какой последовательности они пришли на занятие или ушли с него – важен лишь сам факт присутствия.
Описание множеств
Для описания множеств используют ключевое слово Set, за которым следует of и указывается тип элементов множества:
SET OF <тип элементов множества>
Тип элементов множества может быть любым порядковым, размер которого не превышает 1 байт (256 элементов).
Указанная конструкция может использоваться как в разделе type, так и в разделе var.
Пример: описание множеств
type
TMySet = Set of Char; {множество из 256-ти элементов (символов)}
var
s1: TMySet;
s2: Set of 'a'..'z', 'A'..'Z'; {множество из 52-х элементов (лат. букв)}
s3: Set of 0..10; {множество из 11-ти элементов}
s4: Set of Boolean; {множество из 2-х элементов}
Операции над множествами
В языке Паскаль реализованы все теоретико-множественные операции.
Таблица 14.1.
Операции над множествами в языке Паскаль
Операция | Запись |
1) Пересечение двух множеств s1 и s2 | s:=s1*s2; |
2) Объединение двух множеств s1 и s2 | s:=s1+s2; |
3) Разность двух множеств s1 и s2 (все элементы, которые принадлежат множеству s1 и одновременно не принадлежат множеству s2) | s:=s1-s2; |
4) Проверка принадлежности элемента el множеству s (результат этой операции имеет тип Boolean) | el in s |
5) Обозначение для пустого множества | [] |
6) Создание множества из списка элементов | s:=[e1,_,eN]; |
7) Проверка двух множеств на равенство или строгое включение (результат этих операций имеет тип boolean) | s1 = s2 s1 > s2 s1 < s2 |
Чтобы представить набор констант в виде множества в тексте программы, необходимо заключить их в квадратные скобки:
[<список_элементов>]
Список элементов может быть задан перечислением значений через запятую или интервалом. Элементы и границы интервалов могут быть переменными, константами и выражениями. Если левая граница интервала окажется больше правой, результатом будет пустое множество.
Пример: задание различных множеств:
if c in ['a','e','i','o','u']
then writeln('Гласная буква');
if set1 < [k*2+1..n, 13] then set1:=[];
Следует отметить, что не существует такой процедуры, которая позволила бы распечатать содержимое множества на экране. Выполнить это можно лишь программно.
Пример: печать на экране элементов множества
var
s1: Set of ‘1’..’10’;
i: Integer;
…
for i:=1 to 10 do
if i in s1 then writeln(i);
Пример использования множеств
Задача №1. Пользователь вводит 20 строк (маленькими буквами). Напечатать на экране в алфавитном порядке набор первых символов вводимых строк. Если в разных строках на первой позиции находится один и тот же символ, напечатать его один раз.
Пример:
program primer1;
type tchars = set of char;
var
s: string;
ch: tchars;
i: integer;
c: char;
begin
ch:=[];
for i:=1 to 20 do
begin
readln(s);
ch:=ch + [ s[1] ];
end;
for c:=’a’ to ‘z’ do
if c in ch then writeln(c);
end.
Задача №2. Пользователь вводит текст из 20 строк. Напечатать на экране все цифры (по одному разу), которые входят в текст.
Пример:
program primer2;
type
tdigits = set of ‘0’..’9’;
var
s: string;
dig: tdigits;
i, j: integer;
c: char;
begin
dig:=[];
for i:=1 to 20 do
begin
readln(s);
for j:=1 to length(s) do
if s[j] in [‘0’..’9’] then dig:=dig + [ s[j] ];
end;
for c:=’0’ to ‘9’ do
if c in dig then writeln(c);
end.
Множества как типизированная константы
Задать множество как типизированную константу можно следующим образом:
<имя_константы> : SET OF <тип_эл-тов> = [<список_эл-тов>];
Пример:
type
digits = set of '0'..'9';
const
odds: digits = ['1', '3', '5', '7', '9'];
vowels: set of 'a'..'z' = ['a', 'o', 'e', 'u', 'i'];
Отметим, что множество нельзя задать в виде нетипизированной константы.
Вопросы для самопроверки
1. Что такое множество?
2. Чем множества отличаются от массивов? От записей?
3. Какое максимальное количество элементов может включать в себя множество?
4. Какие операции допустимы над множествами?
5. Учитывает ли множество количество вхождений в него элементов? Порядок следования элементов?
§15. Процедуры и функции
Нередко случаются ситуации, когда одни и те же действия или вычисления необходимо выполнять многократно, но над разными данными.
Пример: в программе нужно сначала найти максимум из чисел a и b, затем – из x и y, и т. д.
При написании исходного кода программы в такой ситуации, конечно, можно несколько раз записать одни и те же операторы в разных местах. Однако можно поступить и по-другому.
Алгоритм решения задачи может быть спроектирован путем декомпозиции всей задачи на отдельные подзадачи. Такие подзадачи обычно реализуются в виде подпрограмм.
Подпрограмма – это последовательность операторов и описаний, которые определены и записаны только в одном месте программы, однако могут быть вызваны для выполнения из нескольких точек программы.
В языке программирования Паскаль существуют два типа таких подпрограмм – процедуры и функции.
Понятие процедуры и функции
Процедуры и функции – это именованные последовательности описаний и операторов (подпрограммы).
Основное различие между процедурами и функциями состоит в том, что функция возвращает некоторое значение и может использоваться в выражениях, в то время как процедура вызывается для выполнения какого-либо действия.
Пример:
x := sin(A); - здесь sin – это функция. Она возвращает значение.
writeln('Это проверка'); - здесь writeln – это процедура. Она выполняет действие (печать на экране), но результата не возвращает.
Можно сказать, что функции – это процедуры особого характера, результатом работы которых является некоторое значение. В то же время в некоторых других языках программирования процедуры реализуются в виде функций, которые не возвращают результат.
При использовании процедур или функций программа на языке Паскаль должна содержать:
а) объявление и описание процедуры или функции;
б) вызов процедуры или функции.
Если текст процедуры включается непосредственно в текст программы, то его необходимо поместить в разделе описания процедур и функций, до ключевого слова begin, означающего начало исходного кода самой программы (см. §4).
Для вызова процедуры или функции в тексте программы указывают имя подпрограммы, а также список фактических параметров (будут рассмотрены позже).
Вызов процедуры может быть записан отдельным оператором (например, writeln, readln).
Вызов же функции, в отличие от процедур, не может быть отдельным оператором, т. к. она всегда возвращает некоторое значение, которое необходимо куда-то сохранить или вывести (например, sin, sqr).
В программе можно использовать не только собственные процедуры и функции, но и уже готовые, хранящиеся в специализированных библиотеках (например, writeln, readln, sin, sqr). Для использования уже готовых процедур и функций нужно предварительно в разделе uses указать имя модуля (библиотеки), в котором они хранятся. Если используются готовые подпрограммы из разных модулей, то их имена перечисляются через запятую.
Пример: используем в программе процедуру ClrScr из модуля Crt, очищающую экран.
uses сrt;
…
begin
ClrScr;
…
end.
Структура процедуры
Описание подпрограммы начинается с ее объявления. В случае процедур объявление выглядит следующим образом.
procedure <имя-процедуры> (<параметры>);
Список параметров в круглых скобках указывается при необходимости, для передачи данных внутрь процедуры. Подробнее параметры будут рассмотрены позже.
Далее следуют блок описания процедуры. Процедура на языке Паскаль может содержать такие же разделы описаний, что и основная программа, а именно: меток, констант, типов, переменных, процедур и функций (за исключение модулей).
label <метки>;
const <описания констант>;
type <определения типов данных>;
var <описания переменных>;
<процедуры и функции>
begin
<основное тело процедуры>;
end;
Следует обратить внимание, что любая процедура может содержать в себе описание других процедур и функций – вложенных.
Описания двух различных подпрограмм не могут пересекаться: каждый блок должен быть логически законченным.
Пример: написать программу, которая печатает на экране слово МАМА (в столбик).
program mama;
procedure M;
begin
writeln(‘** **’);
writeln(‘* * * *’);
writeln(‘* * *’);
writeln(‘* *’);
writeln(‘* *’);
end;
procedure A;
begin
writeln(‘ ***’);
writeln(‘* *’);
writeln(‘*****’);
writeln(‘* *’);
writeln(‘* *’);
end;
begin
M;
A;
M;
A;
end.
Структура функции
Функции имеют такую же структуру, как и процедуры. Исключением является объявление функции.
function <имя_функции> (<параметры>) : <тип данных>;
Так же, как и в случае с процедурами, параметры используются только при необходимости.
Как упоминалось ранее, функция всегда возвращает результат. При объявлении функции всегда указывается тип данных возвращаемого результата (см. выше).
В операторной части функции (основное тело функции) задаются операторы, которые должны выполняться при вызове функции. В случае с функцией здесь должен содержаться по крайней мере один оператор присваивания, в котором имени (идентификатору) функции присваивается некоторое значение. Результатом функции является последнее присвоенное имени функции значение. Если такой оператор присваивания отсутствует или не был выполнен, то значение, возвращаемое функцией, не определено.
Пример: функция GetNumber запрашивает число у пользователя
function GetNumber: Real;
var Responce: Real;
begin
write('Введите число: ');
readln(Response);
GetNumber := Response;
end;
Формальные параметры
В описании процедур и функций, как было отмечено выше, может быть задан список параметров (формальных параметров). Такие параметры принимают значения, передаваемые в подпрограмму извне во время ее вызова.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 |
