Компьютерный форум OSzone.net  

Компьютерный форум OSzone.net (http://forum.oszone.net/index.php)
-   Программирование и базы данных (http://forum.oszone.net/forumdisplay.php?f=21)
-   -   Алгоритмы обхода матрицы (http://forum.oszone.net/showthread.php?t=73476)

mrcnn 25-10-2006 09:04 502377
Алгоритмы обхода матрицы
 
Задача следующая. Есть матрица размера 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 25-10-2006 12:50 502481
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 25-10-2006 16:09 502577
Цитата:
З.Ы. Это только общий алгоритм... Звиняюсь, но из вашего кода я мало чего понял, и про "четверти" с "поворотами" тоже.
Полный поворот для матрицы 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 25-10-2006 22:07 502702
есть, их полно. Правда чем дальме - тем более извращённый способ получается.
Например, сведём всё к одной операции прохода строчки и одной операции поворота матрицы (всё это в цикле).

в цикле:
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();
        }
    }
};
если в линейных преобразованиях не напутал, то должно работать


Время: 01:26.

Время: 01:26.
© OSzone.net 2001-