Иллюстрированный самоучитель по задачам и примерам Assembler

Действия с матрицами

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

Транспонирование прямоугольной матрицы

Приемы работы с массивами размерностью больше 1 удобно рассматривать на типовой задаче, например, такой как транспонирование матрицы.

Суть задачи транспонирования матрицы А = {аij} заключается в замене строк столбцами и столбцов строками в соответствии с формулой а 'ij= аij, где а 'ij – элементы транспонированной матрицы А' = {аij}. Максимальная величина индексов i и j задается константами m (количество строк) и т (количество столбцов), соответственно диапазон их значений составляет: i = 0..m-1, j ~ 0..n-1. Элементы матрицы задаются статически – в сегменте данных.

Выше уже отмечалось то, каким образом производится локализация в памяти элемента многомерного массива исходя из его логического номера при условии, что размерность элементов – 1 байт. Локализация элемента матрицы А относительно базового адреса производится по формуле: аij = n*i+j. (2.1)

Соответствующий элемент в транспонируемой матрице будет расположен по адресу: A'ij-m*i+j. (2.2)

Например, рассмотрим матрицу 3x4:

02h 04h 06h 08h

16h 24h 38h 45h

47h 48h 57h 56h

Эта матрица в памяти будет выглядеть так:

02h. 04h, 06h. 08h. 16h. 24h. 38h. 45h. 47h. 48h, 57h. 56h

Транспонированный вариант матрицы:

02h 16h 47h

04h 24h 48h

06h 38h 57h

08h 45h 56h

Транспонированный вариант матрицы в памяти будет выглядеть следующим образом:

02h. 16h. 47h. 04h. 24h. 48h. 06h. 38h, 57h. 08h. 45h. 56h

Для решения задачи "в лоб" по формулам 1 и 2 требуется выделять в памяти область для хранения транспонированной матрицы, совпадающую по размеру с исходной.

;prg29_102.asm – программа на ассемблере транспонирования матрицы.
:Вход: mas[n] – матрица mxn.
:Выход: _mas[n] – транспонированная матрица nxm.
.data
m dw 3: i =0.. 2
n dw 4;j=0..3
:задаем матрицу 3x4 (mxn):
mas db 02h.04h.06h.08h.l6h.24h,38h.45h.47h,48h.57h,56h
s_mas=$-mas
_mas db sjnas dup (Offh)
temp db 0
'code'
mov cx.m
xorsi.si:i: = 0 ml: push ex:цикл по i
xordiidi;J:-0
локализуем masij по формуле: masij=n*i+j m2: mov ax.n
mul si предполагаем, что результат в рамках ах
add ax.di: n*i+j
mov bx.ax
mov al,mas[bx]
movtemp.al локализуем место-приемник в jnasij по формуле: _masij=masji=m*i+j
mov ax.m
mul di предполагаем, что результат в рамках ах
add ax,si
mov al.temp
mov _mas[bx].al
incdi:j: = j+l
loop rn2
inc si
pop ex восстанавливаем счетчик внешнего цикла
loop ml

Отметим, что для транспонирования прямоугольной матрицы необязательно ее моделировать так, как это сделано в предыдущей программе. Кнут приводит соотношение, которое позволяет транспонировать матрицу в линейном порядке, зная только значения тип. Для этого используется соотношение, при котором значение из ячейки i (для 0<i<N = mn-1) исходной матрицы переводится в ячейку m*x (mod N) транспонированной матрицы.

Если Вы заметили ошибку, выделите, пожалуйста, необходимый текст и нажмите CTRL + Enter, чтобы сообщить об этом редактору.