Алгоритмы обхода матрицы

[mrcnn]

Задача следующая. Есть матрица размера mxn
Нужно отсортировать элементы матрицы и пройти ее по часовой стрелке от начала до центра, располагая в матрице отсортированные ее элементы.

Например, если дана матрица A(m,n) {a(i,j)-элементы} и m=n=3, то проход a(1,1) -> a(1,2) ->a(1,3) -> a(2,3) -> a(3,3) -> a(3,2) -> a(3,1) -> a(2,1) --> a(2,2)

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

'Расположить элементы матрицы по часовой стрелке в возрастающем порядке
Dim a(),x(), sx,posy,posx,numx,numy,k,i,j,l,m,n,s, u, msg, msgst,msgp, nn,tmp

input()
msg=sort(x)
sx=split(msg,"~")
msgp=arr_to_string(sx,1)
msgst=arr_to_string(a,2)

u=0
l=0
numy=Ubound(a,1)
numx=Ubound(a,2)
posy=0
posx=0
i=0

''''''''''один поворот на 3 четверти'''''''''''''
For j=posx To numx
a(i,j)=eval(sx(l))
l=l+1
Next
j=j-1
numx=posx
posx=j

For i=posy+1 To numy
a(i,j)=eval(sx(l))
l=l+1
Next
i=i-1
numy=posy
posy=i

if m<>0 then
For j=posx-1 To numx Step -1
a(i,j)=eval(sx(l))
l=l+1
Next
j=j+1
numx=posx
posx=j
numy=numy+1
end if



'''''''''''следующие повороты на 2 четверти''''''''''
nn=1
while (l<Ubound(sx))
if ((nn Mod 2) <> 0) then

if nn>2 then numy=numy+1

For i=posy-1 To numy Step -1
a(i,j)=eval(sx(l))
l=l+1
Next
i=i+1
numy=posy
posy=i

For j=posx+1 To numx-1
a(i,j)=eval(sx(l))
l=l+1
Next
j=j-1
numx=posx
posx=j

nn=nn+1

else

For i=posy+1 To numy-1
a(i,j)=eval(sx(l))
l=l+1
Next
i=i-1
numy=posy
posy=i

if nn>1 then numx=numx+1

For j=posx-1 To numx Step -1
a(i,j)=eval(sx(l))
l=l+1
Next
j=j+1
numx=posx
posx=j

nn=nn+1

end if
wend


''''''''' Вывод матрицы '''''''''
msg = arr_to_string (a,2)
msgBox("Последовательность: "&vbcrlf& msgp&vbcrlf& _
"Начальная матрица: "&vbcrlf& msgst&vbcrlf&_
"Конечная матрица: "&vbcrlf& msg&vbcrlf)

''''''''''''''''''''''''''''''''''''''''''''''''''''''
Function sort (x())
Dim i,j,s

For i=0 To Ubound(x)-1
For j=i+1 To Ubound(x)
If (x(i)>x(j)) then
tmp=x(j)
x(j)=x(i)
x(i)=tmp
end if
next
next

s=join(x,"~")
sort=s
End Function

Sub input()
Dim k,i,j,t
k=0
m=inputbox("Размерность по y?")
while (not isnumeric(m) or isempty(m) or isnull(m) or m<0)
m=inputbox("Введено некорректное значение. Введите размерность по y")
wend
n=inputbox("Размерность по x?")
while (not isnumeric(n) or isempty(n) or isnull(n) or n<0)
n=inputbox("Введено некорректное значение. Введите размерность по x")
wend
Redim a(m,n)
For i=0 To Ubound(a,1)
For j=0 To Ubound(a,2)
t=inputbox("Введите a("&i&","&j&")")
while (not isnumeric(t) or isempty(t) or isnull(t))
t=inputbox("Введено некорректное значение. Введите a("&i&","&j&")")
wend

Redim Preserve x(k)
a(i,j)=t
x(k)=eval(a(i,j))
k=k+1
Next
Next

End Sub

Sub arr_print(p(), r)
Dim i,j
Select Case r
Case "1"
For i=0 To Ubound(p)
msgBox "p("&i&")/"&p(i)&"/"&vbcrlf
Next
Case "2"
For i=0 To Ubound(p,1)
For j=0 To Ubound(p,2)
msgBox "p("&i&","&j&")="&p(i,j)&vbcrlf
Next
Next
case else
MsgBox("Not supported")
End Select
End Sub


Function arr_to_string(p(), r)
Dim msg,i,j
msg=""
Select Case r
Case "1"
For i=0 To Ubound(p)
msg=msg & p(i) & " "
Next
msg=msg&vbcrlf
Case "2"
For i=0 To Ubound(p,1)
For j=0 To Ubound(p,2)
msg=msg & p(i,j) & " "
Next
msg=msg&vbcrlf
Next
case else
MsgBox("Not supported")
End Select
arr_to_string=msg
End Function



Главное, чтобы мне подобные задачи на экзамене или на зачете не попались, потому что за 2-3 часа написать нереально.

[amel27]

1. Хорошо бы иметь таблицу преобразования (ТП) между координатами элемента в матрице и положением в одномерном массиве "раскрученной спирали", тогда заполнение выполняется за один проход... К примеру для матрицы 3x3 таблица преобразования будет (x,y) = {(1,2) (1,3) (2,3) (3,3) (3,2) (3,1) (2,1) (2,2)}, т.е. по сути это двумерный массив указателей.

2. Теперь как можно построить ТП. Допустим, мы можем построить ее для одного оборота обхода матрицы (MxN) начав с левого верхнего угла, т.е. имеем ф-цию Fun (N, M, I, J), добавляющую в конец глобальной ТП координаты обхода (I, J - "координаты" начала обхода). Так вот, полный путь состоит из последовательности: Fun (N,M, 0,0) --> Fun (N-2,M-2, 1,1) --> Fun (N-4,M-4, 2,2) ... пока размерность массива >0.

3. Алгоритм Fun (M, N, I, J) линеен и состоит из четырех отрезков:
- y=J, x увеличивается от I до I+N-1
- x=I+N-1, y увеличивается от J до J+M-1
- y=J+M-1, x уменьшается от x=I+N-1 до I
- x=I, y уменьшается от J+M-1 до J+1

З.Ы. Это только общий алгоритм... Звиняюсь, но из вашего кода я мало чего понял, и про "четверти" с "поворотами" тоже.

[mrcnn]

З.Ы. Это только общий алгоритм... Звиняюсь, но из вашего кода я мало чего понял, и про "четверти" с "поворотами" тоже.

Полный поворот для матрицы 3x3 это проход от a(1,1) до a(2,1) - по 2 строкам и 2 столбцам
Три четверти поворота это проход от a(1,1) до a(3,1) - по 2 строкам и столбцу

В коде делается следующее.
Задаются начальные значения позиции в матрице и конечные значения:
1. проход по первой строке (четверть от полного поворота по часовой стрелке от a(1,1) до a(1,1)). После каждой четверти поворота меняем начальные значения на конечные. Строка(y) фиксируется, столбцы(x) меняются.
2. проход по последнему столбцу (вторая четверть поворота). Столбец(x) фиксируется, строки(y) меняются.
3. проход по последней строке (четверть поворота - всего 3/4 поворота)

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

По-моему вы предложили то же самое..
Есть ли еще какие-нибудь способы?

[pva]

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

в цикле:
1. прошли верхнюю строчку
2. повернули на 90 CCW (кто фотошоп видел, поймёт)

дальше варианты: копировать матрицу или поворачивать координатную ось. Дешевле повернуть ось (понятней - наоборот). Так и сделаем!

// извиняюсь, что пишу не на языке вопроса, но если идея зацепит, попробую перевести
class pass_matrix
{
static const int gwidth = 10; // начальная ширина
static const int gheight = 20; // начальная высота

int matrix[gwidth*gheight];

int width; // ширина
int height; // высота
int a, b, c, d; // преобразование координат
// x1 = a*x + b
// y1 = c*y + d
int x, y; // смещение

void print()
{
std::cout << "{" << x << ", " << y << "}: "
<< matrix[x + y*qwidth] << "\n";
}

public:
pass_matrix() :
matrix(),
width(gwidth),
height(gheight),
a(1), b(0),
c(1), d(0),
x(0), y(0)
{
// начальная позиция:
// 0123
// 0x->.
// 1....
// 2....
}
private:

void step()
{
// делаем один шаг
x += a;
y += b;
}

void rotate()
{
// шаг назад
// 0123
// 0....x
// 1...|
// 2...v
x += c - a;
y += d - b;

// поворот матрицы (направления)
int a1 = c;
int b1 = d;
int c1 = -a;
int d1 = -b;

a = a1;
b = b1;
c = c1;
d = d1;

// поворот и усечение размеров
--height;
std::swap(width,height);
}

public:
void main()
{
while (0<height)
{
for (int w=width; 0<=--w; step())
{
print();
}

rotate();
}
}
};

если в линейных преобразованиях не напутал, то должно работать