Spiral Matrix Algorithm


Spiralno popunjavnje elemenata matrice tema je za Euler Problem 28. Zadatak na oko jednostavan, ali u biti  vrlo interesantan. Prvo pogledajmo šta znači spiralno popunjavanje elemenata matrice. Pod ovim pojmom podrazumijeva se popunjavanje elemanata matrice krećući od centralnog elementa matrice u smijeru okretanja kazaljke ili suprotno, sve dok se ne dođe do zadnjeg elementa matrice. Npr: na sljedećoj slici imamo matricu 5×5 koja je na takav način popunjena.

image

Krećući iz centra u desnu stranu spiralno izlazimo i završavamo na prvom desnom elementu. Postoji više varijanti algortima u smislu smijera spirale i početka popunjavanja, al u biti svi se svode na spiralno popunjavanje.

Euler Problem 28 zahtjeva da se pronađe zbir svih brojeva na glavnoj i pomoćnoj dijagonali matrice 1001×1001. Naravno ovaj zadatak se može riješiti i bez generiranja spiralne matrice, jednostavnim izračunavanjem koji broj će zaposjesti određeni index u matrici.

Uslov ovog algoritma (odnosno problema 28) je da je je matrica kvadratna i da je broj kolona / vrsta neparan broj. U spuprotnom nebi imali elementa koji se ukršta sa dijagonalama. Za parni broj vrsta / kolona imamo spuprotan spiralni smijer.Ako bi htjeli da se i paran ran matrice popunjava na isti način krenuli bi sa popunjavanjem od elementa sa najvećim indeksom(donji desni element).

Rješenje za ovaj problem na samom početku sam koncipirao da to bude na način da se izgenerira takva matrica, i onda se sa saberu svi članovi sa glavne i pomoćne dijagonale, bez obzira što je proračun vrijednosti elemenata na dijagonalama dosta brža operacija i nije brute-force rješenje.

U ovom postu će biti prikazan samo algoritam spiralnog popunjavanja matrice, a čitaocu se ostavlja da riješi problem 28, na osnovu algoritma što predstavlja trivijalnu radnju:

U samoj koncepciji izrade algoritma potrebno je posmatrati obrnuti postupak popunjavanja jer se kreće od nekog početka, a ne iz sredine, jer to pojednostavljiva indeksiranje u petljama. U biti postoje  4 slučaja ovakvog popunjavanja i to: s desna na lijevo, odozgo prema dolje, s lijeva prema desno i na kraju odozdo prema gore.

//Spiral algorithm
static int [][] SpiralAlgorithm(int m)
{
    int i, j;
    int elNumber = 0;
    int mode = 0;
    int[][]  A = new int[m][];

    for (i = 0; i < m; i++)
    {
        A[i] = new int[m];
        for (j = 0; j < m; j++)
            A[i][j] = 0;
    }
    i = 0;
    j = 0;
    mode = 1;
    elNumber = (m * m);
    while (elNumber > 0)
    {
        //Na lijevo
        if (mode % 4 == 1)
        {
            int k;
            for (k = m - 1; k >= 0; k--)
            {
                if (A[i][k] > 0)
                    continue;

                A[i][k] = elNumber;
                elNumber--;
            }
            mode++;
        }
        //Prema dolje
        else if (mode % 4 == 2)
        {
            for (int k = 0; k < m; k++)
            {
                if (A[k][j] > 0)
                    continue;

                A[k][j] = elNumber;
                elNumber--;
            }
            mode++;
        }
        //Donji prema desno
        else if (mode % 4 == 3)
        {
            int l = m - 1 - i;

            for (int k = 0; k < m; k++)
            {
                if (A[l][k] > 0)
                    continue;

                A[l][k] = elNumber;
                elNumber--;
            }
            mode++;

        }
        //dolje gore
        else if (mode % 4 == 0)
        {
            int l = m - 1 - j;
            for (int k = m - 1; k >= 0; k--)
            {
                if (A[k][l] > 0)
                    continue;

                A[k][l] = elNumber;
                elNumber--;
            }
            mode++;
            j++;
            i++;
        }
    }
    return A;
}

Na početku je inicijalizacija pomoćnih varijabli korištenih u algoritmu, a zatim petlja while koja se izvršava dok ne posjetimo sve elemente matrice.Kada se napravi test za matricu 9×9 imamo sljedeći kod i izlaz na konzoli:

static void Main(string[] args)
{
    int [][] A;
    Console.WriteLine("Unesi dimenziju kvadratne matrice:m");
    int m=int.Parse(Console.ReadLine());

    A = SpiralAlgorithm(m);
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<m;j++)
        {
            Console.Write("{0}\t",A[i][j]);
        }
        Console.WriteLine("");
        Console.WriteLine("");
    }
    Console.WriteLine("Press any key to continue...");
    Console.ReadLine();
 }

image

About Bahrudin Hrnjica

PhD in Mechanical Engineering, Microsoft MVP for .NET. Likes .NET, Math, Mechanical Engineering, Evolutionary Algorithms, Blogging.

Posted on 06/01/2010, in C#, Programiranje, Project Euler and tagged , . Bookmark the permalink. 3 Comments.

  1. Denis Biondic

    heh … lijepo je vidjeti da ima još netko u Bihaću da ga .NET zanima :)

    P.S. Gledam ovaj primjer spirale, hvata me nostalgija kad sam ovo radio u C++-u :) Kod je skoro identičan ovome, a probao sam i implementaciju preko OOP-a. Fin zadačić, nema šta…

    Pozdrav!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s