Типовые задачи на обработку двумерных массивов

К типовым задачам с двумерными массивами относятся задачи на вычисление суммы, произведения, количества, среднего арифметического, максимума, минимума элементов каждой строки или каждого столбца, заданной строки или заданного столбца и др.

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

For i:= a1 To b1
For j:= a2 To b2
......
Next j
Next i

Цикл, который содержит другой цикл называют внешним циклом, а цикл, содержащийся в теле другого цикла, называют внутренним. Все операторы внутреннего цикла должны полностью располагаться в теле внешнего цикла.

Всякий раз, когда внутренний цикл завершается, внешний цикл увеличивает значение своего счетчика на 1, и внутренний цикл выполняется вновь.

Поэтому, если за счетчик внешнего цикла взять индекс строки, а за счетчик внутреннего – номер столбца, то обработка двумерного массива будет идти по строкам, а если наоборот, то по столбцам.

Пример 1. Заполнить двухмерный массив размерностью n * m случайными целыми числами из диапазона [-40,40]. Определить:

- сумму элементов каждой строки;

- максимальные значения для каждого столбца;

- произведение элементов k -ой строки, значения которых лежат в диапазоне от 20 до 40.

Фрагмент программного кода:

Dim i As Integer,j As Integer,s As Integer

Dim max As Integer,k As Integer,p As Integer

Dim flag As Boolean

Dim a(1 To 30, 1 To 30) As Integer

'Очистка текстовых окон

Edit4.Text="": Edit5.Text="": Edit6.Text=""

'Вычисление сумм элементов в каждой строке

For i=1 To n 'Цикл по строкам

s=0;

For j=1 To m

s=s+a(i,j); 'Суммирование элементов i-ой строки

Next J

Edit4.Text= Edit4.Text+Str(s)+ " " 'Вывод суммы i-ой строки

Next i

'Вычисление максимальных элементов в каждом столбце

For j=1 To m 'Цикл по строкам

max=a(1,j) 'Установка начального максимума по первому элементу

'в j-ом столбце

For i=1 To n'Цикл по строкам

If a(i,j) > max Then max=a(i,j)

Next i

'Вывод максимального элемента j-го столбца

Edit5.Text= Edit5.Text+Str(max)+ " "

Next j

'Вычисление произведения элементов k-ой строки, попавших в диапазон [20,40]

k=Val(Edit3.Text) 'Ввод номера строки

p=1

flag=false 'Предполагаем, что нет элементов, попавших в диапазон [20,40]

For j=1 To m'Цикл по столбцам

If (a(k,j)>20) and (a(k,j)<40) Then 'Проверка условия попадания

'в диапазон [20,40]

p=p*a(k,j): flag=True

End if

Next j

'Если есть элементы из промежутка [20,40], то выводится их произведение, иначе

'выводится сообщение

If flag Then

Edit6.Text = Str(p)

Else

Edit6.Text = "Таких элементов нет"

End if

Преобразование двумерных массивов

Преобразование матриц заключается, как правило, в изменении порядка следования его элементов без изменения значений самих элементов.

Пример 2. Сформировать массив из n*m элементов. Получить новый массив, повернув исходный на: 180⁰ и 90⁰ по часовой стрелке и на 90⁰ против часовой стрелки.

Фрагменты кодов программы:

'Поворот на 180⁰ градусов

For i=1 To n 'Цикл по строкам

For j=1 To m 'Цикл по столбцам

b(i,j)=a(n-i+1,m-j+1)

Next j

Next i

 

'Поворот на 90⁰ градусов по часовой

For i=1 To n

For j=1 To m

b(i,j)=a(n-j+1,i)

Next j

Next i

 

'Поворот на 90⁰ градусов против часовой

For i=1 To n

For j=1 To m

b(i,j)=a(j,m-i+1)

Next j

Next i

Пример 3. Сформировать массив из n * m элементов. Зеркально отразить (повернуть) его относительно горизонтальной оси и вертикальной оси. Дополнительных массивов не создавать..

При повороте массива относительно горизонтальной оси внешний цикл по строкам организуется только до целой части от деления n на2(горизонтальной оси массива).

Фрагмент кода программы:

'Относительно горизонтальной оси

For i=1 To n \ 2 'Цикл по строкам

For j=1 To m 'Цикл по столбцам

tmp=a(i,j)

a(i,j)=a(n-i+1,j)

a(n-i+1,j)=tmp

Next j

Next i

При повороте массива относительно вертикальной оси внутренний цикл по столбцам организуется только до целой части от деления m на2 (вертикальной оси массива).

Фрагмент кода программы:

'Относительно вертикальной оси

For i=1 To n 'Цикл по строкам

For j=1 To m \ 2 'Цикл по столбцам

tmp=a(i,j)

a(i,j)=a(i,m-j+1)

a(n-i+1,j)=tmp

Next j

Next i

Пример 4. Сформировать массив из n * m элементов. Преобразовать его в одномерный массив.

Первый способ решения этой задачи состоит в том, что для формирования индекса очередного элемента одномерного массива задается независимый счетчик k.

Фрагмент кода программы:

'Использование независимого счетчика k для формирования одномерного массива

Dim a(1 To 30,1 To 30) As Single 'Описание статического двумерного

'массива, индексы элементов которого будут начинаться с 1

Dim b() As Single 'Описание динамического массива

Dim i As Integer,j As Integer,n As Integer,m As Integer

ReDim(n*m); 'Задание размера массива b, индексы элементов которого

'будут начинаться с 0!}

 

k=0 'Инициализация независимого счетчика

For i=1 To n Do 'Цикл по строкам

For j=1 To m Do 'Цикл по столбцам

Begin

b(k)=a(i,j)

k=k+1 'Значение счетчика увеличивается на 1

End;

Второй способ решения этой задачи состоит в том, что индекс очередного элемента одномерного массива вычисляется по формуле:

b (m * (i- 1 ) + j- 1) = a (i, j).

Фрагмент кода программы:

'Использование независимого счетчика k для формирования одномерного массива

Dim a(1 To 30,1 To 30) As Single 'Описание статического двумерного

'массива, индексы элементов которого будут начинаться с 1

Dim b() As Single 'Описание динамического массива

Dim i As Integer,j As Integer,n As Integer,m As Integer

ReDim(n*m); 'Задание размера массива b, индексы элементов которого

'будут начинаться с 0!

For i=1 To n Do 'Цикл по строкам

For j=1 To m Do 'Цикл по столбцам

b((i-1)*m +j-1)=a(i,j)

Типовые задачи с квадратными матрицами

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

Способ отбора нужных элементов для решения такого рода задач заключается в следующем:

Расположение элементов	Соотношение индексов (i – номер строки, j – номер столбца)
На главной диагонали	Одинаковые индексы (i = j)
Выше главной диагонали	Номер строки меньше номера столбца (i < j)
Ниже главной диагонали	Номер строки больше номера столбца (i > j)
На побочной диагонали	Номер столбца вычисляется по формуле: j = n - i + 1
Выше побочной диагонали	Номер строки меньшечем n - j + 1: (i < n - j + 1)
Ниже побочной диагонали	Номер строки большечем n - j + 1: (i > n - j + 1)

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

Пример 5. Двумерный массив n * n заполнен случайными целыми числами из диапазона [-40,40]. Определить:

- минимальное значение для элементов, расположенных на главной диагонали,

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

- произведение элементов, расположенных выше побочной диагонали; среднее арифметическое элементов, расположенных ниже главной диагонали.

Фрагмент программного кода:

min=a(1,1) 'Первый на главной диагонали

max=a(1,n) 'Первый на побочной диагонали

For i=1 To n 'Цикл по строкам

Begin

'Определение минимума на главной диагонали

If a(i,i) < min Then min= a(i,i)

'Определение максимума на побочной диагонали

If a(i,n-i+1) > max Then max=a(i, n-i+1)

Next i

'Нахождение произведения элементов расположенных выше побочной диагонали

p=1

For i=1 To n 'Цикл по строкам

For j=1 To n 'Цикл по столбцам

If i < n-j+1 Then p=p* a(i,j)

'Нахождение суммы и количества элементов ниже главной диагонали

s=0: kol=0

For i=1 To n 'Цикл по строкам

For j=1 To n 'Цикл по столбцам

If i > j Then s=s+ a[i,j]: kol=kol+1

'Среднее арифметическое элементов расположенных ниже главной диагонали

sr=s / kol

Пример 6. Сформировать массив из n * n элементов. Зеркально отразить (повернуть) его относительно главной и побочной диагоналей. Дополнительных массивов не создавать.

При решении задачи внешний и внутренний циклы организуются так, чтобы проход элементов осуществлялся только до нужной диагонали:

- до i при повороте относительно главной диагонали,

- до n - i при повороте относительно побочной диагонали.

В противном случае, смена произойдет дважды и все останется на своих местах.

Фрагменты кодов программы:

'Зеркальноe отражение массива относительно главной диагонали

For i=1 To n 'Цикл по строкам

For j=1 To i 'Цикл по столбцам

tmp=a(i,j)

a(i,j)=a(j,i)

a(j,i)=tmp

Next j

Next i

 

'Зеркальноe отражение массива относительно побочной диагонали

For i=1 To n-1 'Цикл по строкам

For j=1 To n-i 'Цикл по столбцам

tmp=a(i,j)

a(i,j)=a(n-j+1,n-i+1)

a(n-j+1,n-i+1)=tmp

Next j

Next i