Раз-04-Инф-210700 / УчеП-Раз-4-Инф-270100 / Тема-04-08

Тема 4.8. Программирование алгоритмов формирования и обработки двумерных массивов

Перейти к Теме 4.7 Теме 4.9 Огл.

4.8.1. Средства описания и работы с двумерными массивами данных 4.8.2. Базовые алгоритмы обработки двумерных массивов 4.8.3. Задачи для самостоятельного решения по теме «Программирование

алгоритмов формирования и обработки двумерных массивов» 4.8.4. Тестовые задания по теме «Программирование алгоритмов формирования и

обработки двумерных массивов»

4.8.1. Средства описания и работы с двумерными массивами данных

Из предыдущей темы известно, что массив – представляет собой последовательность переменных одинакового типа, объединенных общим именем.

Количество индексов (измерений) указывает на размерность (ранг) массива.

Например: двумерный массив b(3,2):
b(0,0)	b(0,1)	b(0,2)
b(1,0)	b(1,1)	b(1,2)
b(2,0)	b(2,1)	b(2,2)
b(3,0)	b(3,1)	b(3,2)

Так,	в приведенном выше	примере размерность массива b(3,2)– 2, т.е.	массив
двумерный	(имеет два измерения).	В нашем примере количество элементов	массива

b(3,2)равно 12 (4 строки и 3 столбца).

Перед использованием двумерного массива в программе, его необходимо объявить с помощью оператора Dim, который выделяет место в памяти для размещения элементов массива. Например,

Dim b(3,2)As Single или Dim b(0 To 3,0 To 2) As Single.

Прототипом такого массива является двумерная таблица – объект, широко используемый в математике. В линейной алгебре его называют матрицей. Особое место среди матриц занимают такие матрицы, у которых одинаковое число строк и столбцов.

Матрица прямоугольная A(n,m) - n≠m Матрица квадратная A(n,m) - n=m

0	j	m	0	j	m
0			0
i	A(i,j)		i
n			n

				Побочная диагональ Главная		диагональ
	Рис. 4.8.1-1
				матрицыi=n-j	матрицыi= j
		Таким образом, двумерные массивы можно представить			в виде	таблиц – матриц
	(прямоугольных или квадратных).					A(m,n), так и при
		Необходимо обратить		внимание на то, что, как при описании –

Тема 4.8. Программирование алгоритмов формированияи обработкидвум.массивовСтраница217

обращении – A(i,j)к элементам двумерного массива, в скобках сначала указывается номер

строки, а затем номер столбца.

Для определения параметров двумерного массива могут использоваться свойство класса Array – Rank и метод класса Array – GetLength( ).Свойство Rank используется для определения количества измерений (ранга) массива (для двумерного массива ранг равен 2). Причем каждое измерение в массиве может иметь свою длину. Метод GetLength()используется для определения количества элементов в заданном измерении массива (для первого измерения используется значение 0,для второго – 1 и т.д.). Необходимо обратить внимание, что метод GetLength( ) возвращает значение, которое на единицу больше, чем указанное в объявлении Dim, так как индексация элементов массива в VB всегда начинается с нуля, а метод GetLength( ) определяет количество элементов, считая от единицы.

Так, для определения параметров массива Mac1( ),описанного как

Dim Mac1(0 To 4, 0 To 7)As Integer

можно воспользоваться следующими выражениями:

ArrayRank = Mac1.Rank

RawCount = Mac1.GetLength(ArrayRank-2)

ColumnCount= Mac1.GetLength(ArrayRank-1),

где ArrayRank – ранг матрицы (равен 2);

RawCount – количество строк, т.е. количество элементов в нулевом измерении матрицы (равно 5);

ColumnCount – количество столбцов, т.е. количество элементов в первом измерении (равно 8).

Таким образом, ArrayRank, RawCount, ColumnCount являются переменными целочисленного типа, которые принимают значения 2, 5 и 8 соответственно.

Кроме того для определения параметров двумерного массива можно использовать метод GetUpperBound(),который находит верхнюю границу (максимальный индекс) заданного измерения. В качестве параметра этот метод принимает значения аналогично методу GetLength(), т.е. для первого измерения (строк) используется значение 0, для второго (столбцов) – значение 1.

Например, для массива Mac2

Dim Mac2(4,7) As Double

Dim Cтрока1, Столбец2 As Integer

…

Строка1 = Mac2.GetUpperBound(0)‘Значение переменной Строка1 равно 4 Столбец2 = Mac2.GetUpperBound(1)‘Значение переменной Столбец2 равно 7

Ввод, вывод и обработка двумерных массивов, как правило, основаны на использовании вложенных циклов, которые обеспечивают перебор всех элементов массива. В некоторых задачах может иметь значение порядок перебора элементов массива: «по строкам» или «по столбцам». Если внешний цикл будет организован по первому индексу (по строкам), а внутренний цикл по второму индексу (по столбцам), то выполняется построчный перебор элементов двумерного массива. Если внешний цикл в качестве параметра использует второй индекс, а внутренний цикл – первый индекс, то элементы массива перебираются по столбцам.

Тема 4.8. Программирование алгоритмов формированияи обработкидвум.массивовСтраница218

Пример 4.8.1-1. Написать процедуры ввода/вывода, которые могут использоваться в алгоритмах обработки двумерных массивов.

Некоторые процедуры ввода и вывода приведены в темах 4.3, 4.4, 4.5, 4.6 и 4.7. Остальные процедуры ввода и вывода, которые можно использовать при написании базовых алгоритмов формирования и обработки двумерных массивов, представлены на рис. 4.8.1-1, 4.8.1-2 и 4.8.1-3.

'Процедура ввода элементов двумерного массива типа Single

'с клавиатуры функцией InputBox( ) Sub vvodSngMac18(ByRef a(,)As Single)

Dim i, j, m, n As Integer m = a.GetLength(0) – 1

n = a.GetLength(1) - 1 Dim y As Single

Dim r1, r2 As String For i = 0 To m

For j = 0 To n

r1 = СStr(i) : r2 = СStr(j)

y = InputBox("эл-т массива a("+r1 +","+r2+")=", _

"Ввод эначений эл-тов массива a()") a(i,j) = CSng(Val(y))

Next j Next i

End Sub

Рис. 4.8.1-1

'Процедура форматированного вывода двумерного массива

' типа Single в ListBox

Sub vivodSngMac19(ByRef x(,) As Single, ByRef LB As ListBox)

Dim i, j, m, n As Integer

Dim z, z1 As String

m = x.GetLength(0) – 1 n = x.GetLength(1) - 1 LB.Items.Clear()

For i = 0 To m

z= ""

For j = 0 To n

z1 = Format(x(i,j), "0.000") If x(i,j) < 0 Then

Else

z1 = Space(2) + z1

End If z1 = Space(3) + z1

Nextzj= z + z1

LB.Items.Add(z)

Next i

End Sub

Рис. 4.8.1-2

'Процедура форматированного вывода двумерного массива

'типа Integer в TextBox

Sub vivodIntMac20(ByRef x(,) As Integer, ByRef TB As TextBox) Dim i, j, m, n As Integer

Dim z As String

m = x.GetLength(0) – 1 n = x.GetLength(1) - 1 TB.Text = ""

Тема 4.8. Программирование алгоритмов формированияи обработкидвум.массивовСтраница219

For i = 0 To m

For j = 0 To n

If Abs(x(i,j))>=100 Then

z = CStr (x(i,j)) & Space(2) ElseIf Abs(x(i,j)) >= 10 Then

Else

z = CStr (x(i,j)) & Space(4)

End If z = CStr (x(i,j)) & Space(6)

If x(I,j) >= 0 Then z = Space(1) + z

TB.Text = TB.Text & z

Next j

TB.Text = TB.Text & vbCrLf

Next i

End Sub

Рис. 4.8.1-3

На рис. 4.8.1-3 представлен пример процедуры вывода целочисленной матрицы в TextBox. Напомним, что для того, чтобы в элементе управления TextBox можно было записать несколько строк текста, необходимо присвоить его свойству MultiLine значение True. В тексте процедуры используется встроенная константа vbCrLf (см. тему 4.2.3).

4.8.2. Базовые алгоритмы обработки двумерных массивов

Для работы с массивами, как правило, используются алгоритмы регулярной циклической структуры. В примерах 4.8.2-1 – 4.8.2-5 приведены базовые алгоритмы обработки двумерных массивов.

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

Пример 4.8.2-1. Написать процедуру, которая формирует двумерный массив x, состоящий из 4 строк и 4 столбцов, по правилу: x(i,j) = 2*(i - 2) 2 - (j - 2) 2 и определяет максимальный элемент среди элементов, лежащих ниже главной диагонали, а также минимальный элемент – выше главной диагонали. Найденные максимальный и минимальный элементы поменять местами.

Общий алгоритм решения данной задачи представлен на рис. 4.8.2-1. Формирование значений элементов двумерного массива x по заданной формуле и их вывод в виде матрицы производится с помощью вложенных циклов. В переменных xmin и xmax в цикле фиксируются минимальный и максимальный элементы массива, в переменных imin, jmin и imax, jmax– их координаты (номер строки и номер столбца), вначале это 1- й элемент ниже диагонали и 1- й элемент выше диагонали.

Изменяя номера строки i с помощью внешнего цикла, отдельно просматриваются элементы, расположенные ниже (j от 0 до i-1) и выше (j от i+1 до 3) главной диагонали.

После просмотра всех элементов массива x в переменных imax	и	jmax	фиксируются
координаты максимального элемента, а в переменных imin	и	jmin–	координаты

минимального элемента.

Для краткости вывод матрицы здесь, а в дальнейшем и во всех последующих схемах алгоритма представлены, укрупнено – одним блоком.

Тема 4.8. Программирование алгоритмов формированияи обработкидвум.массивовСтраница220

Pr4821( )
i=0, 3
j=0, 3	Формирование
	двумерного
	массива
x(i,j)=2·(i-2)2-(j-2)2
imin=0, jmin=1
imax=1, jmax=0
xmin=x(0,1)
xmax=x(1,0)
i=0, 3

j=0,i-1

Определение

Нет

Да

x(i,j)>xmax

максимального

элемента, лежащего

xmax=x(i,j)

ниже главной

imax=i

диагонали

imax=j

j=i+1,3

Нет

Да

Определение

x(i,j)<xmin

минимального элемента,

лежащего выше

главной диагонали

xmin=x(i,j)

imin=i

jmin=j

x(imax, jmax)

Обмен максимального

↔и минимального

x(imin, jmin)

элементами

Вывод

x(0:3,0:3)

Конец

Рис. 4.8.2-1

В соответствии с концепцией VS .NET реальные программы должны состоять из множества отдельных процедур. Поэтому в алгоритме, приведенном на рис. 4.8.2-1, можно выделить несколько функциональных частей, описывающих определенные действия, каждую из которых можно реализовать своей процедурой: формирование двумерного массива, вывод двумерного массива, нахождение и обмен максимального и минимального элементов, вывод максимального и минимального элементов.

В этом случае программный код процедуры будет таким, как на рис. 4.8.2-2.

Тема 4.8. Программирование алгоритмов формированияи обработкидвум.массивовСтраница221

Sub Pr4822(ByRef x(,) As Single, _

ByRef xmin As Single, _ ByRef xmax As Single)

Dim i, j As Integer

Dim m As String, r As Single

Dim imin, jmin, imax, jmax As Integer ReDim x(3,3)

FormMac2(x) 'Формирование двумерного массива x( , )

vivodSngMac19(x,ListBox1)'Вывод сформированного массива

MaxH(x,xmax, imax, jmax)'Нахождение max эл. и его индексов, vivodSng3(xmax, TextBox1) 'лежащих ниже главной диагонали, и vivodInt4(imax, TextBox2) 'их вывод в элементы TextBox vivodInt4(jmax, TextBox3)

MinB(x, xmin, imin, jmin)'Нахождение min эл. и его индексов, vivodSng3(xmin, TextBox4)'лежащих выше главной диагонали, и vivodInt4(imin, TextBox5)'их вывод в элементы TextBox vivodInt4(jmin, TextBox6)

Ob(x, imax, jmax, imin, jmin) 'Обмен max и min элементов vivodSngMac19(x, ListBox2)'Вывод преобразованного массива

End Sub

'Формирование двумерного массива x(,)

Sub FormMac2(ByRef				x( , ) As Single)
Dim i, j, m			As Integer
m = x.GetLength(0) – 1
For	i =	0	To	m
	For	j =	0	To m
	Next	x(i,j) = 2*(i – 2) ^2 - (j - 2)^2
Next		j
	i
End Sub

'Нахождение max эл.				и его индексов, лежащих ниже главной диагонали
Sub MaxH(ByRef x(,)				As Single, _
ByRef xmax				As Single, _
ByRef imax				As Integer, _
ByRef jmax As Integer)
Dim i, j, m		As Integer
m = x.GetLength(0) – 1					xmax = x(1,0)
imax = 1	:	jmax = 0 :
For i = 0		To	m	i - 1
For	j = 0		To		Then
If	x(i,j) > xmax
	xmax = x(i,j ): imax = i : jmax = j
End If
Next	j
Next i
End Sub

'Нахождение min эл.	и его индексов, лежащих выше главной диагонали
Sub MinB(ByRef x(,)	As Single, _
ByRef xmin	As Single, _
ByRef imin	As Integer, ByRef jmin As Integer)

Dim i, j, m As Integer

Тема 4.8. Программирование алгоритмов формированияи обработкидвум.массивовСтраница222

m = x.GetLength(0) – 1
imin = 0	:	jmin = 1	: xmin = x(0,1)
For i =	0	To m	m
For	j = i + 1 To
If	x(i,j) < xmin		Then
	xmin = x(i,j )
	imin = i
	jmin = j
End If
Next	j
Next i
End Sub
'Обмен max и min элементов
Sub Ob(ByRef x(,) As Single _
ByVal imax As Integer, ByVal jmax As Integer _
ByVal imin As Integer, ByVal jmin As Integer)
Dim r As Single
r = x(imax,jmax)
x(imax,jmax)=x(imin,jmin)
x(imin,jmin) = r
End Sub
Рис. 4.8.2-2

Процедура Pr4822( )может быть вызвана из любой другой процедуры или из модуля формы, например, следующим образом:

Dim xx( , ) As	Single
Dim xm1, xm2 As	Single
…
Pr4823(xx, xm1, xm2)
Рис. 4.8.2-3

На рис 4.8.2-3 двумерный массив xxи переменные xm1, xm2– фактические параметры, а на рис. 4.8.2-2двумерный массив x и переменные xmin, xmax – формальные параметры.

Обратите внимание, что при постановке задачи входной массив определен как массив, состоящий из 4строк и 4 столбцов – x(3,3) . Поэтому при написании программы, где это необходимо, была использована константа 3.

Однако, реальные процедуры должны быть универсальными, то есть в нашем случае должны обрабатывать двумерные массивы произвольного размера – x(n,n).

Это можно реализовать или с помощью передачи в процедуру параметра n, или воспользоваться методами класса Array (GetLength( )или GetLepperBound( )).

Пример 4.8.2-2.Написать процедуру, которая заполняет элементы массива f(5x2) целыми числами таким образом, чтобы получилась следующая таблица:

1	2	3
4	5	6
7	8	9
10	11	12
13	14	15
16	17	18,

а затем осуществить перестановку элементов первого и последнего столбцов.

Тема 4.8. Программирование алгоритмов формированияи обработкидвум.массивовСтраница223

Алгоритм и код программы данной задачи приведены на рис. 4.8.2-4.

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

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

f(i,0) и f(i,2). После этого массив выводится на экран в следующем виде:
3	2	1
6	5	4
9	8	7
12	11	10
15	14	13
18	17	16.

Pr4824( )

Ввод

f( , )

Вычисление

RawCount,

ColCount

i=0,RawCount-1

j=0,ColCount-1

Вывод

f(i,j)

i=0,RawCount-1

f(i,0)↔f(i,2)

Вывод

f( , )

Sub Pr4824( )

Dim i, j, r As Integer

Dim f(,) As Integer={{1,2,3}, {4,5,6}, _ {7,8,9}, {10,11,12}, _ {13,14,15}, {16,17,18}}

Dim c1, c2 As Integer

c1=0 : c2=2'номера столбцов vivodIntMac20(f, TextBox1)'Вывод исход. мас.

ПерСтол(f, c1, c2)'Перест.1-го и 2-го столб. vivodIntMac20(f, TextBox2)'Вывод преобр.масс.

End Sub

'Процедура перестановки столбцов

Sub ПерСтол(ByRef f(,)As Integer, _ ByVal cc1 As Integer, ByVal cc2 As Integer)

Dim ArrayRank, RawCount, i, r As Integer ArrayRank = f.Rank

RawCount= f.GetLength(ArrayRank - 2) For i = 0 To RawCount - 1

r= f(i,cc1) : f(i,сс1)=f(i,cc2) f(i,cc2)= r

Next i End Sub

End Sub

Рис. 4.8.2-4

В приведенном примере для определения параметров массива используются методы класса Array: Rank и GetLength( ).

Пример 4.8.2-3.Написать процедуру, которая формирует одномерный массив, каждый элемент которого представляет собой количество положительных элементов соответствующего столбца двумерного массива b(15,25).

Предполагается, что выделение памяти и ввод массива b(15,25)осуществляется в другой процедуре, которая вызывает процедуру Pr4823( ).

Тема 4.8. Программирование алгоритмов формированияи обработкидвум.массивовСтраница224

Алгоритм и код программы представлены на рис. 4.8.2-5.

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

b( , )

Sub

Pr4825(ByRef

b(,) As Single, _

Pr4925

ByRef

a( ) As Integer)

a( )

Dim

Вычисление

Rank, RC, CC, j, i, n As

Integer

RC

Rank = b.Rank

CC

RC = b.GetLength(Rank - 2) - 1

CC = b.GetLength(Rank - 1) - 1

j=0, CC

ReDim a(CC)

Dim

m

As String

n=0

For

j = 0

To

CC

n = 0

i = 0

TO

RC

For

If

Then n=n+1

i=0,RC

i

b(i,j) > 0

Next

Нет

b(i,j)>0

Да

Next

a(j)= n

j

n=n+1

'vivodInt16(a, ListBox1)

End Sub

a(j)=n

End Sub

Рис. 4.8.2-5

Пример 4.8.2-4.Написать процедуру, которая из матрицы х(n,m), являющейся входным параметром, получает и выводит на экран транспонированную к ней матрицу y(m, n).

Алгоритм и программа решения данной задачи приведены на рис. 4.8.2-6.

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

Тема 4.8. Программирование алгоритмов формированияи обработкидвум.массивовСтраница225

Pr4926( )	X( , )	Sub Pr4926(ByRef				x(,) As Single, _
	Y( , )			ByRef		y(,) As Single )
Вычисление		Dim ArrayRank, n, m, j, i As						Integer
n, m		ArrayRank = x.Rank
		n = x.GetLength(ArrayRank - 2) - 1
i=0, n		m = x.GetLength(ArrayRank - 1) - 1
		ReDim y(m,n)			To	n
		For	i = 0
j=0 ,m		For		j = 0		To	m
			y(j,i) = x(i,j)
		Next		j
y(j,i)=x(i,j)		Next	i
		vivodSngMac19(y,ListBox2)
		End Sub
Вывод
y(m,n)
End Sub

Рис. 4.8.2-6

Пример 4.8.2-5.Написать процедуру, которая вычисляет и выводит на экран алгебраическое произведение р матрицы х порядка 15х20 на матрицу y порядка

20х10.

Алгоритм и программа решения данной задачи представлены на рис. 4.8.2-7. Произведением p матрицы x порядка m х n на матрицу y порядка n х k называется

матрица порядка m х k , в которой элемент, стоящий на пересечении i-й строки и j-ого столбца, равен произведению i-го вектора-строки матрицы x на j-й вектор-столбец матрицы y.

Произведением вектора-строки a на вектор-столбец b с одинаковым числом элементов

n называется сумма произведений соответствующих элементов этих векторов ∑n ai bi .

i=0

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

pij = ∑n xit ytj, гдеi = 0,m; j = 0,k.

t=0

Из определения следует, что в нашем случае матрица p будет иметь порядок 15х10. Для формирования такой матрицы необходимо организовать вложенные циклы: внешний цикл, изменяющий номер строки от 0 до m, и внутренний цикл, изменяющий номер столбца от 0 до k. Для вычисления произведения текущей строки матрицы x на текущий столбец матрицы y, в теле внутреннего цикла требуется организовать еще один цикл, параметр которого меняется от 0 до n.

Тема 4.8. Программирование алгоритмов формированияи обработкидвум.массивовСтраница226