Web Analytics Made Easy - Statcounter
SVET PROGRAMIRANJA

UGNJEŽDENE PETLJE U JEZIKU C

​Ugnježdene petlje su petlje koje se nalaze unutar drugih petlji, omogućavajući višestruko ponavljanje skupa naredbi. Ova struktura je ključna za rešavanje problema koji zahtevaju iteraciju kroz složene podatke, poput dvodimenzionalnih nizova ili matrica.

​Kako funkcionišu ugnježdene petlje?

Kada se koristi ugnježdena petlja, unutrašnja petlja se izvršava u potpunosti za svaku iteraciju spoljašnje petlje. Na primer, u slučaju dvostruke ugnježdene petlje:
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// Kod koji se izvršava za svaku kombinaciju i, j
}
}
  • Spoljašnja petlja upravlja glavnim brojem iteracija (i u ovom slučaju).
  • Unutrašnja petlja izvršava svoj kod za svaku vrednost j, dok se vrednost i ne promeni.
Ova kombinacija omogućava da se iterira kroz strukture podataka sa više dimenzija, kao što su tabele, matrice ili liste unutar lista.
Kada koristiti ugnježdene petlje?Ugnježdene petlje se koriste kada postoji potreba za iteracijom kroz:
  • Dvodimenzionalne nizove (matrice).
  • Strukture podataka koje imaju hijerarhijsku organizaciju.
  • Algoritme za crtanje obrazaca, poput piramida ili dijamanata.
  • Algoritme sortiranja i pretraživanja, poput algoritma za pretragu kroz grafove.
Petlje ili ciklusi su naredbe čija je uloga da neku, ili više drugih naredbi ponavljaju određen broj puta. Te naredbe koje se ponavljaju se pišu u telu for petlje. To može biti bilo koja druga naredba, pa samim tim i nova for naredba.
​Posmatrajmo sada sledeći zadatak

Primer 1: Ispisati prvih 100 prirodnih brojeva u 10 redova i 10 kolona.

Ovaj zadatak može da se uradi i bez ugnježdenih petlji. Vidi primer na Petlje u C/C++ primeri
​Međutim, mi ćemo pokazati ovde kako se isti primer može uraditi upotrebom ugnježdenih petlji.
​
Za ispisivanje jednog broja koristimo printf naredbu: 

printf("%2d",broj);
u jeziku c++
cout << broj << " ";
Za ispisivanje jednog reda koristimo for petlju u kojoj ćemo kontrolnu promenljivu označiti slovom j i to će predstavljati i redni broj kolone matrice koju treba ispisati:
for(int j=1; j<=10; j++)
{
printf("%4d",broj);
}
printf("/n");
Ovo će ispisati 1 red. Ovo sada treba ponoviti 10 puta, za svaki red. Za to ćemo koristiti još jednu petlju, tako da prethodne naredbe budu u telu te petlje, tj između vitičastih zagrada. Kontrolna promenljiva spoljašnje petlje koju ćemo označiti sa i biće broj reda umanjena za 1, tako da se menja od 0 do 9.
Promenljiva broj treba da bude povezan kako sa j tako i sa i na sledeći način:
broj =10 * i + j;
Kada se ispisuje prvi red, i=0, pa se ispisuju brojevi koji samo zavise od tekuće kolone j, tako da  se u 1. koloni ispisuje 1, u 2. koloni 2 itd.
U sledećem redu se ispisuju vrednosti koje su veće od vrednosti prethodnog reda za 1*10, tako da dobijemo redom 11,12,13,....
​U svakom sledećem  redu brojevi su za 10 veći nego u prethodnom. 
int broj;
for(int i=0; i<10; i++)
{
for(int j=1; j<=10; j++)
{
broj=10*i+j;
printf("%4d",broj);
}
printf("/n");
}

​​Primer 2: Generisanje Tablice Množenja

Zadatak: Napisati program koji će na ekranu ispisati tablicu množenja
Objašnjenje: 
​Kod za generisanje tablice množenja koristi ugnježdene petlje gde spoljašnja petlja iterira kroz redove, a unutrašnja petlja kroz kolone.
#include <stdio.h>

int main() {
int i, j;

for (i = 1; i <= 10; i++) {
for (j = 1; j <= 10; j++) {
printf("%d*%d=%d\t", i, j, i * j);
}
printf("\n");
}

return 0;
}

​​Primer 3: Crtanje Obrasca Zvezdica

Napišite program u C/C++ jeziku koji koristi ugnježdene petlje za crtanje obrasca zvezdica. Obrazac treba da bude u formi trougla, sa zvezdama koje se postepeno povećavaju sa svakim redom. Na primer, za broj redova n, program treba da prikaže sledeći obrazac:
​*
**
***
****
*****

Rešenje: 

  • Prvi korak: Počnite sa definisanjem broja redova u obrascu. U ovom zadatku, broj redova (n) treba da bude unet od strane korisnika.
  • Drugi korak: Koristite spoljnu petlju (for) za iteraciju kroz redove. Broj redova treba da bude jednak unetoj vrednosti n.
  • Treći korak: Za svaki red, unutar spoljne petlje, koristite unutrašnju petlju koja će štampati odgovarajući broj zvezdica. U svakom sledećem redu, broj zvezdica treba da bude jedan veći nego u prethodnom.
  • Četvrti korak: Nakon što unutrašnja petlja završi, pređite na sledeći red i ponovite proces.
Kod za crtanje trougla zvezdica koristi ugnježdene petlje gde unutrašnja petlja određuje broj zvezdica po redu.
#include <stdio.h>

int main() {
// Broj redova u obrazcu
int n = 5;

for (int i = 1; i <= n; i++) {
// Ispisuje zvezdice u svakom redu
for (int j = 1; j <= i; j++) {
printf("*");
}
// Novi red nakon svake iteracije spoljašnje petlje
printf("\n");
}

return 0;
}

Objašnjenje kompleksnijih scenarija

​Iako ugnježdene petlje mogu biti veoma korisne, često dovode do problema sa performansama, posebno kada se koriste u velikim petljama ili u kontekstu velikih nizova. Postoje različite tehnike za optimizaciju ovih petlji, kao što su loop unrolling (razvijanje petlje) i loop fusion (spajanje petlji).

1. Ugnježdene petlje sa višedimenzionalnim nizovima (matricama)​

​Višedimenzionalni nizovi, kao što su matrice, predstavljaju jedan od najčešćih slučajeva u kojima se koriste ugnježdene petlje. Matrica je zapravo niz nizova, pa da bismo pristupili svakom elementu matrice, potrebno je da koristimo dve petlje: spoljašnju i unutrašnju.

​​Primer 4: Prolazak kroz Dvodimenzionalni Niz

Napišite program u C jeziku koji koristi ugnježdene petlje za prolazak kroz dvodimenzionalni niz. Program treba da unese dimenzije niza (broj redova i broj kolona), a zatim da popuni niz sa vrednostima koje unosi korisnik. Na kraju, program treba da prikaže sadržaj niza.
Primer za niz dimenzija 3x3:
Unesite broj redova: 3
Unesite broj kolona: 3
Unesite elemente matrice:
1 2 3
4 5 6
7 8 9
Elementi matrice su:
1 2 3
4 5 6
7 8 9

Rešenje:

​Razmotrimo matricu dimenzija m x n (m redova i n kolona). Da bismo pristupili svakom elementu matrice i obradili ga (npr. ispisali vrednosti), koristićemo dve ugnježdene petlje: spoljašnju koja prolazi kroz redove i unutrašnju koja prolazi kroz kolone.
​Kod za ispis elemenata dvodimenzionalnog niza pokazuje primenu ugnježdenih petlji za obradu matrica.
#include <stdio.h>

// Program za prolazak kroz dvodimenzionalni niz
int main() {
int n = 3, m = 3;
int niz[n][m] = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
printf("%d ", niz[i][j]);
}
printf("\n");
}

return 0;
}

Objašnjenje rešenja

  • Unos dimenzija matrice: Program prvo traži od korisnika da unese broj redova n i broj kolona m.
  • Kreiranje matrice: Kreira se dvodimenzionalni niz matrica[n][m], gde n predstavlja broj redova, a m broj kolona.
  • Unos elemenata: Dve ugnježdene petlje se koriste za unos elemenata matrice. Spoljašnja petlja iterira kroz redove, dok unutrašnja petlja unosi vrednosti za svaki element u tom redu.
  • Ispis matrice: Još jedna ugnježdena petlja se koristi za ispis elemenata matrice. Unutrašnja petlja ispisuje vrednosti u jednom redu, dok spoljašnja petlja prelazi na sledeći red.
Više primera iz ove oblasti možete naći na web strani: Ugnježdene petlje u C/C++ primeri

2. Optimizacija ugnježdenih petlji​

Iako ugnježdene petlje mogu biti veoma korisne, često dovode do problema sa performansama, posebno kada se koriste u velikim petljama ili u kontekstu velikih nizova. Postoje različite tehnike za optimizaciju ovih petlji, kao što su loop unrolling (razvijanje petlje) i loop fusion (spajanje petlji).

2.1 Loop Unrolling (Razvijanje petlje)

​Loop unrolling je tehnika koja se koristi da bi se smanjio broj iteracija u petlji, tako što se unutrašnja petlja "razvija" tako da obavlja više operacija po iteraciji. Ovo može poboljšati performanse smanjenjem broja operacija sa skokom (jump) i povećanjem lokalnosti podataka u kešu.

Primer bez unrollinga:

for (int i = 0; i < 8; i++) {
a[i] = b[i] + c[i];
}

​Primer sa unrollingom:

U kontekstu optimizacije, kada pominjemo "loop unrolling" (razvijanje petlje), radi se o tehnici gde se rad jedne petlje "razvija" tako da obavlja više operacija po iteraciji, čime se smanjuje broj iteracija. U ovom kodu to je ostvareno ovako:
  • Umesto da prolazi kroz svaki indeks i (kao u jednostavnoj petlji for (int i = 0; i < 8; i++)), petlja se kreće u koracima od 2 (i += 2), dok telo petlje obrađuje dva elementa a[i] i a[i + 1] u istoj iteraciji.
for (int k = 0; k < n; k++) { // Spoljašnja petlja
for (int i = 0; i < 8; i += 2) { // Unutrašnja petlja
a[i] = b[i] + c[i];
a[i + 1] = b[i + 1] + c[i + 1];
}
}
​U ovom slučaju, spoljašnja petlja (for (int k = 0; k < n; k++)) obavlja više prolaza kroz celokupni proces unutar unutrašnje petlje. Kod bez spoljašnje petlje obavlja optimizaciju samo jedne operacije.

​ 2.2 Loop Fusion (Spajanje petlji)

Loop fusion je tehnika koja se koristi kada imamo više petlji koje prolaze kroz iste podatke, pa ih možemo spojiti u jednu petlju. Ovo može poboljšati efikasnost smanjenjem broja petlji i omogućavanjem bolju lokalnost podataka.
​Posmatrajmo sledeći primer:
#include <stdio.h>

int main() {
const int rows = 2; // Broj redova
const int cols = 8; // Broj kolona

int a[cols], b[cols], c[cols], d[cols], e[cols], f[cols];

// Inicijalizacija matrica za primer
for (int i = 0; i < cols; i++) {
b[i] = i + 1; // Primer vrednosti za b
c[i] = i + 2; // Primer vrednosti za c
e[i] = i + 3; // Primer vrednosti za e
f[i] = i + 4; // Primer vrednosti za f
}

// Ugnježdena struktura
for (int i = 0; i < rows; i++) { // Spoljašnja petlja za redove
for (int j = 0; j < cols; j++) { // Unutrašnja petlja za kolone
if (i == 0) { // Prvi red (odgovara \"Prvoj petlji\")
a[j] = b[j] + c[j];
} else if (i == 1) { // Drugi red (odgovara \"Drugoj petlji\")
d[j] = e[j] + f[j];
}
}
}

// Ispis rezultata
printf("Rezultati za prvi red (a[i] = b[i] + c[i]):\n");
for (int i = 0; i < cols; i++) {
printf("a[%d] = %d\n", i, a[i]);
}

printf("\nRezultati za drugi red (d[i] = e[i] + f[i]):\n");
for (int i = 0; i < cols; i++) {
printf("d[%d] = %d\n", i, d[i]);
}

return 0;
}
Objašnjenje:
  1. #include <stdio.h>
    Koristi se za uključivanje standardne biblioteke za unos i ispis u C jeziku.
  2. Deklaracija konstanti:
    • rows označava broj redova (2 u ovom slučaju).
    • cols označava broj kolona (8 u ovom slučaju).
  3. Inicijalizacija nizova:
    Kreiraju se nizovi b, c, e, i f sa vrednostima koje se generišu u for petlji.
  4. Ugnježdene petlje:
    • Spoljašnja petlja (for (int i = 0; i < rows; i++)) iterira kroz redove.
    • Unutrašnja petlja (for (int j = 0; j < cols; j++)) iterira kroz kolone svakog reda.
    • U prvom redu, vrednosti niza a se izračunavaju kao a[j] = b[j] + c[j].
    • U drugom redu, vrednosti niza d se izračunavaju kao d[j] = e[j] + f[j].
  5. Ispis rezultata:
    Koristi se funkcija printf za prikaz rezultata na standardnom izlazu:
    • Prvo se ispisuju vrednosti niza a.
    • Zatim se ispisuju vrednosti niza d.
Analizirajmo sada unutrašnju for petlju koja je u ovom primeru bez fusion(spajanja):
// Prva petlja
for (int i = 0; i < 8; i++) {
a[i] = b[i] + c[i];
}

// Druga petlja
for (int i = 0; i < 8; i++) {
d[i] = e[i] + f[i];
}
Ako bi brimenili spajanje, unutrašnja for petlja bi bila:
for (int i = 0; i < 8; i++) {
a[i] = b[i] + c[i];
d[i] = e[i] + f[i];
}
​U ovom primeru, dve petlje su spojene u jednu, što smanjuje broj prolaza kroz podatke i može poboljšati performanse.

2.3 Korišćenje optimizacija kompilatora

Mnogi moderni kompilatori imaju ugrađene optimizacije, kao što su automatski loop unrolling i loop fusion. Ove optimizacije mogu se omogućiti pomoću kompilatorskih opcija (npr. -O2 ili -O3 za optimizaciju u GCC-u).

Zaključak

  • Ugnježdene petlje su nezamenjiv alat kada radimo sa višedimenzionalnim nizovima ili matricama, ali mogu biti i problematične za performanse.
  • Tehnike loop unrolling i loop fusion mogu značajno poboljšati performanse koda smanjenjem broja petlji i povećanjem efikasnosti procesora.
  • Pravilno razumevanje i implementacija ovih tehnika može dovesti do značajnih poboljšanja u brzini izvođenja programa.

​Prikazivanje problema sa ugnježdenim petljama:

Problemi sa performansama
​Ugnježdene petlje su moćan alat za iteraciju kroz višedimenzionalne strukture podataka, ali mogu postati vrlo neefikasne kada se koriste na velikim skupovima podataka. Glavni problem je kvadratna vremenska složenost (ili čak veća), koja može značajno usporiti izvršenje programa.

Primer kvadratne složenosti:

for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// Operacija koja se izvršava n*n puta
cout << i << ", " << j << "\\n";
}
}
​Ova struktura ima vremensku složenost O(n²). Ako je n veliki (npr. 10,000), broj iteracija može biti ogroman (100 miliona).

Realni primer problema:

  • Obrada slike (n x m piksela): Svaki piksel se obrađuje, što zahteva dvostruku iteraciju.
  • Pretraga parova u velikim datasetovima: Kada se za svaki element porede svi ostali elementi.

​Saveti za optimizaciju ugnježdenih petlji

1. Izbegavanje nepotrebnih iteracija:

​Preispitajte da li sve iteracije u unutrašnjoj petlji zaista moraju da se izvrše. Na primer, umesto:
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i < j) {
cout << i << ", " << j << "\\n";
}
}
}
​optimizujte tako da unutrašnja petlja započne od i + 1:
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
cout << i << ", " << j << "\\n";
}
}
​Ovo smanjuje broj iteracija skoro za polovinu.

2. Korišćenje algoritama sa nižom složenošću:

​Kada je moguće, zamenite dvostruke ili višestruke petlje efikasnijim algoritmima. Na primer, sortiranje može eliminisati potrebu za dvostrukim poređenjem.

3. Loop unrolling (razmotavanje petlji):

​Ako je broj iteracija poznat i mali, petlje se mogu "razmotati" da bi se smanjila režija ponavljanja:
for (int i = 0; i < n; i += 2) {
a[i] = b[i] + c[i];
a[i + 1] = b[i + 1] + c[i + 1];
}
​Ovo smanjuje broj iteracija spoljašnje petlje za polovinu.

4. Korišćenje paralelizacije:

​Podelite iteracije među više procesora ili jezgara. Biblioteke kao što su OpenMP u C++ omogućavaju lako dodavanje paralelizacije:
#pragma omp parallel for
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
a[i][j] = b[i][j] + c[i][j];
}
}

5. Smanjenje broja poziva funkcija unutar petlji:

​Premestite funkcije ili operacije koje ne zavise od unutrašnjih parametara izvan petlje: Pre:
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
result = someFunction(i) + anotherFunction(j);
}
}
Posle:
for (int i = 0; i < n; i++) {
int precomputed = someFunction(i);
for (int j = 0; j < n; j++) {
result = precomputed + anotherFunction(j);
}
}

6. Profilisanje i analiza:

​Koristite alate za profilisanje (npr. gprof, Valgrind, ili Visual Studio Profiler) kako biste identifikovali kritične delove koda i optimizovali samo ono što je potrebno.

Zaključak:

Razumevanje i pažljiva upotreba ugnježdenih petlji je ključ za pisanje efikasnog koda. Optimizacija petlji kroz tehnike kao što su razmotavanje, paralelizacija, i preispitivanje algoritama može značajno unaprediti performanse, posebno u aplikacijama koje rade sa velikim datasetovima ili višedimenzionalnim strukturama podataka.

Dodatni resursi:

​Prethodno
​|< Petlje u jeziku C
Sledeće
​​Nizovi u jeziku C >|

Srodni članci

​Petlje u c/c++ programskom jeziku-primeri
Petlje u programskom jeziku JAVA
Nizovi-primeri
Fibonačijev niz
Podaci u C/C++ jeziku
Algoritmi
Matrice
Java
Linkovi
​Politika Privatnosti
Kontakt

© 2025 by Slobodan svetprogramiranja.com

Sva prava zadržana
SVET PROGRAMIRANJA