WEBnSTUDY.com
Algoritmi

Programiranje sa nizovima i matricama

Elementima niza pristupamo preko numeričkog (celobrojnog) indeksa, a da bismo obezbedili rad sa celim nizom, obično koristimo brojački ciklus pomoću koga pristupamo svim elementima niza. Ako radimo sa dvodimenzionalnim nizom, odnosno matricom, svakom elementu pristupamo pomoću dva indeksa, a za to obično koristimo koncentrične cikluse.

Ovde ćemo se upoznati sa nekim osnovnim programerskim rešenjima kada radimo zadatke sa nizovima. Naučićemo kako se pristupa pojedinim elementima niza, kako se niz unosi ili generiše i kako se "prolazi" kroz elemente niza i matrice. Objasnićemo šta su to pretraga i sortiranje niza, obnovićemo neke matematičke koncepte vezane za rad sa matricama, a koje bismo mogli programerski da rešimo (kao npr. determinanta matrice i množenje matrica), zatim ćemo se upoznati sa terminima kao što su rotacija i transponovanje, kao i šta su to dijagonale matrice.

Osnove rada sa nizovima

Pošto su nizovi složena struktura podataka, potrebno je da obavestimo računar o tome da je neka promenljiva u stvari niz. Neki programski jezici zahtevaju da se nizovi deklarišu na tačno određenom mestu (obično pre početka programa) kako bi kompajler unapred odvojio dovoljno memorije. Ovo je tzv. statička alokacija memorije, a takvi nizovi se nazivaju statički nizovi. Međutim, u nekim jezicima se nizovi kreiraju tokom izvršavanja programa, što predstavlja dinamičku alokaciju memorije, čime dobijamo tzv. dinamičke nizove.

Skript jezici poput JavaScripta i PHP-a koriste dinamičku alokaciju, pa ćemo i mi koristiti isti pristup u našem pseudo-kodu. Ne zaboravite da kreirate niz pre nego što počnete da ga koristite, a preporučujemo da to uradite na samom početku programa. U pseudo-kodu koristimo posebnu funkciju array(), kojoj kao parametre zadajemo maksimalne dimenzije niza (jedan broj za običan niz, dva broja za matricu, tri broja za trodimenzionalni niz, itd.)

a = array(N, M, ...);

Druga važna stvar je to što se u pseudo-kodu nizovima pristupa po referenci. Ovo je pristup koji ima i JavaScript - kada neku promenljivu proglasimo za niz, u stvari kreiramo niz negde u memoriji, a promenljiva je samo poveznica ka tom nizu. Ovo je važno da znamo zato što može da se desi da iskoristimo operator dodele nad nizom. U tom slučaju nećemo dobiti kopiju niza, već samo drugu promenljivu koja predstavlja isti niz u memoriji. Isto važi i kada niz prosleđujemo funkciji kao parametar.

a = array(100); b = a; // b je u stvari isti niz kao i a // sve što radimo sa nizom b, odraziće se na niz a

Pojedinom elementu niza pristupamo preko njegovog indeksa. Ako želimo da "automatizujemo" rad sa članovima niza, onda obično koristimo brojački ciklus (mada to nije obavezno slučaj) pomoću koga pristupamo svim elementima.

Rad sa nizovima

Deklarisanje niza

Hajde da počnemo sa samim osnovama - kako se kreira niz i demonstriranjem pristupa nizu putem reference.

a = array(10); a[1] = 156; a[2] = "Tekst"; b = a; b[2] = "Novi tekst"; write(a[2]);

Unos i ispis elemenata niza

Rad sa nizovima se uvek odvija kroz ciklus. To znači da kada zadamo broj elemenata niza, započinjemo ciklus kroz koji se unosi jedan po jedan element, a kasnije na isti način radimo i njihov ispis.

a = array(100); read(N); for (i = 1..N) { read(a[i]); } write("Uneti su članovi niza:"); for (i = 1..N) { write(i + ": " + a[i]); }

Unos elemenata niza sa tastature ćemo vršiti samo ako moramo, pošto se onda gubi puno vremena. Ovde možete videti deo programa koji možemo koristiti da niz popunimo slučajnim brojevima.

Ostali (sakriveni) delovi programa su isti kao u prethodnom primeru.

a = array(100); read(N); for (i = 1..N) { a[i] = trunc(rand()*1000); } write("Članovi niza:"); for (i = 1..N) { write(i + ": " + a[i]); }

Pretraga i sortiranje niza

Kada radimo sa nizovima, često se srećemo sa dva tipična problema - pronalaženje određenih elemenata unutar niza, kao i sortiranje elemenata niza po nekom redosledu. Osnovni zahtev ovih algoritama je da budu najbrži mogući, uz razuman utrošak memorije.

Tokom godina su razvijeni mnogobrojni algoritmi i metodi za pretraživanje i sortiranje. Te dve stvari vrlo često i idu ruku pod ruku, pošto se veliki broj algoritama za pretragu oslanja na posebno uređene elemente.

Pretraga i sortiranje niza

Pronalaženje elementa u nizu - sekvencijalna pretraga

Neki od prvih zadataka koje ćemo raditi će biti oni u kojima se traži da u nizu pronađemo određeni element. Dok vežbamo rad sa nizovima, koristićemo najjednostavniji algoritam, a to je sekvencijalna pretraga, što predstavlja "stručan" naziv za prostu pretragu ispitivanjem jednog-po-jednog elementa.

U ovom primeru ćemo pokušati da pronađemo indeks elementa koji je jednak unetoj vrednosti x.

a = array(100); read(N); write("Generisan niz:"); for (i = 1..N) { a[i] = trunc(rand()*100); write(i + ": " + a[i]); } read(x); a[N+1] = x-1; i = 1; while(a[i]<>x and i<=N) { i++; } if (i<=N) { write("Pronađen elemenat na poziciji " + i); } else { write("Traženi elemenat nije pronađen"); }

U ovoj situaciji je bilo smisleno prekinuti potragu kada se elemenat pronađe. U nekom drugom slučaju bismo morali da prođemo kroz sve elemente niza.

Postoji još veliki broj algoritama za pretragu, ali svi zahtevaju da podaci budu posebno pripremljeni (npr. binarna pretraga je veoma brza, ali zahteva sortiran niz) i vrlo često čak smešteni u nekoj sasvim drugačijoj strukturi podataka (stablo ili hash tabela).

Primer sortiranja niza - Selection sort

Sortiranje se obično sprovodi tako što međusobno upoređujemo elemente i ako treba, menjamo im mesta, da bismo tako malo-po-malo došli do sortiranog niza.

a = array(100); read(N); for (i = 1..N) { a[i] = trunc(rand()*1000); } for (i=1..N-1) { min = i; for (j=i+1..N) { if (a[j]<a[min]) { min = j; } } if (min > i) { t = a[i]; a[i] = a[min]; a[min] = t; } } write("Sortirani elementi:"); for (i = 1..N) { write(a[i]); }

Ovo nije ni najgori ni najbolji algoritam za sortiranje i ovde je dat samo kao primer. Ovaj i drugi algoritmi će biti detaljnije objašnjeni u posebnim lekcijama.

Osnove rada sa matricama

Već smo naučili da je matrica niz nizova, ili drugačije - dvodimenzionalni niz. Svakom elementu matrice pristupamo preko dva indeksa. Možete ih posmatrati kao indeks glavnog niza i indeks podniza, kao horizontalu i vertikalu, kao koordinate elementa - bilo koja definicija nam "završava posao".

Ako matrica ima isti broj redova i kolona, onda je to specifičan slučaj, tzv. kvadratna matrica.

Prolazak kroz matricu

Kao što nam za prolazak kroz elemente niza treba ciklus, za prolazak kroz sve elemente matrice potrebna su dva ciklusa - jedan unutar drugog. Jasno je i zašto - ako je matrica niz nizova, onda nam za prolazak kroz "glavni" niz treba spoljni ciklus, a onda, pošto je svaki element tog niza opet neki niz, koristimo unutrašnji ciklus da prođemo kroz elemente podniza.

Primer prolaska kroz elemente matrice

Formiranje matrice

Najpre ćemo demonstrirati prolazak kroz kompletnu matricu i to za deo programa u kome generišemo sve elemente kao slučajne brojeve.

a = array(100,100); read(N,M); for (i = 1..N) { for (j = 1..M) { a[i,j] = trunc(rand()*1000); } }

Ovaj deo programa ćemo kasnije dosta koristiti da bismo dobili matricu.

Ispis matrice

Ako matricu ispisujemo element po element, nećemo baš imati lep rezultat - svi elementi će biti ispisani jedan ispod drugog - kao niz, što je malo nrepregledno. Ovde ćemo pokušati da ispišemo matricu na "lepši" način.

a = array(100,100); read(N,M); for (i = 1..N) { for (j = 1..M) { a[i,j] = trunc(rand()*100); } } for (i = 1..N) { r = ""; for (j = 1..M) { r += a[i,j] + " "; } write(r); }

Linearna algebra

Determinanta matrice se može izračunati za kvadratnu matricu metodom Laplasovog razvijanja po nekom redu ili koloni (kada radimo "ručno" obično biramo red ili kolonu sa puno nula, da bismo manje računali). Dakle, prolazimo kroz elemente reda (ili kolone) i svakim od tih elemenata množimo minor po tom elementu (determinantu podmatrice koja se dobija kada se iz matrice eliminiše red i kolona tog elementa).

Tako dobijeni rezultati se sabiraju, s tim što neki imaju negativan predznak, koji se računa kao:

(-1)i+j // drugim rečima, negativni su oni sabirci za koje je zbir indeksa neparan

Pogledajmo kako bi izgledalo računanje determinante za matricu dimenzija [3,3]. Vršićemo razvijanje po prvom redu. To znači da prolazimo kroz elemente prvog reda i računamo proizvod tog elementa i njegovog minora (detrerminanta podmatrice). U svakoj matrici smo zeleno obojili su elemenat iz reda po kome razvijamo, a crvenom bojom elemente njegovog minora:

11 12 13
21 22 23
31 32 33
11 12 13
21 22 23
31 32 33
11 12 13
21 22 23
31 32 33
11 * det( [22 23] ) -12 * det( [21 23] ) +13 * det( [21 22] ) [32 33] [31 33] [31 32]

Determinanta matrice dimenzija [2,2] je a1,1 * a2,2 - a1,2 * a2,1. To nam daje rešenje:

11 * (22*33 - 23*32) -12 * (21*33 - 23*31) +13 * (21*32 - 22*31 )

Množenje dve matrice se može izvršiti samo ako je broj kolona prve matrice jednak broju redova druge matrice. Rezultujuća matrica ima broj redova prve i broj kolona druge matrice. Ova operacija se obavlja tako što se računaju sume proizvoda odgovarajučih elemenata. Suštinski ovo bi značilo:

A[N,M] x B[M,L] = C[N,L]

Kod rezultujuće matrice se [i,j]-ti elemenat dobija množenjem elemenata i-tog reda prve matrice sa j-tom kolonom druge matrice i sabiranjem tih proizvoda:

c[i,j] = a[i,1]*b[1,j] + a[i,2]*b[2,j] + ... + a[i,M]*b[M,j]

Rotiranje i transponovanje matrice

Rotiranje matrice predstavlja promenu pozicija elemenata na takav način da se matrica "obrne" za 90 ili 180 stepeni. Pogledajte primer kako bi izgledala rotacija matrice za 90 stepeni.

a j
1 2 3 4 5
i 1 11 12 13 14 15
2 21 22 23 24 25
3 31 32 33 34 35
b j
1 2 3
i 1 31 21 11
2 32 22 12
3 33 23 13
4 34 24 14
5 35 25 15

Transponovanje matrice predstavlja "obrtanje" matrice u smislu da redovi postaju kolone, a kolone redovi. To znači da od matrice dimenzija NxM dobijamo matricu dimenzija MxN.

a j
1 2 3 4 5
i 1 11 12 13 14 15
2 21 22 23 24 25
3 31 32 33 34 35
b j
1 2 3
i 1 11 21 31
2 12 22 32
3 13 23 33
4 14 24 34
5 15 25 35

Plavom bojom smo obeležili prvi red matrice kako biste lakše ispratili šta se dešava sa elementima prilikom rotacije i transponovanja.

Transformacije matrica

Rotacija za 90 stepeni

Rotaciju matrice za 90 stepeni bismo mogli da objasnimo u stilu:

  • prvi red postaje poslednja kolona
  • drugi red postaje pretposlednja kolona
  • ...
  • poslednji red postaje prva kolona
a=array(100,100); b = array(100,100); read(N,M); for (i = 1..N) { for (j = 1..M) { a[i,j] = trunc(rand()*100); }} ispis(a,N,M); for (i = 1..N) { for (j = 1..M) { b[j,N-i+1] = a[i,j]; } } write("Rotirano:"); ispis(b,M,N); function ispis(a,n,m){for (i = 1..n) {r = ""; for (j = 1..m) { r += a[i,j] + " "; }write(r);}}

Transponovanje

Najjednostavnije objašnjenje transponovanja je da se element sa pozicije [i,j] prebacuje na poziciju [j,i].

a=array(100,100); b = array(100,100); read(N,M); for (i = 1..N) { for (j = 1..M) { a[i,j] = trunc(rand()*100); }} ispis(a,N,M); for (i = 1..N) { for (j = 1..M) { b[j,i] = a[i,j]; } } write("Transponovano:"); ispis(b,M,N); function ispis(a,n,m){for (i = 1..n) {r = ""; for (j = 1..m) { r += a[i,j] + " "; }write(r);}}

Razmislite o zadatku koji bi bio memorijski efikasniji - u kome biste trebali da rotirate ili transponujete matricu bez korišćenja pomoćne matrice.

Dijagonale matrice

Kvadratna matrica nas zanima i zato što ima glavnu i sporednu dijagonalu. Glavna dijagonala ide od gornjeg-levog do donjeg-desnog elementa, a sporedna od gornjeg-desnog do donjeg-levog.

a j
1 2 3 4
i 1 11 12 13 14
2 21 22 23 24
3 31 32 33 34
4 41 42 43 44

U prikazanoj tabeli, zelene ćelije predstavljaju glavnu, a plave sporednu dijagonalu.

Prolazak kroz dijagonale

Elementi glavne dijagonale

Za ove elemente je karakteristično što su im oba indeksa ista.

a = array(100,100); read(N); for (i = 1..N) { for (j = 1..N) { a[i,j] = trunc(rand()*100); } } write("Elementi na glavnoj dijagonali:"); for (i = 1..N) { write(a[i,i]); }

Elementi sporedne dijagonale

Ovde takođe koristimo samo jedan ciklus, ali je potrebno malo računanja da bismo došli do ispravnog indeksa. Razmislite:

  • za prvi red traži se poslednja kolona [1,N]
  • za drugi red traži se pretposlednja kolona [2,N-1]
  • za treći red tražimo element [3,N-2]
    ...
  • za poslednji red traži se prva kolona [N,1]
a = array(100,100); read(N); for (i = 1..N) { for (j = 1..N) { a[i,j] = trunc(rand()*100); } } write("Elementi na sporednoj dijagonali:"); for (i = 1..N) { write(a[i,N-i+1]); }

Razmislite kako biste napravili program koji radi sa npr. elementima ispod glavne dijagonale. U tom slučaju biste koristili dva ciklusa, ali da li bi oba baš išla od 1 do N?

Svi elementi sajta Web'n'Study, osim onih za koje je navedeno da su u javnom vlasništvu, vlasništvo su autora i ne smeju se koristiti, u celosti ili delimično bez pismenog odobrenja autora. To uključuje tekstove, slike, ilustracije, animacije, prateći grafički materijal i programski kod.
Ovaj sajt koristi tehnologiju kolačića (cookies) radi vođenja interne statistike u cilju unapređenja korisničkog iskustva. Tako prikupljeni podaci su anonimni i nedostupni trećim licima. Vaša privatnost nije ugrožena ni na koji način.