Ovde smo pripremili zadatke za vežbanje programiranja sa dvodimenzionalnim nizovima - matricama.
Poznavanje rada sa matricama je od velikog značaja u praktičnom programiranju, pošto smo često u prilici da radimo sa
podacima koji su tabelarno predstavljeni. Rad sa matricama je bitan u kompjuterskoj grafici (2D i 3D transformacije,
primena efekata na slikama), pa čak i u kompjuterskim igrama.
U stvari, kada se uvežbamo u rešavanju ovakvih zadataka, biće nam mnogo lakše da pojmimo bilo kakvu drugačiju strukturu
gde su podaci "zadati" unutar drugih podataka.
Najpre ćemo kreirati malu biblioteku funkcija koje ćemo koristiti za neke aktivnosti
koje se stalno ponavljaju - unos i ispis, automatsko kreiranje niza i matrice.
Zahvaljujući ovim funkcijama, naši programi će biti čitljiviji.
Funkcije
Ovo su funkcije koje se bave nekim operacijama koje se često ponavljaju. Izdvojili smo ih na posebno
mesto, a često koristimo
function unosNiza(a, n) {for (i=1..n) { read(a[i]); } }
function popunaNiza(a,n, kor) {for (i=1..n) { a[i] = trunc(rand()*100) + kor; } }
function ispisNiza(a, n) { s=""; for (i=1..n) { s += a[i] + " "; } write(s); }
function unosMatrice(a, n,m) {for (i=1..n) { write("Unos " + i + ". reda"); for (j=1..m) {read(a[i,j]);}} }
function popunaMatrice(a, n,m, kor) { for (i=1..n) { for (j=1..m) { a[i,j] = trunc(rand()*100) + kor; }} }
function popunaMatriceSmall(a, n,m) { for (i=1..n) { for (j=1..m) { a[i,j] = trunc(rand()*10); }} }
function priprema(num) {s = str(num); match (len(s)) { value(1) { s = " " + s; } value(2) {s = " " + s;} } return(s); }
function ispisMatrice(a, n,m) { for (i=1..n) {r = ""; for (j=1..m) {r += priprema(a[i,j]) + " ";} write(r); } }
Zadaci za vežbu
Najpre počinjemo sa nekoliko osnovnih zadataka.
Ovi zadaci dosta podsećaju na zadatke koje smo radili sa nizovima, s tim što sada radimo sa "nizovima nizova". Samim tim,
zadaci postaju malo drugačiji i zanimljiviji. Prva razlika je što moramo da koristimo ugnježdene cikluse (ciklus unutar ciklusa)
kako bismo pristupili svim elementima matrice.
Zadatak A.1
Za unetu numeričku matricu A[N,M], kreirati niz od M elemenata koji sadrži
aritmetičke sredine svih kolona matrice.
Za matricu od 3x4 elementa, dobijamo niz od 4 elementa:
1
2
10
12
5
9
11
4
9
10
9
8
5
7
10
8
_show;mat--sr
a = array(50,50); p = array(50); read(n,m); popunaMatrice(a, n,m, -50); ispisMatrice(a,n,m);
for (j=1..m) {
s = 0;
for (i=1..n) {
s += a[i,j];
}
p[j] = s / n;
}
write("Proseci kolona:"); ispisNiza(p,m);
Zadatak A.2
Za unete numeričke nizove A[N] i B[M], kreirati matricu C[NxM] (od N redova i M kolona)
koja se dobija množenjem "vektora" A i B.
Ako npr. imamo nizove A[3] i B[4], množenjem odgovarajućih elemenata dobijamo matricu C[3,4]:
Zadatak A.3
Za zadate matrice A i B, od N redova i M kolona, kreirati novu matricu C čiji se svaki elemenat dobija
kao veći od odgovarajućih elemenata matrica A i B.
Ako npr. imamo dve matrice od 3x4 elementa, pogledajte kako se "sklapa" rezultujuća matrica:
Zadatak A.4
Za unetu kvadratnu numeričku matricu A[N,N], proveriti da li su jednaki svi zbirovi elemenata po vrstama i kolonama.
1
3
6
10
2
6
2
10
7
1
2
10
10
10
10
_show;mat--sr
a = array(20,20); read(n); unosMatrice(a, n,n);
sum = 0;
for (j=1..n) { sum += a[1,j]; }
ok = true;
for (i=2..n) {
s = 0;
for (j=1..n) {
s += a[i,j];
}
if (sum <> s) {
ok = false;
}
}
if (ok) {
for (j=1..n) {
s = 0;
for (i=1..n) {
s += a[i,j];
}
if (sum <> s) {
ok = false;
}
}
}
if (ok) { write("SVE SUME JEDNAKE"); }
else { write("Nisu sve sume jednake"); }
Zadatak A.5
Automobilski servis je u toku meseca popravio N vozila.
Radnici u servisu umeju da poprave M kvarova i izveštaj o popravkama daju u tabeli A[N,M],
čiji elementi imaju sledeće vrednosti:
a[i,j] = 1 ako je vozolo i imalo kvar j
a[i,j] = 0 u suprotnom
a) ispisati redne brojeve vozila koja su imala SVE kvarove
b) naći ukupan broj vozila koja su imala K kvarova
c) ispisati redni broj kvara koji se najčešće dešavao
Podrazumeva se da su podaci ispravno uneti, pa to ne moramo da proveravamo.
REZULTAT: 2
1
0
1
0
1
1
1
1
0
0
1
1
Za K=2, REZULTAT: 2 kolone
1
0
1
0
1
1
1
1
0
0
1
1
REZULTAT: 3
1
0
1
0
1
1
1
1
0
0
1
1
_show;mat--sr
a = array(50,50); read(n, m); unosMatrice(a, n,m);
write("Sve kvarove su imali:");
for (i=1..n) {
s = 0;
for (j=1..m) {
s += a[i,j];
}
if (s==m) {
write("Vozilo " + i);
}
}
read(k);
num = 0;
for (j=1..m) {
s = 0;
for (i=1..n) {
s += a[i,j];
}
if (s==k) {
num++;
}
}
write(k + " kvarova je imalo " + num + " vozila.");
max = 0;
mj = 0;
for (j=1..m) {
br = 0;
for (i=1..n) {
br += a[i,j];
}
if (br > max) {
max = br;
mj = j;
}
}
write("Najčešće se dešavao kvar broj " + mj);
Dijagonale matrice
Zadatak B.1
Pronaći indeks najvećeg elementa na glavnoj dijagonali kvadratne matrice od N elemenata.
Zadatak B.2
Izračunati aritmetičku sredinu elemenata na sporednoj dijagonali kvadratne matrice od N elemenata.
1
2
12
4
3
9
11
8
7
10
2
5
1
6
14
3
_show;mat--sr
a = array(50,50); read(n); popunaMatrice(a, n,n, -50); ispisMatrice(a, n,n);
s = 0;
for (i=1..n) {
s += a[i, n-i+1];
}
p = s/n;
write(p);
Zadatak B.3
Za unetu numeričku kvadratnu matricu A[N,N], izračunati zbir svih elemenata iznad glavne dijagonale,
uključujući i elemente na samoj dijagonali.
1
2
12
4
3
9
11
8
7
10
2
5
1
6
14
3
_show;mat--sr
a = array(50,50); read(n); popunaMatrice(a, n,n, 0); ispisMatrice(a, n,n);
s = 0;
for (i=1..n) {
for (j=i..n) {
s += a[i,j];
}
}
write(s);
Zadatak B.4
Unosi se kvadratna matrica A[N,N], simetrična u odnosu na glavnu dijagonalu.
1
2
3
4
2
8
5
6
3
5
9
7
4
6
7
0
_show;mat--sr
a = array(50,50); read(n); unosMatrice(a, n,n);
sim = true;
for (i=2..n) {
for (j=1..i-1) {
sim = sim AND (a[i,j] == a[j,i]);
}
}
if (sim) { write("Simetrična"); }
else { write("Nije simetrična"); }
Zadatak B.5
Zadata je kvadratna numerička matrica A[N,N].
Uporediti zbirove elemenata iznad i ispod sporedne dijagonale, ne računajući elemente na samoj dijagonali.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Prvo rešenje ovog zadatka će biti predstavljeno kroz nezavisni prolaz kroz oba "trougla".
_show;mat--sr
a = array(50,50); read(n); popunaMatrice(a, n,n, 0); ispisMatrice(a, n,n);
iznad = 0;
for (i=1..n-1) { for (j=1..n-i) { iznad += a[i,j]; } }
ispod = 0;
for (i=2..n) { for (j=n-i+2..n) { ispod += a[i,j]; } }
if (iznad > ispod) {
write("Elementi IZNAD imaju veću sumu");
}
else {
write("Elementi ISPOD imaju veću (ili jednaku) sumu");
}
U drugom rešenju imamo malo drugačiji pristup. Prolazimo kroz celu matricu, a onda ispitujemo
kom "trouglu" pripada koji element. Ovo radimo tako što znamo da se za svaki red, kolona elementa sa sporedne dijagonale
dobija kada od broja kolona oduzmemo redni broj reda i to korigujemo za 1.
_show;mat--sr
a = array(50,50); read(n); popunaMatrice(a, n,n, 0); ispisMatrice(a, n,n);
iznad = 0;
ispod = 0;
for (i=1..n) { for (j=1..n) {
if(j<n-i+1) {iznad += a[i,j];} elseif (j>n-i+1) {ispod += a[i,j];}
} }
if (iznad > ispod) {
write("Elementi IZNAD imaju veću sumu");
}
else {
write("Elementi ISPOD imaju veću (ili jednaku) sumu");
}
Zadatak B.6
Za unetu numeričku kvadratnu matricu A[N,N], proveriti da li je u pitanju magični kvadrat
(jednaki zbirovi po vrstama, kolonama i dijagonalama), uz uslov da je matrica popunjena isključivo brojevima
od 1 do N2, bez ponavljanja.
2
7
6
15
9
5
1
15
4
3
8
15
15
15
15
15
_show;mat--sr
read(n); a = array(n,n); d=array(n*n); unosMatrice(a, n,n);
ok = true;
sum = 0;
sd = 0;
for (i=1..n) {
for (j=1..n) {
if (a[i,j] > 0 AND a[i,j] <= n*n) {
if (d[a[i,j]] <> 1) { d[a[i,j]] = 1; }
else { ok = false; }
}
else { ok = false; }
}
sum += a[i,i];
sd += a[i, n-i+1];
}
ok = ok AND (sum == sd);
if (ok) {
for (i=1..n) {
sr = 0;
sk = 0;
for (j=1..n) {
sr += a[i,j];
sk += a[j,i];
}
ok = ok AND (sum == sr) AND (sum == sk);
}
}
if (ok) { write("MAGIČNI KVADRAT"); }
else { write("Nije magični kvadrat"); }
Prolazak kroz specifične elemente matrice
Zadatak C.1
Za zadatu matricu A[N,M], pronaći maksmume svih parnih i minimume svih neparnih kolona.
Rezultate smestiti u poseban niz.
1
2
3
4
5
6
7
8
9
10
11
12
_show;mat--sr
a = array(50,50); r=array(50); read(n,m); popunaMatrice(a, n,m, 0); ispisMatrice(a, n,m);
for (j=1..m) {
r[j] = a[1,j];
for (i=2..n) {
if (j % 2) {
uslov = a[i,j] < r[j];
}
else {
uslov = a[i,j] > r[j];
}
if (uslov) {
r[j] = a[i,j];
}
}
}
ispisNiza(r, m);
Zadatak C.2
Izračunati razlike najvećih i najmanjih elemenata numeričke matrice od A[N,M], isključivo parnih redova.
Rezultate smestiti u poseban niz.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
_show;mat--sr
a = array(50,50); r=array(25); read(n,m); popunaMatrice(a, n,m, 0); ispisMatrice(a, n,m);
k = 0;
i=2;
while (i <= n) {
min = a[i,1];
max = a[i,1];
for (j=2..m) {
if (a[i,j] < min) {
min = a[i,j];
}
if (a[i,j] > max) {
max = a[i,j];
}
}
k++;
r[k] = max-min;
i += 2;
}
for (i=1..v) { write(i*2 + ": " + r[i]); }
Zadatak C.3
Prebrojati koliko ima elemenata numeričke matrice A[N,M] koji su veći od nule, ali samo ako se gleda svaki drugi element,
kao po "šahovskom polju". Počinje se od elementa [1,1].
-1
2
12
-4
3
9
-11
-8
7
10
2
5
_show;mat--sr
a = array(50,50); read(n,m); popunaMatrice(a, n,m, -50); ispisMatrice(a, n,m);
br = 0;
moze = true;
for (i=1..n) {
for (j=1..m) {
if (moze AND a[i,j]>0) {
br++;
}
moze = NOT moze;
}
}
write(br);
Zadatak C.4
Ako su zadate dve numeričke matrice A[N,M] i B[M,L], izračunati matricu C[N,L] koja se dobija množenjem matrica A i B.
Ako npr. imamo matrice od 3x4 i 4x2 elementa treba da se dobije matrica od 3x2 elementa.
Elemenat [3,2] se dobija kao zbir proizvoda elemenata 3. reda matrice A i 2. kolone matrice B
(f = 9*2 + 10*4 + 11*6 + 12*8).
1
2
3
4
5
6
7
8
9
10
11
12
1
2
3
4
5
6
7
8
a
b
c
d
e
f
_show;mat--sr
a = array(50,50); b = array(50,50); c = array(50,50); read(n,m,l); popunaMatriceSmall(a, n,m); popunaMatriceSmall(b, m,l);
write("Matrica A"); ispisMatrice(a, n,m); write("Matrica B"); ispisMatrice(b, m,l);
for (i=1..n) {
for (j=1..l) {
c[i,j] = 0;
for (k=1..m) {
c[i,j] += a[i,k] * b[k,j];
}
}
}
write("Izračunata matrica C");
ispisMatrice(c, n,l);
Zadatak C.5
Data je matrica brojeva A od [N,M] elemenata. Elemenat a[i,j] se naziva "sedlo" ako je
najmanji u svojoj vrsti (i) i najveći u koloni (j). Formirati matricu S[N,M] čiji elementi
imaju vrednosti:
s[i,j] = 1 ako je a[i,j] sedlo
s[i,j] = 0 ako a[i,j] nije sedlo
11
12
13
14
15
81
82
55
84
85
31
32
33
34
35
41
42
43
44
45
_show;mat--sr
a=array(50,50); s=array(50,50); read(n, m); unosMatrice(a, n,m); write("Matrica A"); ispisMatrice(a, n,m);
for (i=1..n) { for (j=1..m) { s[i,j] = 0; } }
for (i=1..n) {
mj = 1;
for (j=2..m) {
if (a[i,j] < a[i,mj]) {
mj = j;
}
}
s[i,mj] = 1;
for (r=1..n) {
if (a[r,mj] > a[i,mj]) {
s[i,mj] = 0;
}
}
}
write("Matrica S");
ispisMatrice(s, n,m);
Zadatak C.6
U kvadratnoj matrici A[N,N] je data tabela fudbalskog turnira, gde elementi imaju sledeće vrednosti:
a[i,j] = 2 ako je ekipa I pobedila ekipu J
a[i,j] = 0 ako je ekipa I izgubila od ekipe J
a[i,j] = 1 ako su ekipe I i J igrale nerešeno
a) proveriti da li su podaci ispravno uneti: ako je a[i,j] = 2, onda mora da bude a[j,i] = 0 i obrnuto,
kao i da ako je a[i,j] = 1, onda mora da bude i a[j,i] = 1.
b) naći ukupan broj ekipa koje imale više pobeda nego poraza
c) naći ukupan broj ekipa bez poraza
U zadacima sadržaj glavne dijagonale može da se zanemari.
1
2
0
1
2
0
1
0
1
1
2
2
1
1
2
1
1
1
1
2
0
1
0
0
1
_show;mat--sr
a = array(50,50); read(n); unosMatrice(a, n,n);
ok = true;
for (i=1..n-1) {
for (j=i+1..n) {
match(a[i,j]) {
value(2) {ok = ok AND (a[j,i] == 0);}
value(0) {ok = ok AND (a[j,i] == 2);}
value(1) {ok = ok AND (a[j,i] == 1);}
}
}
}
if (ok) {
write ("Tabela je ispravno uneta.");
numB = 0; numC = 0;
for (i=1..n) {
pobede = 0;
bezPoraza = true;
for (j=1..n) {
if (i<>j) {
if (a[i,j] == 2) {pobede++;}
if (a[i,j] == 0) {pobede--; bezPoraza=false;}
}
}
if (pobede>0) {numB++;}
if (bezPoraza) {numC++;}
}
write("Broj ekipa koje imaju više pobeda od poraza: " + numB);
write("Broj ekipa bez poraza: " + numC);
}
else {write ("Tabela nije ispravna.");}
Transformisanje matrice
Zadatak D.1
Na osnovu unete matrice A[N,M] treba kreirati novu matricu B[N,M] koja se dobija kada se unetoj matrici
obrne redosled kolona.
a
b
c
d
1
2
3
4
5
6
7
8
d
c
b
a
4
3
2
1
8
7
6
5
_show;mat--sr
a = array(50,50); b = array(50,50); read(n,m); popunaMatrice(a, n,m, 0); write("Matrica A"); ispisMatrice(a, n,m);
for (i=1..n) {
for (j=1..m) {
b[i,j] = a[i,m-j+1];
}
}
write("Matrica B"); ispisMatrice(b, n,m);
Zadatak D.2
Na osnovu unete matrice A[N,M] treba kreirati novu matricu B[M,N] koja se dobija
rotiranjem početne matrice za 90 stepeni u smeru kazaljke.
a
b
c
d
1
2
3
4
5
6
7
8
5
1
a
6
2
b
7
3
c
8
4
d
_show;mat--sr
a = array(50,50); b = array(50,50); read(n,m); popunaMatrice(a, n,m, 0); write("Matrica A"); ispisMatrice(a, n,m);
for (i=1..n) {
for (j=1..m) {
b[j, n-i+1] = a[i,j];
}
}
write("Matrica B"); ispisMatrice(b, m,n);
Zadatak D.3
Unosi se matrica A od [N,M] elemenata i brojevi R, K, NB i MB.
Treba kreirati novu matricu B, od [NB,MB] elemenata koja predstavlja
podmatricu unete matrice sa početkom u redu R i koloni K. Podrazumeva se da dimenzije podmatrice
ne izlaze van okvira početne matrice.
Ako npr. imamo matricu od 4x5 elemenata i zadato R=1 i K=2, kao i dimenzije NB=3 i MB=2,
dobija se matrica od 3x2 elemenata:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
7
8
12
13
_show;mat--sr
a = array(50,50); b = array(50,50); read(n,m); popunaMatrice(a, n,m, 0); write("Matrica A"); ispisMatrice(a, n,m);
read(r,k, nb,mb);
for (i=1..nb) {
for (j=1..mb) {
b[i,j] = a[r+i-1,k+j-1];
}
}
write("Matrica B"); ispisMatrice(b, nb,mb);
Zadatak D.4
Dat je niz A[N]. Treba formirati kvadratnu matricu B[N,N],
čiji je prvi red jednak nizu A, a svaki sledeći red se dobija cikličnim pomeranjem
prethodnog reda ulevo za po jedan elemenat.
1
2
3
4
1
2
3
4
2
3
4
1
3
4
1
2
4
1
2
3
_show;mat--sr
a = array(50); b = array(50,50); read(n); popunaNiza(a, n, 0); write("Niz A"); ispisNiza(a,n);
for (i=1..n) {
b[1,i] = a[i];
}
for (i=2..n) {
for (j=1..n-1) {
b[i,j] = b[i-1,j+1];
}
b[i,n] = b[i-1,1];
}
write("Matrica B"); ispisMatrice(b, n,n);
Zadatak D.5
Napisati program kojim se u kvadratnoj matrici A[N,N], razmenjuju red koji sadrži
elemenat najveće vrednosti i kolona koja sadrži elemenat najmanje vrednosti.
11
12
13
14
21
55
23
24
31
32
33
34
41
42
5
44
_show;mat--sr
a = array(50,50); read(n); popunaMatrice(a, n,n, 0); ispisMatrice(a, n,n);
minR = 1; minK = 1; maxR = 1; maxK = 1;
for (i=1..n) {
for (j=1..n) {
if (a[i,j] < a[minR,minK]) {
minR = i;
minK = j;
}
if (a[i,j] > a[maxR,maxK]) {
maxR = i;
maxK = j;
}
}
}
for (i=1..n) {
t = a[i,minK];
a[i,minK] = a[maxR,i];
a[maxR,i] = t;
}
write("Dobijena matrica:");
ispisMatrice(a, n,n);
Zadatak D.6
Unosi se matrica A[N,M]. Formirati matricu B[N-1,M-1], koja se dobija
izbacivanjem R-tog reda i K-te kolone iz matrice A.
Ako npr. imamo matricu od 4x5 elemenata i zadato R=2 i K=4, dobija se matrica od 3x4 elemenata:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
1
2
3
5
11
12
13
15
16
17
18
20
_show;mat--sr
a = array(50,50); b = array(50,50); read(n, m); popunaMatrice(a, n,m, 0); write("Matrica A"); ispisMatrice(a, n,m);
read(r,k);
bi = 1;
for (i=1..n) {
bj = 1;
if (i <> r) {
for (j=1..m) {
if (j <> k) {
b[bi,bj] = a[i,j];
bj++;
}
}
bi++;
}
}
write("Matrica B");
ispisMatrice(b, n-1,m-1);
Zadaci za razmišljanje
Ovde ćemo predstaviti par klasičnih zadataka koji služe kao "mozgalice" đacima koji se pripremaju za takmičenja.
Zadatak X.1
Kreirati kvadratnu matricu A od N*N brojeva upisanih po spirali, počev od gornjeg-levog, pa do centralnog elementa.
Drugim rečima, ono što treba da se dobije je sledeća matrica:
1
2
3
4
5
16
17
18
19
6
15
24
25
20
7
14
23
22
21
8
13
12
11
10
9
Ovaj problem se razbija na popunjavanje prsten-po-prsten. Kao što vidimo, krenućemo od spoljnih ivica i popunjavaćemo zasebno
sva četiri smera. U matrici 5x5 elemenata, "spoljni prsten" ima po 4 elementa u svakom "potezu". Pošto je broj elemenata jednak
i u svakom pravcu na neki način ide od 1 do 4, ne moramo da pravimo 4 ciklusa, već ih možemo popuniti u jednom prolazu.
1
2
3
4
5
16
6
15
7
14
8
13
12
11
10
9
Onda popunjavamo sledeći "prsten". Vidimo da se u sva četiri poteza krećemo kroz elemente od 2. do 3. (bilo po horizontali,
bilo po vertikali).
1
2
3
4
5
16
17
18
19
6
15
24
20
7
14
23
22
21
8
13
12
11
10
9
_show;mat--sr
a = array(20,20);
read(n);
pola = n div 2;
a[pola+1,pola+1] = n*n;
br = 1;
for (x=1..pola) {
y = n - x;
d = y-x+1;
for (i=x..y) {
a[x,i] = br;
a[i,y+1] = br + d;
a[y+1,n-i+1] = br + d*2;
a[n-i+1,x] = br + d*3;
br++;
}
br += d*3;
}
write("Matrica");
ispisMatrice(a, n,n);
Zadatak X.2
Unosi se matrica A u obliku niza od N*M elemenata. Izvršiti in-situtransponovanje matrice
(to u stvari znači - bez korišćenja bilo kakve pomoćne matrice ili niza, tj. bez utroška dodatne memorije).
Da razmislimo malo o ovom zadatku. Recimo da imamo početnu matricu od npr. 3 reda i 4 kolone.
Ona bi bila predstavljena ovako:
a1
a2
a3
a4
b1
b2
b3
b4
c1
c2
c3
c4
Mi treba da preraspodelimo elemente da dobijemo matricu od 4 reda i 3 kolone, koja onda kao niz izgleda ovako:
a1
b1
c1
a2
b2
c2
a3
b3
c3
a4
b4
c4
Ovo nije trivijalan problem (bio bi u rangu npr. republičkog takmičenja),
a programeri već decenijama pokušavaju da smisle "bolje" rešenje. Vidite, glavni problem je u premeštanju elemenata.
Neki element X bi trebao da dođe na mesto elementa Y, međutim, oni neće prosto zameniti mesta, jer element Y
onda ide na mesto elementa Z, elemenat Z na mesto nekog četvrtog elementa, i tako sve dok ko-zna-koji element
ne dođe na mesto elementa X. U tom trenutku smo "izvrteli" neke elemente, a neke nismo. Shvatate šta je problem?
Ako onda pređemo na neki sledeći element, kako da znamo da li je on već premešten ili nije?
Evo jedne prostije ideje.
Ovom problemu možemo da pristupimo kao algoritmu za sortiranje niza, gde se vrše stalne preraspodele
elemenata. Tako bismo razrešavali red po red početne matrice, od kraja prema početku. Drugim rečima, naš prvi cilj je:
a1
a2
a3
a4
b1
c1
b2
c2
b3
c3
b4
c4
Kako ćemo to postići? Pa uzimamo elemenat po elemenat reda B i smeštamo ga na odgovarajuće mesto,
dok istovremeno premeštamo ostale elemente (reda C) za po jedno mesto ulevo:
a1
a2
a3
a4
b1
b2
b3
b4
c1
c2
c3
c4
a1
a2
a3
a4
b1
b2
b3
c1
c2
c3
b4
c4
a1
a2
a3
a4
b1
b2
c1
c2
b3
c3
b4
c4
a1
a2
a3
a4
b1
c1
b2
c2
b3
c3
b4
c4
Tako ponavljamo postupak za svaki red dok ne ispremeštamo i elemente prvog reda (u ovom slučaju - red A).
Naravno, ovo nije idealan algoritam, pošto se vrši veliki broj premeštanja elemenata.
Međutim, ovo rešenje u potpunosti zadovoljava zahtev da se ne koristi nikakva pomoćna matrica ili niz,
što bi matematičari rekli, memorijska zahtevnost je O(1) (sa povećanjem veličine matrice uopšte
se ne javlja potreba za dodatnom memorijom).
_show;mat--sr
read(n, m); a = array(n*m); popunaNiza(a, n*m, 0);
function ispis(a, r,k) {
for (i=1..r) {
red = "";
for (j=1..k) {
red += priprema(a[i*k-k + j]) + " ";
}
write(red);
}
}
write("Matrica A");
ispis(a, n,m);
preskok = 1;
start = (n-1) * m;
for (i=2..n) {
poz = n*m-preskok;
for (j=2..m) {
t = a[start];
for (k=start..poz-1) {
a[k] = a[k+1];
}
a[poz] = t;
start--;
poz -= preskok+1;
}
start = (n-i)*m;
preskok++;
}
write("Matrica AT");
ispis(a, m,n);
M. Čabarkapa, N. Spalević (1995): Metodička zbirka zadataka iz programiranja sa rešenjima u Pascal-u, Sova, Beograd
M. Škarić, V. Radović (2009): Uvod u programiranje - Zbirka zadataka iz programskog jezika C, Mikro knjiga, Beograd
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.
