Лабораторная работа №4. Программирование с использованием массивов

 

Цель работы: научиться правильно описывать различные массивы, уметь инициализировать массивы, распечатывать содержимое массива; научится решать задачи на использование массивов.

Общие сведения:

Массив - это структурированный тип данных, который используется для описания упорядоченной совокупности фиксированного числа элементов одного типа, имеющих общее имя. Для обозначения элементов массива используются имя переменной-массива и индекс.

Массивы

Массив - упорядоченные данные одного типа. Возможно создание массива, вклю-чающего массив другого типа. Массивом часто обозначают характеристики обьектов одного типа, имеющих одинаковые единицы измерения. Массив состоит из элементов, имеющих порядковые номера, т. е. элементы массива упорядоченны. Таким образом, если обьекты одного типа обозначить именем, например "A", то элементы обьекта будут A[1], A[2] и т. д. В квадратных скобках указан номер элемента. Порядковый номер элемента массива, обычно не несет никакой информации о значении элемента, а показывает расположение элемента среди других. К элементам массива можно обращаться только по их номеру (индексу). Значения элементам массива присваиваются также как и другим переменным с учетом типа массива. Если элементы массива имеют один индекс, то массив называется одномерным или линейным, либо массив - вектор. Значения элементов одномерного массива обычно выводят на экран или бумагу в виде столбца или строки. В некоторых случаях удобно элементы массива пронумеровывать двуми независимыми индексами, такие массивы называются двумерными или матрицами. Значения элементов двумерного массива обычно выводят на экран в виде таблицы. Если элементы массива имеют три независимых индекса, то массив называется трехмерным. Значения элементов трехмерного массива обычно выводят на экран в виде набора таблиц.

Линейные массивы

Линейным массивом можно обозначить, например, оценки учеников класса. Каждая оценка является значением элемента массива оценок "A" и имеет порядковый номер (индекс). В Турбо-Паскале значение индекса указывается в квадратных скобках после имени массива. Можно создать массив фамилий "S" учеников класса. Значением элемента массива будет фамилия ученика, а индексом - порядковый номер по списку. Пусть дан список фамилий учеников и их оценки:

№	Фамилии	Оценки
	Иванов
	Петров
	Сидоров
	Титов
...	...	...
	Якупов

Описание массивов:

Var A: array[1..30] of byte; S: array[1..30] of string; {или} SO: array[1..30] of string[12];

Присвоение значений элементам массива:

"A" - A[1]:= 5; A[2]:= 4; и т. д. "S " - S[1]:= 'Иванов'; S[2]:= 'Петров'; и т. д.

Приведем таблицу обозначений и соответствия элементам массива, их значений и индексов:

Номер элемента индекса
Элементы массива "S"	S[ 1 ]	S[ 2 ]	S[ 3 ]	S[ 4 ]	S[ i ]	S[ 30 ]
Значения элементов	Иванов	Петров	Сидоров	Титов	...	Якупов
Элементы массива "A"	A[ 1 ]	A[ 2 ]	A[ 3 ]	A[ 4 ]	A[ i ]	A[ 30 ]
Значения элементов					...

 

Если известна зависимость, по которой изменяются значения элементов массива, то присвоение значений удобно проводить в операторах цикла c параметром или с условием. Например, присвоим значения элементам массива "y" по зависимости: y=sin(x), где x= Pi * i/180, 0<= i <=180.

For i:= 0 to 180 Do y[i]:= sin(Pi * i/180);

Присвоим случайные значения в диапазоне от -30 до +40 ста элементам массива "R":

Randomize; for i:= 1 to 100 Do R[i]:= - 30 + Random(71);

Присвоим значения семи элементам массива "A" оператором Readln:

For i:= 1 to 7 Do begin Write('Введите A[',i,']= '); Readln(A[i]); end;

При выводе массива на экран удобно размещать данные в виде таблицы - в несколько колонок. Для вывода обозначений переменных ("шапки таблицы") можно использовать операторы вывода символов в цикле, например:

For j:=1 to 66 do Write('-'); Writeln; For j:=1 to 3 do Write('| Фамилия | оценка |'); Writeln; For j:=1 to 66 do Write('-'); Writeln;

- шапка для вывода в три пары колонок значений переменных "S" и "A". Шапка занимает 66 позиций (по ширине экрана в текстовом режиме размещается 79 символов и пробел). Оператор Writeln; переводит курсор на новую строчку.

Вывод значений ста элементов массивов "S" и "A" в три пары колонок, произведем операторами:

For i:= 1 to 100 do begin Write('|', s[i]:11,'|', a[i]:8, '|'); if (i mod 3) = 0 Then Writeln; if (i mod 60) = 0 then Readln; end;

В этом случае данные таблицы полностью не умещаются на экране и можно задержать прокрутку экрана при выводе данных, применяя оператор Readln после вывода, например, 20 строк.

В цикле удобно определять сумму элементов массива, наибольший (наименьший) элемент и создавать новые массивы, удовлетворяющие некоторому условию, например:

s:= 0; for i:= 1 to 100 do s:= s + a[i]; { s - сумма элементов массива} a_max:= a[1]; for i:= 1 to 100 do { поиск наибольшего элемента a[j] } if a[i] > a_max then begin a_max:= a[i]; j:= i; end; j:= 0; k:= 0; for i:=1 to 100 do {создание новых массивов с элементами: b[j]>=0, c[k]<0} if a[i] >= 0 then begin j:= j+1; b[j]:= a[i]; end else begin k:= k+1; c[k]:= a[i] end; j:= 0; k:= 8; for i:= 1 to 100 do {создание массива номеров "M" для элементов: a[i] > a[k]} if a[i] > a[k] then begin j:= j+1; M[j]:= i; end;

Двумерные массивы

Массивы, рассмотренные выше, имеют элементы, упорядоченные по одному индексу и называются одномерными массивами или векторами. Массив может быть двумерным, трехмерным и т. д. Двумерные массивы имеют элементы, упорядоченные по двум индексам и часто называются матрицами. В Турбо-Паскале при описании многомерного массива диа-пазоны изменения индексов перечисляются через запятые, например:

Var A: array[1..30, 1..7] of byte;

Рассмотрим пример работы с двумерными массивами. Обозначим массивом оценки учеников класса по нескольким предметам. Каждая оценка является значением элемента массива оценок "A" и имеет порядковый номер (два индекса). Поставим в соответствие первому индексу номер фамилии в списке учеников, а второму - номер предмета, по которому получена оценка. Тогда двумерный массив оценок можно представить в виде таблицы: каждый элемент a[i, j] находится на пересечении I-ой строки и J-го столбца.
Исходные данные могут быть представлены в виде таблицы оценок:
Годовые оценки по предметам:

№	Фамилия	Физика	Химия	Алгебра	Геометрия	История	Биология
	Иванов
	Петров
	Сидоров
...	...	...	...	...	...	...	...
	Якупов

 

Можно создать одномерные массивы фамилий "S" учеников класса и наименований предметов "P". Значением элемента массива "Р" будет наименование предмета, а индексом - порядковый номер предмета, например: 1 - физика, 2 - химия, 3 - алгебра, 4 - геометрия, 5 - история, 6 - биология.

Приведенная выше таблица может быть представлена в виде набора элементов (число строк = N, число столбцов = M):

Номер строки "I"	Номер столбца "J"					...	J	...	M
Массив "S"	Массив "P"	P[1]	P[2]	P[3]	P[4]	...	P[J]	...	P[M]
	S[1]	Массив "A"	a[1, 1]	a[1, 2]	a[1, 3]	a[1, 4]	...	a[1, j]	...	a[n, m]
	S[2]	a[2, 1]	a[2, 2]	a[2, 3]	a[2, 4]	...	a[2, j]	...	a[2, m]
	S[3]	a[3, 1]	a[3, 2]	a[3, 3]	a[3, 4]	...	a[3, j]	...	a[3, m]
	S[4]	a[4, 1]	a[4, 2]	a[4, 3]	a[4, 4]	...	a[4, j]	...	a[4, m]
...	...	...	...	...	...	...	...	...	...
I	S[I]	a[i, 1]	a[i, 2]	a [i, 3]	a [i, 4]	...	a[i, j]	...	a[i, m]
...	...	...	...	...	...	...	...	...	...
N	S[N]	a[n, 1]	a[n, 2]	a[n, 3]	a[n, 4]	...	a[n, j ]	...	a[n, m]

 

Массив оценок можно задать с использованием функции Random, например:

for i:= 1 to N do for j:= 1 to M do A[i, j]:= random(4) + 2;

Для вывода наименований предметов ("шапка" таблицы) можно использовать операторы:

Writeln; Write('Фамилия\\Предметы:|'); For i:= 1 to M do write(P[i]:9,' |');

Для вывода элементов массива "A" на экран удобно использовать вложенный цикл:

for i:= 1 to N do begin writeln; write(S[i]:19, ' |'; for j:= 1 to M do write(A[i,j]:7, ' |') end;

Для расчета массива "SS" - сумм "M" элементов в каждой из "N" строк массива "A" (NxM) можно применить операторы:

for i:= 1 to N do begin SS[i]:= 0; for j:= 1 to M do SS[i]:= SS[i] + A[i,j]; end;

Здесь для каждого индекса "i" от 1 до N происходит суммирование элементов A[i, j] по индексу "j" от 1 до M.

При модификации массива "A" изменяется расположение данных в исходном массиве, например, в случае вставки данных из линейного массива "B" в колонку с номером "M1" необходимо сдвинуть данные в колонках J >= M1 используя операторы:

for i:= 1 to N do begin for j:=M+1 downto M1+1 do A[i,j]:=A[i,j-1]; A[i,M1]:=B[i]; end;

Если порядковый номер предмета изменится, то необходимо изменить расположение оценок в массиве "A", например, перестановку колонок с оценками по физике и химии можно сделать операторами:

for j:= 1 to N do begin a1:=A[1,j]; A[1,j]:=A[2,j]; A[2,j]:=a1; end;

Примечание: при модификации массива "A" не забудьте соответственно изменять расположение данных в сопутствующих массивах, например, "P" или "S".

При создании новых массивов согласно некоторым условиям выбираются данные из элементов исходного массива. Например, для создания массива "В" из четных столбцов массива "A" можно использовать операторы:

for j:= 1 to M do If (j Mod 2) = 0 then for i:= 1 to N do B[i,j Div 2]:= A[i,j];

Для создания массива "В", состоящего из строк массива "A", удовлетворяющих условию A[i, 1] > C, где C - заданное число, можно использовать операторы:

k:= 0; for i:= 1 to N do If A[i,1] > C then begin k:= k + 1; for j:= 1 to M do B[k,j]:= A[i,j]; end;

Для сравнения значений элементов массива удобно строить столбиковые диаграммы (гистограммы). Например, для вывода "N" значений положительных элементов массива "SS" в виде горизонтальной гистограммы можно использовать операторы:

k:= 30/S_max; { k - нормирующий масштабный коэффициент } { S_max - наибольший элемент массива "SS" } for i:=1 to N do begin writeln; { переход к новому столбику } yg:= round(k*SS[i]); { yg - длина столбика гистограммы } for j:=1 to yg do write(#220); { вывод символа '_' с кодом 220 } end;

Добавив операторы вывода порядкового номера и значений SS[i] получаем гистограмму в виде:

 

Примеры:

Пример1: Дан двумерный массив. В каждой строке все его элементы, не равные нулю, переписать (сохраняя порядок) в начало строки, а нулевые элементы - в конец массива. Новый массив не заводить.

Этапы решения задачи:
1. Суть одного из алгоритмов решения данной задачи состоит в том чтобы "просматривать" массив построчно и находить в каждой строке пару (0:число), а затем менять их местами между собой и так до тех пор пока в строке таких пар не окажется.
2. Напишем программу на псевдо паскале:

program example1; var V:array[1..100,1..100] of integer; m,n, i,j, c: integer; flag: boolean; begin <ввод размерности массива m*n> <заполнение ячеек массива> for i:=1 to m do repeat flag:= true; for j:=1 to n-1 do if (v[i,j]=0) and (v[i,j+1]<>0) then begin <поменять их местами> flag:= false; end; until flag; <Печать массива> readln; end.

 

3.Составим блок схему алгоритма

Детализируем блок "Упорядочиваем 1-ю строку"

Блок схема алгоритма целиком:

4.Приведем программу на языке Паскаль:

program example1; var V:array[1..100,1..100] of integer; m,n, i,j, c: integer; flag: boolean; begin write('Введите размерность массива m-n> '); readln(m,n); for i:= 1 to m do for j:= 1 to n do begin write('V[',i,',',j,']= '); readln(V[i,j]); end; for i:=1 to m do repeat flag:= true; for j:=1 to n-1 do if (v[i,j]=0) and (v[i,j+1]<>0) then begin c:=v[i,j]; v[i,j]:=v[i,j+1]; v[i,j+1]:=c; flag:= false; end; until flag; for i:= 1 to m do begin for j:= 1 to n do write(V[i,j]:2); writeln end; readln; end.

 

Контрольные вопросы

1. Каким образом определяются переменные типа массив (одномерный и двумерный)?

2. Как осуществляется доступ к отдельному элементу одномерного и двумерного массива?

3. Каким образом выводятся элементы массива на экран?

4. Приведите пример фрагмента программы, который выводит на экран двумерный массив в виде матрицы.

5. Сколько чисел можно записать в шестимерный массив X: Array[0..1, 0..1, 0..1, 0..1, 0..1, 0..1] of Integer?

Задания

1. Дан массив размера N. Вывести его элементы в обратном порядке.

2. Дан массив размера N. Вывести вначале его элементы с четными индексами, а затем - с нечетными.

3. Дан целочисленный массив A размера 10. Вывести номер первого и последнего из тех его элементов A[i], которые удовлетворяют двойному неравенству: A[1] < A[i] < A[10]. Если таких элементов нет, то вывести 0.

4. Дан целочисленный массив размера N. Преобразовать его, прибавив к четным числам первый элемент. Первый и последний элементы массива не изменять.

5. Дан целочисленный массив размера N. Вывести вначале все его четные элементы, а затем - нечетные.

6. Поменять местами минимальный и максимальный элементы массива размера 10.

7. Заменить все отрицательные элементы целочисленного массива размера 10 на минимальное значение элементов массива.

8. Дан массив размера N. Осуществить сдвиг элементов массива вправо на одну позицию.

9. Дан массив размера N и число k (0 < k < 5, k < N). Осуществить циклический сдвиг элементов массива влево на k позиций.

10. Проверить, образуют ли элементы целочисленного массива размера N арифметическую прогрессию. Если да, то вывести разность прогрессии, если нет - вывести 0.

11. Дан массив ненулевых целых чисел размера N. Проверить, чередуются ли в нем положительные и отрицательные числа. Если чередуются, то вывести 0, если нет, то вывести номер первого элемента, нарушающего закономерность.

12. Дан массив размера N. Определить количество участков, на которых его элементы монотонно возрастают.

13. Дан массив размера N. Определить количество его промежутков монотонности (то есть участков, на которых его элементы возрастают или убывают).

14. Дан целочисленный массив размера N. Определить максимальное количество его одинаковых элементов.

15. Дан целочисленный массив размера N. Если он является перестановкой, то есть содержит все числа от 1 до N, то вывести 0, в противном случае вывести номер первого недопустимого элемента.

16. Дан целочисленный массив размера N. Назовем серией группу подряд идущих одинаковых элементов, а длиной серии - количество этих элементов (длина серии может быть равна 1). Вывести массив, содержащий длины всех серий исходного массива.

17. Дано число k (0 < k < 11) и матрица размера 4 x 10. Найти сумму и произведение элементов k-го столбца данной матрицы.

18. Дана матрица размера а x б. Найти суммы элементов всех ее четных строк и нечетных столбцов.

19. Дана матрица размера а x б. Найти минимальное значение в каждой строке.

20. Дана матрица размера а x б. В каждой строке найти количество элементов, больших среднего арифметического всех элементов этой строки.

21. Дана матрица размера а x б. Преобразовать матрицу, поменяв местами минимальный и максимальный элемент в каждой а) строке б) столбце.

22. Дана целочисленная матрица размера а x б. Вывести номер ее первой строки, содержащего равное количество положительных и отрицательных элементов (нулевые элементы не учитываются). Если таких строк нет, то вывести 0.

23. Дана целочисленная матрица размера M x N. Найти количество ее строк и столбцов, все элементы которых различны.

24. Дана квадратная матрица порядка M. Найти сумму элементов ее главной и побочной диагонали.

25. Дана квадратная матрица порядка M. Заменить нулями элементы матрицы, лежащие а) ниже главной диагонали, б) выше главной диагонали, в) нижепобочной диагонали.

26. Дана квадратная матрица порядка M. Повернуть ее на 90,180,270 градусов в положительном направлении.

27. Даны два числа k1 и k2 и матрица размера а x б. Поменять местами столбцы матрицы с номерами k1 и k2.

28. Дано число k и матрица размера а x б. Удалить столбец матрицы с номером k.

29. Даны целые числа а1, а2, а3. Получить целочисленную матрицу [bij]i,j=1,2,3, для которой bij=ai-3aj.

30. Получить [aij]i=1,…10; j=1,…12 - целочисленную матрицу, для которой aij=i+2j.

31. Дано натуральное число n. Получить действительную матрицу [aij]i, j=1,…n, для которой aij= .

32. Дана действительная квадратная матрица порядка n. Найти наибольшее из значений элементов, расположенных в заштрихованной части матрицы.

а) б) в) г)

33. Дана квадратная вещественная матрица размерности n. Найти количество нулевых элементов, стоящих: выше главной диагонали; ниже главной диагонали; выше и ниже побочной.

34. Дана вещественная матрица размерности n * m. По матрице получить логический вектор, присвоив его k-ому элементу значение True, если выполнено указанное условие и значение False иначе: - все элементы k столбца нулевые; - элементы k строки матрицы упорядочены по убыванию; - k строка массива симметрична.

35. Дана вещественная матрица размерности n * m. Сформировать вектор b, в котором элементы вычисляются как: - произведение элементов соответствующих строк; - среднее арифметическое соответствующих столбцов; - разность наибольших и наименьших элементов соответствующих строк; - значения первых отрицательных элементов в столбце.

36. Дан двухмерный массив A[1..m,1..n]. Написать программу построения одномерного массива B[1..m], элементы которого соответственно равны а) суммам элементов строк, б) произведениям элементов строк, в) наименьшим средних арифметических элементов строк.

37. Расположить элементы данного массива в обратном порядке (первый элемент меняется с последним, второй - с предпоследним и т.д. до середины; если массив содержит нечетное количество элементов, то средний остается без изменения).

38. В данном массиве поменять местами элементы, стоящие на нечетных местах, с элементами, стоящими на четных местах.

Задачи повышенной сложности

1. В массиве А[1..N,1..N] определить номера строки и столбца какой-нибудь седловой точки. Некоторый элемент массива называется седловой точкой, если он является одновременно наименьшим в своей строке и наибольшим в своем столбце.

2. Массив А[1..5,1..7] содержит вещественные числа. Требуется ввести целое число K и вычислить сумму элементов А[I,J], для которых I+J=К. Прежде, однако следует убедиться, что значение К позволяет найти решение, в противном случае нужно напечатать сообщение об ошибке.

3. Дан массив A[1..N,1..N]. Составить программу, которая прибавила бы каждому элементу данной строки элемент, принадлежащий этой строке и главной диагонали.

4. Дана матрица NxM. Переставляя ее строки и столбцы, переместить наибольший элемент в верхний левый угол. Определить можно ли таким же образом поместить минимальный элемент в нижний правый угол.

5. Заполнить двухмерный массив Т[1..n,1..n] последовательными целыми числами от 1 до n 52 0, расположенными по спирали, начиная с левого верхнего угла и продвигаясь по часовой стрелке:

1 2 3 4 5 6 20 21 22 23 24 7 19 32 33 34 25 8 18 31 36 35 26 9 30 29 28 27 10 15 14 13 12 11

 

6. Элемент двухмерного массива называется локальным минимумом, если он строго меньше всех имеющихся у него соседей. Подсчитать количество локальных минимумов заданной матрицы размером NxN найти максимум среди всех локальных минимумов.