Info1415_L_Matrix

12 Массивы

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);

{ пример вызова }