- •Конспект лекций
- •1.4 Общая структура программы
- •1.5 Стандартные процедуры и функции
- •1.6 Процедуры ввода/вывода
- •2. Простые типы данных
- •2.1 Целые типы
- •2.2 Вещественные типы
- •2.3 Cимвольный тип данных
- •2.4 Логический тип данных.
- •2.5 Ограниченные типы
- •2.6 Перечислимые типы
- •2.7 Описание типов
- •2.8 Преобразование типов
- •2.9 Порядок вычисления выражений
- •3. Операторы языка Паскаль
- •3.1 Оператор присваивания
- •3.2 Составной оператор
- •3.3 Условный оператор
- •3.4 Оператор выбора case
- •3.5 Оператор цикла с параметром (цикл for)
- •3.6 Оператор цикла с предусловием (цикл while)
- •1 Вариант:
- •2 Вариант:
- •3 Вариант:
- •3.7 Оператор цикла с постусловием (цикл repeat)
- •3.8 Вложенные циклы
- •3.9 Оператор перехода goto
- •4. Массивы
- •4.2 Сортировка элементов массива
- •4.3 Многомерные массивы
- •5. Подпрограммы (процедуры и функции)
- •5.1 Процедуры
- •5.2 Функции
- •5.3 Области действия имен
- •5.4 Параметры процедур и функций
- •5.5 Побочные эффекты при использовании подпрограмм
- •5.6 Передача массивов в подпрограммы
- •5.7 Параметры-костанты
- •5.8 Массивы открытого типа
- •5.9 Рекурсия в подпрограммах
- •6. Строковый тип данных
- •6.1 Описание строк
- •6.2 Операции со строками
- •6.3 Процедуры и функции для работы со строками
- •7. Стандартные модули Турбо-Паскаля
- •7.1 Модули турбо3 и graph3
- •7.2 Модуль overlay
- •7.3 Модуль dos
- •7.4 Модуль system
- •7.5 Модуль printer
- •7.6 Модуль crt
- •7.7 Модуль graph
- •8. Записи
- •8.1 Определение записи
- •8.2 Оператор над записями
- •8.3 Вложенные записи
- •8.4 Массив записей
- •8.5 Записи с вариантами
- •9. Файлы
- •9.1 Определение файла
- •9.2 Процедуры и функции для работы с файлами
- •9.3 Нетипизированные файлы
- •10. Интегрированная среда Турбо Паскаля
- •10.1 Как начать работу с Турбо Паскалем
- •10.2 Ваша первая программа
4.2 Сортировка элементов массива
Сортировкой массива называется расстановка элементов массива в возрастающем или убывающем порядке.
Существует множество методов сортировки, рассмотрим два наиболее простых и распространенных метода: метод прямого выбора и метод «пузырька».
Метод прямого выбора (через поиск максимального и минимального элемента).
Алгоритм сортировки по возрастанию (через поиск минимального элемента):
Определяется минимальный элемент массива и помещается на 1-е место
Среди оставшихся элементов (начиная со 2-го) определяется минимальный элемент и помещается на 2-е место.
Среди оставшихся элементов (начиная со 3-го) определяется минимальный элемент и помещается на 3-е место.
И т.д. до конца массива.
Пример:
3 5 8 7 1
1|5 8 7 3
1 3|8 7 5
1 3 5 7 8
Программа:
var a: array [1..10] of real;
i,j: integer;
t: real;
begin
randomize;
for i:= 1 to 10 do
begin
a[i]:=random;
write(a[i]:6:3);
end;
writeln;
for i:= 1 to 9 do
for j:=i+1 to 10 do
if a[i]>a[j] then
begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
end;
for i:= 1 to 10 do write (a[i]:6:3);
end.
Для обмена значениями двух переменных обычно используют дополнительную переменную (дополнительную ячейку памяти), в приведенной выше программе – это переменная t.
Метод «пузырька» (перестановок).
Алгоритм сортировки по возрастанию:
Сравниваются попарно соседние элементы: 1-й со 2-м, 2-й с 3-м, 3-й с 4-м и т.д. до конца массива. Если соседние элементы расположены не по возрастанию, то они меняются местами. Таким образом, максимальный элемент массива «всплывает» на последнее место.
Снова сравниваются попарно соседние элементы и меняются местами, если не по возрастанию. Всплывает элемент, меньший максимального, на предпоследнее место.
И т.д. до тех пор, пока будут перестановки.
Пример:
3 5 8 7 1
3 5 7 1 8
35 1 7 8
3 1 5 7 8
1 3 5 7 8
Программа:
var a: array [1..10] of real;
i: integer;
t: real;
b: boolean;
begin
randomize;
for i:= 1 to 10 do
begin
a[i]:=random;
write(a[i]:6:3);
end;
writeln;
repeat
b:=false;
for i:= 1 to 9 do
if a[i]>a[i+1] then
begin
t:=a[i];
a[i]:=a[i+1];
a[i+1]:=t;
b:=true;
end;
until b=false; {Если b=false – это значит, что не было ни одной перестановки. Следовательно,
массив отсортирован, переходим к выводу отсортированного массива на экран: }
for i:= 1 to 10 do write(a[i]:6:3);
end.
4.3 Многомерные массивы
В качестве элементов массива могут быть значения любого типа, в том числе и массивы, например:
var a: array [N1..N2] of array [N3..N4] of real;
Обычно используют более короткую форму записи:
var a: array [N1..N2, N3..N4] of real; - двумерный массив (матрица), имеет два размера:
N1..N2 – диапазон изменения первого индекса (номер строки)
N3..N4 – диапазон изменения второго индекса (номер столбца)
Пример 1:
var a: array [1..3, 1..4] of integer;
a11 a12 a13 a14
a21 a22 a23 a24
a31 a32 a33 a34
Пример 2:
var b: array [1..5, 1..5, 1..5] of real; - трехмерный массив
Мы будем использовать только одномерные и двумерные массивы.
Обращение к элементам: a[1,3]:=0;
a[3,2]:=5;
В памяти:
-
1
2
3
4
1
0
2
3
5
Замечание: Размер любого массива не должен превышать 64 кбайта.
Как вычислить размер массива рассмотрим на примере 1. Массив a имеет размер 3x4, т.е. состоит из 12-ти элементов. Элементы массива a целого типа, т.е. каждый элемент занимает 2 байта памяти. Следовательно, весь массив занимает 24 байта памяти.
При обработке матрицы внешний цикл может быть по номеру строки, а внутренний цикл – по номеру столбца матрицы:
for str:= 1 to 3 do
for stb:= 1 to 4 do
write (a[i,j]);
либо наоборот: внешний цикл - по номеру столбца, а внутренний цикл – по номеру строки матрицы:
for stb:= 1 to 4 do
for str:= 1 to 3 do
write (a[i,j]);
В результате выполнения 1-го фрагмента программы увидим на экране содержимое элементов массива в следующем порядке: a11 a12 a13 a14 a21 a22 a23 a24 a31 a32 a33 a34
В результате выполнения 2-го фрагмента программы - в другом порядке:
a11 a21 a31 a12 a22 a32 a13 a23 a33 a14 a24 a34
Пример 3: Заполнить матрицу размерностью 5х10 целыми случайными числами в диапазоне от 0 до 99 и найти минимальный элемент матрицы и сумму элементов.
var m: array [1..5,1..10] of integer;
i,j,s, min: integer;
begin
randomize;
for i:=1 to 5 do
begin
for j:=1 to 10 do
begin
m[i,j]:=random(100);
write(m[i,j]:4);
end;
writeln;
end;
s:=0; min:=m[1,1];
for i:=1 to 5 do
for j:=1 to 10 do
begin
s:=s+m[i,j];
if m[i,j]<min then min:=m[i,j];
end;
writeln(‘S = ’,s,’ min = ’,min);
end.
Пример 4: Сформировать матрицу размерностью 5х5, где aij=i*j , и вывести ее на экран;
определить сумму элементов каждого столбца матрицы и вывести полученные значения на экран.
var a: array [1..5,1..3] of integer;
sum,i,j: integer;
begin
for i:=1 to 5 do
begin
for j:=1 to 3 do
begin
a[i,j]:=i*j;
write(a[i,j]:4);
end;
writeln;
end;
for j:=1 to 3 do
begin
sum:=0;
for i:=1 to 5 do
sum:=sum+ a[i,j];
writeln(‘сумма ’,,j,’-го столбца = ’,sum);
end;
end.
Задачи для самоконтроля
4.1 Какой оператор является ошибочным?
var a: array [0..5] of integer;
p: integer;
Begin
a[1]:=8;
p:=5;
a[p+1]:=7;
4.2 Определите значение sum после выполнения программы:
var a: array [1..2,1..3] of integer;
p, sum: integer;
Begin
a[1,1]:= 8; a[1,2]:= - 6; a[1,3]:= 2;
a[2,1]:= 4; a[2,2]:= 9; a[2,3]:= - 5;
for p:=1 to 2 do
sum:= sum + a[p,p];
end.