Info1415_L_Matrix
.pdf12 Массивы |
1 |
12 Массивы
Материалы к лекциям по курсу ¾Основы информатики1.
Пример 12.1 (плохой). Пусть описаны три вектора:
type Vector = array[1..5] of Integer;
var A, B, C : Vector; |
|
|
|
||||
|
|
|
|
Инициализация элементов массива (:=, ввод с клавиатуры) |
|
|
|
|
|
|
|
|
|
||
1 |
a[5] := 4; |
a[3] := 2; a[1] := 0; a[2] := 1; a[4] := 3; |
|||||
2 |
b[1] := 4; |
b[2] := 2*a[5]; b[3] := -b[2]; |
|||||
3 |
b[4] := b[2] Div 3; |
b[5] := 3; |
|||||
4 |
Write(b[1], b[2], b[3], b[4], b[5]); |
||||||
5 |
Read(c[1], c[2], c[3], c[4], c[5]); |
||||||
|
|
|
|
||||
|
|
Легко пропустить ошибку (где a[1]? a[4] инициализирован дважды) |
|
||||
|
|
|
|||||
a[5] := 4; a[3] := 2; |
a[4] := 0; a[2] := 1; a[4] := 3; |
||||||
|
|
|
|
|
|
|
|
Пример 12.2. Пусть описаны два 1D массива:
Описание массивов const Max = 5; { число элементов }
type Vector = array[1..Max] of Integer;
var A, C : Vector;
i : Integer;
Инициализация элементов массива в цикле: a1 = 0, a2 = 1,. . .
for i := 1 to Max do a[i] := i - 1;
Ввод элементов массива в цикле for i := 1 to Max do Read(c[i]);
Пример 12.3. Формирование списка студентов учебной группы.
|
|
|
|
Обработка подмассивов |
|
|
|
|
|
|
|
1 |
const Max |
= 25; |
{ макс. число студентов } |
||
2 |
var A |
: array[1..Max] of string; |
|||
3 |
i, KS |
: Integer; |
{ KS - реальное число студентов } |
||
4 |
Fio |
: string; |
|
|
|
5begin
6 |
Write(’Вв. фамилию или 1 (выход) ’); ReadLn(Fio); |
7KS := 0;
8while (Fio <> ’1’) and (KS < Max) do
9begin
10 |
KS := KS + 1; |
|
11 |
a[KS] := Fio; |
{ занесение данных в массив } |
12 |
Write(’Вв. фамилию или 1 ’); ReadLn(Fio); |
|
13 |
end; |
|
1 Версия 1 от 13.11.2014. Автор: Ширяева Е. В. ЮФУ, мехмат.
2
14if KS = Max then WriteLn(’Массив полон’);
15WriteLn(’Список студентов’);
16for i := 1 to KS do WriteLn(i:3, ’ ’, a[i]);
17end.
Пример 12.4. Использование массивов в качестве параметров подпрограмм.
|
|
Процедура |
InputVec |
получение массива случайным образом |
|
||||
|
|
Процедура |
PrintVec |
печать массива |
|
||||
|
|
Процедура |
Plus |
сложение двух массивов |
|
||||
|
|
Функция |
Sravn |
сравнение двух элементов массива |
|
||||
|
|
|
|
|
Использование параметра-массива (начало) |
|
|
|
|
1 |
const NMax = 15; |
|
|
|
|||||
|
|
|
|
|
|||||
2 |
(* обязательное объявление типа *) |
|
|||||||
3 |
type Vec = array[1..NMax] of Integer; |
|
|||||||
|
|
|
|
|
|
||||
|
|
|
Использование параметра-массива (описание подпрограмм) |
|
|
||||
|
|
|
|
|
|||||
4 |
procedure InputVec(N: Integer; var A1: Vec); |
|
|||||||
5 |
var i: Integer; |
|
|
|
|
|
|||
6 |
begin |
|
|
|
|
|
7for i := 1 to N do A1[i] := Random(10);
8 |
end; {------------------------------------------------ |
} |
9 |
procedure PrintVec(N: Integer; const A1: Vec); |
|
10 |
var i: Integer; |
|
11begin
12for i := 1 to N do Write(A1[i]:4);
13Writeln;
14 |
end; {------------------------------------------------ |
} |
15 |
function Sravn(x, y: Integer): Boolean; |
|
16begin
17Sravn := x = y;
18 |
end; {------------------------------------------------ |
} |
19 |
procedure Plus(N: Integer; const A1, B1: Vec; var C1: Vec); |
|
20 |
var i: Integer; |
|
21begin
22for i := 1 to N do C1[i] := A1[i] + B1[i];
23end;
Тело программы
24 var A, B, C: Vec;
25begin
26Randomize; { иниц-ция датчика псевдослучайных чисел }
27 |
InputVec(5, A); |
PrintVec(5, A); |
28 |
InputVec(5, B); |
PrintVec(5, B); |
29 |
Plus(5, A, B, C); |
PrintVec(5, C); |
30WriteLn(Sravn(a[1], a[5]));
31end.
12 Массивы |
3 |
Пример 12.5.
Процедура печати массива произвольной длины
1procedure PrintMas(const A : array of Integer);
2var i: Integer;
3begin
4for i := Low(A) to High(A) do Write(A[i]:3);
5end;
Демонстрация работы с открытым массивом
1const M = 4;
2var i : Integer;
3SA : array[0..M] of Integer;
4SB : array[0..2*M] of Integer;
5
6begin
7Randomize;
8WriteLn(’Array A’);
9for i := 0 to M do SA[i] := Random(10);
10 |
PrintMas(SA); |
11 |
WriteLn; WriteLn(’Array B’); |
12for i := 0 to 2*M do
13SB[i] := Random(10);
14PrintMas(SB);
15end.
Пример 12.6. Найти Max/Min элемент в массиве и определить значение индекса этого элемента.
Поиск max элемента в массиве (описание типа)
1const NMax = 10;
2type Vec = array[1..NMax] of Integer;
Поиск max элемента в массиве (описание процедуры)
1procedure MaxMax(const A1: Vec; var iM: Integer);
2 var i : Integer;
3begin
4iM := 1;
5for i := 2 to NMax do
6if A1[i] > A1[iM] then iM := i;
7end;
8 |
|
|
|
9 |
var A |
: Vec; |
|
10 |
MaxI |
: Integer; |
(* номер макс. эл-нта *) |
11 |
begin |
... |
|
12MaxMax(A, MaxI);
13WriteLn(’Max = A[’, MaxI, ’] = ’, A[MaxI]);
14end.
4
Пример 12.7.
Линейный поиск-I
1ReadLn(T);
2{ ---------- поиск - цикл с постусловием ---------- }
3i := 0;
4repeat
5i := i + 1
6until (i = NMax) or (a[i] = T);
7
8{ ---------- или поиск - цикл с предусловием ---------- }
9i := 1;
10 |
while (i < NMax) and (a[i] <> T) do i := i + 1; |
11
12{ ---------- анализ результата поиска ---------- }
13if a[i] <> T then WriteLn(’Числа в массиве нет’)
14else WriteLn(’Номер первого вхождения ’, i);
Пример 12.8. Поиск методом фиктивного элемента.
Линейный поиск-II
1const NMax = 10;
2type Vec = array[1..NMax+1] of Integer;
3...
4ReadLn(T);
5a[NMax+1] := T; (* фиктивный элемент *)
6{ ---------- поиск - цикл с предусловием ---------- }
7i := 1;
8 |
while a[i] <> T do i := i + 1; |
9
10{ ---------- анализ результата поиска ---------- }
11if i = NMax+1 then WriteLn(’Числа в массиве нет’)
12else WriteLn(’Номер первого вхождения ’, i);
Пример 12.9.
Линейный поиск элемента в упорядоченном массиве a[NMax+1] := T;
i := 1;
while a[i] < T do i := i + 1;
(* анализ флага Found *)
Found := (a[i] = T) and (i <> NMax+1);
if not Found then
Writeln(’Элемента нет. Он мог бы стоять на месте ’, i) else
WriteLn(’Номер первого вхождения ’, i);
12 Массивы |
5 |
Пример 12.10. Проследим за процессом поиска элемента методом половинного деления на примере массива:
|
a1 = 3 a2 = 7 a3 = 8 a4 = 10 a5 = 13 a6 = 15 a7 = 16 a8 = 18 |
|
|||||||||||||||
|
|
a9 = 21 a10 = 23 a11 = 37 |
a12 = 39 |
a13 = 40 a14 = 44 a15 = 53 |
|
||||||||||||
|
|
СХЕМА |
|
|
|
|
|
|
Разыскиваемый элемент 43 |
||||||||
|
|
|
|
|
|
|
|
s |
a[s] |
a[s] < T |
p |
|
q |
||||
|
|
|
|
|
|
|
|
|
|
|
|||||||
s = (p + q) div 2 |
|
|
|
|
|
|
|
|
|
1 |
|
15 |
|||||
|
|
|
|
|
|
|
|
|
8 |
18 |
|
True |
9 |
|
15 |
||
as < T |
|
p |
|
q |
|
|
|
12 |
39 |
|
True |
13 |
|
15 |
|||
|
|
|
|
|
|||||||||||||
|
|
|
|
|
14 |
44 |
|
False |
13 |
|
14 |
||||||
|
|
|
|
|
|
|
|
|
|
|
|||||||
да |
|
s+1 |
|
прежнее |
|
|
|
||||||||||
|
|
|
|
|
13 |
40 |
|
True |
14 |
|
14 |
||||||
нет |
|
прежнее |
|
s |
|
|
|
|
|
||||||||
|
|
|
|
|
|
Результат поиска: элемента нет |
|||||||||||
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
Разыскиваемый элемент 7 |
|
|
|
|
||||||||
|
|
|
|
|
s |
|
a[s] |
a[s] < T |
|
p |
|
q |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
15 |
|
|
|
|
|
|
|
|
|
|
8 |
|
18 |
False |
1 |
|
8 |
|
|
|
|
|
||
|
|
|
|
4 |
|
10 |
False |
1 |
|
4 |
|
|
|
|
|
||
|
|
|
|
2 |
|
7 |
False |
1 |
|
2 |
|
|
|
|
|
||
|
|
|
|
|
1 |
|
3 |
True |
2 |
|
2 |
|
|
|
|
|
|
|
|
|
|
|
Результат поиска: элемент № 2 |
|
|
|
|
Пример 12.11 (удаление по номеру). Удалить элемент массива с заданным номером.
|
|
|
Удаление по номеру |
|
|
|
|
1 |
const NMax = 10; |
||
2 |
var a |
: array[1..NMax] of Integer; |
3i, Nom : Integer;
4 |
begin |
|
5 |
InputVec(Max, A); |
(* получение элементов массива *) |
6WriteLn(’№ удаляемого элемента ’);
7ReadLn(Nom);
8for i := Nom to NMax - 1 do
9 |
a[i] := a[i+1]; |
(* сдвиг влево *) |
10a[NMax] := 0;
11PrintVec(NMax-1, A);
12end.
Задание (удаление по значению) Пусть все элементы массива разные. Удалить из массива максимальный элемент.
Удаление по значению
Программу написать самостоятельно.
6
Пример 12.12 (вставка по номеру). Вставить некоторое заданное число в 1D массив на место с заданным номером.
Вставка по номеру
1program DemoIns;
2const M = 5;
3 var a : array[1..M+1] of Integer;
4i, k, x : Integer;
5begin
6InputVec(M, A);
7x := 8;
8Write(’Позиция? ’);
9ReadLn(k);
10for i := M downto k do a[i+1] := a[i];
11a[k] := x;
12PrintVec(M+1, A);
13end.
Пример 12.13. imax номер максимального элемента.
|
|
|
Сортировка выбором. Результат: a[1] < ... < a[n] |
|
|
|
|
1 |
for i |
:= N downto 2 do |
|
2 |
begin |
|
|
3(* поиск номера макс. эл-та *)
4imax := 1;
5 |
for |
j := 2 |
to i |
do |
6 |
if |
a[j] > |
a[imax] |
then imax := j; |
7
8(* перестановка эл-тов *)
9 |
y := a[imax]; |
a[imax] := a[i]; |
a[i] := y; |
10 |
end; |
|
|
Пример 12.14. imin номер минимального элемента.
|
|
|
Сортировка выбором. Результат: a[1] < ... < a[n] |
|
|
|
|
1 |
for i |
:= 1 to N do |
|
2 |
begin |
|
|
3(* пусть мин. значение у I эл-нта в подмассиве *)
4imin := i;
5for j := i + 1 to N do
6if a[j] < a[imin] then imin := j;
7(* перестановка элементов *)
8 |
y := a[imin]; |
a[imin] := a[i]; |
a[i] := y; |
9 |
end; |
|
|
12 |
Массивы |
|
|
|
7 |
|||
Пример 12.15. |
|
|
|
|
|
|
||
|
|
|
|
|
Сортировка обменом, I вариант |
|
|
|
|
|
|
|
|
|
|||
1 |
for |
i := 1 |
to |
N - |
1 |
do |
||
2 |
for |
j := 1 |
to |
N |
- i |
do |
3begin
4 |
if a[j] > a[j+1] then |
5begin
6y := a[j];
7a[j] := a[j+1];
8a[j+1] := y;
9end;
10 end;
Пример 12.16.
Сортировка обменом, II вариант
1 Sort := True; (* массив надо сортировать *)
2i := 1;
3while Sort do
4begin
5Sort := False;
6 |
for j := 1 to N - i do |
7begin
8 |
if a[j] > a[j+1] then |
9begin
10 |
Sort |
:= True; |
(* |
есть перестановка *) |
11 |
y := |
a[j]; |
a[j] |
:= a[j+1]; a[j+1] := y; |
12end;
13end;
14i := i+1;
15end;
Пример 12.17.
Сортировка включением, I вариант
1for i := 2 to N do
2begin
3y := a[i];
4j := i - 1;
5while (j >= 1) and (y < a[j]) do
6begin
7 |
a[j+1] := a[j]; |
j := j - 1; |
8end;
9a[j+1] := y;
10 end;
Условие j >= 1 предотвращает выход за начало списка.
8
Пример 12.18. |
|
|
|
|
|
|
|
II вариант |
|
|
|
|
|
|
1 |
for i := 2 to N do |
|||
2 |
begin |
|
|
|
3 |
y := a[i]; |
j := i - 1; |
||
4 |
a[0] := y; |
{ new - барьерный элемент } |
5while y < a[j] do { new - новая проверка }
6...
7 end;
Пример 12.19.
Сортировка включением, III вариант (начало I шаг метода выбора)
1 imin := 1;
2 for i := 2 to N do
3if a[i] < a[imin] then imin := i;
4 |
if imin <> 1 |
then { перестановка только если a[1] > a[2] } |
|
5 |
begin |
|
|
6 |
y := a[1]; |
a[1] := a[imin]; |
a[imin] := y; |
7 |
end; |
|
|
1
2
3
4
5
6
Сортировка включением, III вариант (продолжение метод вставок) for i := 3 to N do
begin
y := a[i]; j := i - 1;
while y < a[j] do
...
Алгоритм слияния для упорядоченных по неубыванию массивов
c1 = min(a1; b1);
если min(a1; b1) = a1, то на следующем шаге сравниваются a2 и b1, если min(a1; b1) = b1, то будут сравниваться a1 и b2 и т. д.
Если на очередном шаге окажется, что из одного входного массива все элементы переписаны в C, то элементы из другого массива дописываются в C (без дополнительных проверок).
AB
|
|
Внизу указан номер элемента в новом массиве. |
|
12 |
11 |
||
|
|||
44 |
23 |
C = 1 1 2 4 4 10 12 13 14 19 |
|
45 |
106 |
||
|
|||
149 |
127 |
При описании массива C следует учесть: nC = nA + nB, |
|
|
138 |
где nA, nB, nC кол-во элементов массивов A, B, C. |
|
|
1910 |
|
12 Массивы |
9 |
||||
Пример 12.20. |
|
|
|
||
|
|
Слияние двух упорядоченных массивов (раздел описаний) |
|
|
|
|
|
|
|||
const nA = 4; |
|
|
|
||
nB = 6; |
|
|
|
||
var A |
: array[1..nA] of Byte = (1, 4, 4, 14); |
|
|||
B |
: array[1..nB] of Byte = (1, 2, 10, 12, 13, 19); |
|
|||
C |
: array[1..nA+nB] of Byte; |
|
|||
i,j,k : Integer; |
|
|
|
||
begin |
|
|
|
|
|
// заполнение нового массива |
|
||||
i := 1; |
j := 1; k := 1; |
(* для A, B и C *) |
|
||
while (i <= nA) and (j <= nB) do |
|
||||
begin |
|
|
|
|
|
if a[i] < b[j] then |
|
|
|
||
begin |
|
|
|
|
|
c[k] := a[i]; |
|
|
|
||
i := i + 1; |
|
|
|
||
end |
|
|
|
|
|
else |
|
|
|
|
|
begin |
|
|
|
|
|
c[k] := b[j]; |
|
|
|
||
j := j + 1; |
|
|
|
||
end; |
|
|
|
|
|
k := k + 1; |
|
|
|
||
end; |
|
|
|
|
|
// ДОзаполнение нового массива |
|
||||
if i < nA then { если не пуст массив A } |
|
||||
for j := i to nA do |
|
|
|
||
begin |
|
|
|
|
|
C[k] := A[j]; |
|
|
|
||
k := k + 1; |
|
|
|
||
end |
|
|
|
|
|
else { если не пуст массив B } |
|
||||
for i := j to nB do |
|
|
|
||
begin |
|
|
|
|
|
C[k] := B[i]; |
|
|
|
||
k := k + 1; |
|
|
|
||
end; |
|
|
|
|
|
PrintVec(A); |
|
|
|
||
PrintVec(B); |
|
|
|
||
PrintVec(C); |
|
|
|
||
end. |
|
|
|
|
|
|
|
|
|
|
|
Здесь PrintVec процедура печати массива произвольной длины.
10
Пример 12.21. Обозначим: ИР = индекс_для_рядов |
ИС = индекс_для_столбцов |
||
|
Шаблон доступа к 2d массиву A по рядам |
|
|
|
|
||
for ИР... do |
|
|
|
for ИС... do |
|
|
|
обработка элемента A[ИР, ИС] |
|
|
|
|
|
|
|
Шаблон доступа к 2d массиву A по столбцам
for ИС... do for ИР... do
обработка элемента A[ИР, ИС]
Пример 12.22. Различные способы инициализации 2D-массивов.
Ввод с клавиатуры
1 |
for |
i := 1 |
|
to |
NMax do |
2 |
for |
j := |
1 |
to |
MMax do |
3begin
4Write(’a[’, i, ’,’, j, ’] = ’);
5ReadLn(a[i,j])
6end;
Инициализация элементов массива по заданному закону for i := 1 to NMax do
for j := 1 to MMax do a[i,j] := 10 * i + j;
Инициализация массива при его описании
const Max = 3;
type Mas2 = array[1..Max-1, 1..Max] of Integer; var i, j : Integer;
A : Mas2 = ( (1, 3, 4),
(-5, 13, -4) );
Пример 12.23. Печать массива в виде таблицы.
Печать массива
1procedure PrintMas(NMax,MMax: Integer; const A0: Mas2);
2var i, j: Integer;
3begin
4 |
for i := 1 to NMax do |
5begin
6 for j := 1 to MMax do
7Write(a0[i,j]:3); { печать по столбцам }
8 |
WriteLn; |
{ переход на новую строку } |
9end;
10end;
11...
12 |
PrintMas(Max-1, Max, A); |
{ пример вызова } |