Лекция6(2) Типовые алгоритмы
.pdfТиповые алгоритмы обработки двумерных массивов
Двумерные массивы
•Двумерный массив – это таблица, содержащая информацию и состоящая из нескольких строк и столбцов. В математике аналогом является матрица.
•Каждый элемент двумерного массива имеет тоже имя, что и весь массив и отличается от другого элемента номером строки и номером столбца, на пересечении которых он находится.
•Номер строки и номер столбца называются индексами.
•Индексы в двумерном массиве записываются в скобках через запятую. На первом месте стоит индекс строки, на втором месте – индекс столбца.
•Например, В(I,J) –элемент двумерного массива с именем В, стоящий на пересечении I строки и J столбца.
Лекция 6 Информатика, часть 2 |
32 |
Ввод и вывод элементов двумерных массивов
Ввод элементов двумерного мссива X(N,M),
I=1,2,…,N, J=1,2,…,M
Шаг изменения I и J равен 1. Пусть N=2, M=3.
При I=1, изменения J=1,2,…,3 вводятся элементы массива Х(1,1), Х(1,2), Х(1,3)
При I=2, изменения J=1,2,…,3 вводятся элементы массива X(2,1), X(2,2), X(2,3)
N,M
I=1,N,1
J=1,M,1 |
Х(I,J) |
АНАЛОГИЧНО
Вывод элементов двумерного массива У(N,M), I=1,…,N, J=1,2,…,M
Шаг изменения I и J равен 1.
При N= 3 и M=2 элементы массива Y(1,1), Y(1,2), Y(2,1), Y(2,2), Y(3,1),У(3,2)
I=1,N
I=1,N
Y(I,J)
Лекция 6 Информатика, часть 2 |
33 |
Алгоритм вычисления среднего значения элементов массива по строкам
Вычислить средние значения элементов
массива А(N,М) по строкам. Входные данные: N,M, A(N,M).
Выходные данные: S(N) – сумма элементов массива по строкам, SR(N) – средние значения по строкам.
Вспомогательные данные: I,J Математическая постановка задачи
S(I ) = åM A(I, J ) |
SR(I ) = |
S(I) |
|
|
M |
||||
j= 1 |
|
|||
Задание начального значения суммы S(I)=0. Формула в цикле(сумма) S(I)=S(I)+А(I,J). Среднее SR(I)=S(I)/M
I=1,N,1
S(I)=0
А(1,1) А(1,2) А(1,3) S(1) SR(1) А(2,1) А(2,2) A(2,3) S(2) SR(2) А(3,1) А(3,2) А(3,3) S(3) SR(3) А(4,1) А(4,2) A(4,3) S(4) SR(4)
J=1,M,1
S(I)=S(I)+A(I,J) 
SR(I)=S(I)/M
Лекция 6 Информатика, часть 2 |
34 |
Алгоритм вычисления среднего значения элементов массива по столбцам
Вычислить средние значения элементов
массива А(N,М) по столбцам. Входные данные: N,M, A(N,M).
Выходные данные: S(M) – сумма элементов массива по строкам, SR(M) – средние значения по строкам.
Вспомогательные данные: I,J Математическая постановка задачи
S(J ) = å A(I, J ) |
SR(J ) = S(J ) |
||
N |
|
|
|
|
|
|
|
i= 1 |
|
N |
|
Задание начального значения суммы S(J)=0. Формула в цикле(сумма) S(J)=S(J)+А(I,J). Среднее SR(J)=S(J)/M
J=1,M,1
S(J)=0
А(1,1) А(1,2) А(1,3) А(2,1) А(2,2) A(2,3) А(3,1) А(3,2) А(3,3) А(4,1) А(4,2) A(4,3) S(1) S(2) S(3)
SR(1) SR(2) SR(3)
I=1,N,1 |
|
S(J)=S(J)+A(I,J) |
SR(J)=S(J)/N |
Лекция 6 Информатика, часть 2 |
35 |
Алгоритм транспонирования матрицы
Транспонирование матрицы . Замена |
Формула в цикле |
строк матрицы А(N,М) её столбцами, а |
|
столбцов – строками. |
B(J,I)=А(I,J) |
Транспонированная матрица |
|
В(M,N) = A(N,M) |
J=1,M,1 |
Входные данные: N,M, A(N,M). |
|
Выходные данные: B(M,N) – |
I=1,N,1 |
Вспомогательные данные: I,J |
|
Математическая постановка задачи |
B(J,I)=A(I,J) |
|
|
B(J, I) = A(I, J) |
|
А(1,1) |
А(1,2) |
А(1,3) |
|
B(1,1) |
B(1,2) |
А(2,1) |
А(2,2) |
A(2,3) |
|
B(2,1) |
B(2,2) |
|
|
|
|
B(3,1) |
B(3,2) |
|
|
|
Лекция 6 Информатика, часть 2 |
36 |
Алгоритм произведения матрицы А(N,M) на вектор B(M)
Входные данные: N,M, A(N,M), |
Задание начального |
||||
B(M) |
|
|
значения переменной |
||
Выходные данные: C(N) – вектор |
C(I)=0. |
||||
результата. |
|
Формула во внутреннем |
|||
|
цикле С(I)=C(I)+А(I,J)*B(J). |
||||
Вспомогательные данные: I,J |
|||||
|
|||||
Математическая постановка |
|
||||
задачи |
M |
|
|
||
|
|
A(I, J)* B(J) |
|
||
|
|
C(I) = å |
I=1,N,1 |
||
|
|
|
|
||
|
|
j= 1 |
|
C(I)=0 |
|
А(1,1) |
А(1,2) |
А(1,3) |
С(1) |
||
|
|||||
А(2,1) |
А(2,2) |
A(2,3) |
C(2) |
J=1,M,1 |
|
А(3,1) |
А(3,2) |
А(3,3) |
C(3) |
C(I)=C(I)+A(I,J)*B(J) |
|
B(1) |
B(2) |
B(3) |
|
||
|
|
||||
Лекция 6 Информатика, часть 2 |
37 |
Алгоритм преобразования матрицы в одномерный массив
Преобразовать массив А(N,М) в вектор
Х(N*M).
Входные данные: N,M, A(N,M).
Выходные данные: X(N*M) – вектор, в который последовательно переписаны строки массива А.
Вспомогательные данные: I,J Математическая постановка задачи
L = (I − 1) * M + J
X (L) = A(I , J )
Формулы в цикле: Вычисление значения индекса массива Х L=(I-1)*M+J
Запись элемента X(L)=A(I,J)
I=1,N,1
J=1,M,1
А(1,1) |
А(1,2) |
А(1,3) |
N=2, M=3 |
L=(I-1)*M+J |
|
||||
А(2,1) |
А(2,2) |
A(2,3) |
N*M=6 |
|
X(1) X(2) X(3) X(4) X(5) X(6) |
X(L)=A(I,J) |
|||
|
||||
I=2, J=1, M=3 |
|
|
|
|
L=(I-1)*M+J=(2-1)*3+1=4 |
|
|||
X(4)=A(2,1) |
|
Информатика, часть 2 |
38 |
|
Алгоритм нахождения максимального элемента в строках двумерного массива
Найти максимальные элементы в
строках массива В (N, M) с запоминанием максимального элемента и его индекса.
Входные данные: N, M, B(N,M).
Выходные данные: MAX(N) – массив максимальныx элементов, IMAX (N) –массив индексов максимальных элементов.
Вспомогательные данные: I,J Постановка задачи
В(I,1) |
B(I,2) |
B(I,3) |
IMAX(I) |
MAX(I) |
10 |
20 |
10 |
2 |
20 |
1 |
10 |
20 |
1 |
25 |
2 |
30 |
25 |
2 |
30 |
Задание начальных значений
MAX(I)=B(I,1), IMAX(I)=1.
Формулы в цикле
МАХ(I)=B(I,J) и IMAX(I)=J ,
если МАХ(I)>B(I,J)
I=1,N |
|
MAX(I)=B(I,1) |
|
IMAX(I)= 1 |
|
J=1,M |
|
Нет |
IMAX(I) |
MAX(I)>B(I,J) |
|
Да |
MAX(I) |
|
|
MAX(I)=B(I,J) |
|
IMAX(I)= J |
|
Лекция 6 Информатика, часть 2 |
39 |
Алгоритм удаления строки из матрицы
Удаление К строки из матрицы |
Формула в цикле |
|
А(N,М). |
A(I,J)=А(I+1,J) |
|
Все строки, начиная с К+1 |
|
|
переместить вверх. Число строк |
|
|
уменьшится на 1. |
N=N-1 |
|
Входные данные: N,M, К, A(N,M). |
||
Выходные данные: А(N-1,M) |
|
|
Вспомогательные данные: I,J |
I=K,N,1 |
|
Математическая постановка задачи |
||
|
A(I, J ) = |
A(I + 1, J ) |
J=1,M,1 |
||||
100 |
100 |
100 |
K=3 |
|
|
A(I,J)=A(I+1,J) |
1 |
200 |
200 |
1 |
100 |
100 |
|
300 300 300 |
2 |
200 |
200 |
|
||
1 |
400 |
400 |
3 |
400 |
400 |
|
100 |
100 |
100 |
100 |
100 |
100 |
|
Лекция 6 Информатика, часть 2 |
40 |