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

Приемы работы с массивами размерностью больше 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) транспонированной матрицы.

Содержание Назад Вперед

Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий