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]);
  Na početku kreiramo niz sa 10 elemenata, korišćenjem funkcije array().
  Ovo će kreirati niz u memoriji, a promenljiva A je referenca koja nas povezuje sa nizom.
  
  Prvom elementu niza pristupamo preko indeksa 1.
  
  Pošto pseudo-kod nije strogo tipiziran jezik, elementi niza mogu biti različitih tipova. 
    Prvi je bio broj, drugi je string.
  
  Ovde promenljivoj B dodeljujemo niz A. Ovo nije kopiranje niza, znači
    B neće postati novi niz, već samo nova referenca na isti niz na koji je i A
    referenca.
  
  Šta to znači u praksi? Pa znači da sve što radimo sa nizom B će se odraziti i na niz A.
  Ovde smo promenili vrednost drugog elementa niza B.
  
  Pokrenite program da biste videli šta ćete dobiti kao rezultat kada sada ispišemo vrednost
  drugog elementa niza A. Da li očekujete "Tekst" ili "Novi tekst"?

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]);
  }
  Prvo unosimo broj elemenata niza i pazimo da taj broj bude manji ili jednak maksimalnom broju elemenata.
  Započinjemo brojački ciklus u kome brojačka promenljva uzima vrednosti od 1 do N.
  U ciklusu se unosi i-ti element - znači sa svakim prolaskom kroz ciklus unosimo novi elemenat niza.
  Ispis elemenata niza obavljamo kroz isti takav ciklus.

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]);
  }
  
  U ovom slučaju unosimo samo broj članova niza, a ako nas posle mrzi da unosimo sve te brojeve, 
  prosto možemo ubaciti slučajne brojeve. Ovde su to neki celi brojevi od 0 do 999.

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");
  }
  Unosimo x koje se traži.
  Posle poslednjeg elementa dodajemo broj koji je sigurno različit od x,
    kako ne bismo imali problem sa ispitivanjem nedefinisanog elementa.
  Kada nađemo element X, nema svrhe da "vrtimo" niz do kraja, pa zato koristimo while ciklus sa uslovom da se
    izvršava sve dok je trenutni elemenat niza različit od unetog X.
  
  Pošto može da se desi da se x ne nađe u nizu, moramo da se osiguramo da će se ciklus zaustaviti
    kada se stigne do kraja niza.
  
  Ako ciklus treba da nastavi sa izvršavanjem, prelazi se na sledeći elemenat.
  
  Kada se izađe iz ciklusa, proveravamo da li je i ostalo u okvirima niza - 
    ako jeste, znači da je element bio 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]);
  }
  
  Upoređivanje elemenata se obično obavlja kroz dve koncentrične petlje. Ovo je spoljni ciklus 
    kojim prolazimo od prvog do pretposlednjeg elementa.
  
  Unutrašnji ciklus nam služi da pokušamo da pronađemo indeks najmanjeg elementa, gledano od i-tog do poslednjeg.
  Najmanji element treba da se nađe na i-toj poziciji.
  
  Ako smo ga našli, vršimo zamenu i-tog i pronađenog elementa. Onda spoljni ciklus prelazi na sledeći element
    i cela se priča sa traženjem najmanjeg (od preostalih elemenata) ponavlja.

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);
    }
  }
  Prvo kreiramo matricu pomoću funkcije array() u kojoj zadajemo dva parametra - 
    maksimalan broj redova i maksimalan broj kolona.
  
  Onda od korisnika zahtevamo da unese koliko ćemo zaista imati redova i kolona za matricu.
  
  Spoljni ciklus služi da prolazimo kroz N redova...
  
  ...a unutrašnji da u svakom redu prolazimo kroz M kolona.
  
  Unutar ciklusa za element [i, j] generišemo slučajan broj. Ovako dobijamo svih NxM elemenata.

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);
  }
  Prolazimo kroz N redova.
  
  Za svaki red započinjemo sa "praznom" promenljivom R u koju ćemo dodavati elemente iz kolona.
  
  Onda za svaki (i-ti) red prolazimo kroz M kolona.
  
  Unutar unutrašnjeg ciklusa ne ispisujemo zaista elemenat A[i,j], već ga dodajemo u string promenljivu R.
  
  Tek kada dodamo sve elemente iz jednog reda, ispisujemo promenljivu R i tako dobijamo red po red ispisan jedan ispod drugog.

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 a_1,1 * a_2,2 - a_1,2 * a_2,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
a		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
b		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
a		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
b		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);}}
  
  Dakle j-ta kolona postaje j-ti red, dok i-ti red postaje i-ta kolona od pozadi.

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);}}
  
  U j,i-tielement matrice b ubacujemo [i,j]-ti element matrice a.
  Suštinski potpuno isti rezultat bismo dobili i da smo pisali b[i,j] = a[j,i].

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
a		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]);
  }
  Prvo što je karakteristično je to da se koristi samo jedan ciklus.
  
  Međutim, za pristup elementima nam svakako trebaju dva indeksa, 
    jedino što su oba jednaka - pristupamo i-toj koloni i-tog reda.

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]);
  }
  I dalje se koristi samo jedan ciklus.
  Za pristup elementima nam isto trebaju dva indeksa, ali drugi računamo na osnovu prvog.

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). Detaljnije o tome možete pročitati u tekstu o našoj politici privatnosti.