UGNJEŽDENE PETLJE U JEZIKU C++

Sadržaj stranice

Dobrodošli na stranicu posvećenu ugnježdenim petljama u C++! Ova stranica nudi sve ključne informacije, primere koda i praktične savete o radu sa ugnježdenim petljama, koje su od suštinskog značaja za iteraciju kroz složene strukture podataka i višedimenzionalne podatke. Pomoću tabele sadržaja možete brzo preskočiti na interesantne sekcije i pronaći sadržaj koji vas zanima.

Uvod

Ugnježdene petlje predstavljaju petlje unutar drugih petlji. Kada se jedna petlja nalazi unutar tela druge petlje, unutrašnja petlja se izvršava potpuno za svaku iteraciju spoljašnje petlje. Ovakva struktura se koristi kada je potrebno iterirati kroz složene podatke, kao što su matrice, liste lista, ili višedimenzionalni nizovi.

Kako funkcionišu ugnježdene petlje?

Kada se koriste?

Ugnježdene petlje su korisne u sledećim situacijama:
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

Osnovna struktura ugnježdenih petlji


Ugnježdene petlje su strukture u kojima se jedna petlja nalazi unutar druge. Ovaj koncept omogućava iteraciju kroz višedimenzionalne strukture podataka, kao što su matrice, gde spoljna petlja upravlja redovima, a unutrašnja petlja upravlja kolonama.

Ključni elementi ove strukture su:

  • Inicijalizacija i uslov spoljne petlje za iteraciju kroz redove.
  • Inicijalizacija i uslov unutrašnje petlje za iteraciju kroz kolone svakog reda.
  • Obrada svakog elementa u matrici unutar tela unutrašnje petlje.

Razmotrite sledeći primer u C++ koji ilustruje osnovnu strukturu ugnježdenih petlji: 

for (int i = 0; i < broj_redova; i++) {
    for (int j = 0; j < broj_kolona; j++) {
        // Obrada elementa na poziciji [i][j]std::cout << matrica[i][j] << " ";
    }
    std::cout << std::endl;
}

U ovom primeru, spoljna petlja kontroliše redove matrice, dok unutrašnja petlja iterira kroz kolone svakog reda. Ovakav pristup omogućava sistematsku obradu svakog elementa u dvodimenzionalnoj strukturi.

Napomene:

  • Vodite računa o ispravnoj inicijalizaciji i uslovima za petlje kako biste izbegli beskonačne iteracije.
  • U slučaju višedimenzionalnih struktura, prevelika dubina ugnježdenih petlji može otežati čitljivost koda i uticati na performanse.
  • Razmotrite korišćenje funkcija ili modularizaciju koda za kompleksnije operacije kako bi kod ostao pregledan.

Primeri ugnježdenih petlji

Primer 1: Ispisivanje po redovima i kolonama

Zadatak: 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 cout naredbu: 

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++)
{
cout << broj << " ";
}
cout << endl;
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;
cout << broj << " ";
}
cout << endl;
}

Primer 2: Generisanje Tablice Množenja

Zadatak: Napisati program koji će na ekranu ispisati tablicu množenjaObjaš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 <iostream>
using namespace std;

// Program za generisanje tablice množenja
int main() {
int n = 10; // Velicina tablice mnozenja

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cout<< i << "*" << j << "=" << i * j << "\t";
}
cout << endl;
}

return 0;
}

Testirajte svoj kod u editoru ispod!

// Ovde pišite C++ kod...

​Primer 3 a): Crtanje Obrasca Zvezdica

Kod za crtanje trougla zvezdica koristi ugnježdene petlje gde unutrašnja petlja određuje broj zvezdica po redu.
#include <iostream>
using namespace std;

// Program za crtanje trougla zvezdica
int main() {
int n = 5; // Visina trougla

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
cout << "*";
}
cout << endl;
}

return 0;
}
Izlaz:
*
**
***
****
*****

Objašnjenje rešenja:

​Primer 3 b): Crtanje Obrasca Zvezdica u obliku pravouglog trougla sa temenom na dole

Napisati kod koji iscrtava trougao za unetu vrednost dimenzije n  kao što je prikazano u primeru ulaza i izlaza ispod:

Ulaz:

Unesite broj n
5

Izlaz:

 *****  
  ****  
   ***  
    **  
     *

​​Primer 4: Prolazak kroz Dvodimenzionalni Niz

Zadatak: 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 dimenziju 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
​Kod za ispis elemenata dvodimenzionalnog niza pokazuje primenu ugnježdenih petlji za obradu matrica.
#include <iostream>
using namespace std;

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

for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
cout << matrica[i][j] << " ";
}
cout << endl;
}

return 0;
}

Objašnjenje koda

​​​Objašnjenje Složenijih Scenarija Korišćenja Ugnježdenih Petlji

1. Iteracija Kroz Dvodimenzionalne Nizove

​Jedan od najčešćih scenarija za korišćenje ugnježdenih petlji je rad sa dvodimenzionalnim nizovima (matricama). Dvodimenzionalni niz se može zamisliti kao tabela sa redovima i kolonama. Svaka vrednost u tabeli može se posetiti pomoću dva indeksa: jedan za redove i drugi za kolone.
#include <iostream>
using namespace std;

int main() {
const int rows = 3, cols = 3;
int matrix[rows][cols] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};

cout << "Ispis dvodimenzionalnog niza:" << endl;

for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
cout << matrix[i][j] << " ";
}
cout << endl;
}

return 0;
}
​Ovaj program koristi dve petlje: spoljašnja petlja prolazi kroz redove, a unutrašnja petlja kroz kolone matrice. Ovo omogućava pristup svakom elementu dvodimenzionalnog niza.

2. Implementacija Algoritama sa Više Nivoa Petlji

#include <iostream>
using namespace std;

// Funkcija main gde se implementira Bubble Sort algoritam
int main() {
// Definišemo niz koji ćemo sortirati
int arr[] = {5, 2, 9, 1, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);

// Prikazujemo originalni niz pre sortiranja
cout << "Originalni niz: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;

// Bubble Sort algoritam
for (int i = 0; i < n - 1; i++) {
// Unutrašnja petlja poredi susedne elemente
for (int j = 0; j < n - i - 1; j++) {
// Ako je trenutni element veći od sledećeg, zameni ih
if (arr[j] > arr[j + 1]) {
int temp = arr[j]; // Privremeno čuvamo vrednost trenutnog elementa
arr[j] = arr[j + 1]; // Trenutni element postaje sledeći
arr[j + 1] = temp; // Sledeći element postaje prethodni
}
}
}

// Prikazujemo sortirani niz
cout << "Sortirani niz: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;

// Vraćamo 0 jer je program uspešno izvršen
return 0;
}
Ovaj kod implementira Bubble Sort algoritam koristeći ugnježdene petlje:

​​​​Upozorenja o Potencijalnim Greškama kod Ugnježdenih Petlji

​Kod rada sa ugnježdenim petljama, često se javljaju greške koje mogu izazvati neispravnost programa ili dovesti do neočekivanih rezultata. Ovde su istaknute najčešće greške i saveti kako ih izbeći:

1. Beskonačne Petlje

​Ako petlja nema ispravan uslov završetka, može se izvršavati beskonačno, što će zaustaviti dalji rad programa.Uobičajeni uzrok:

Primer greške

for (int i = 0; i < 5; /* Zaboravljena inkrementacija i++ */) {
cout << i << endl;
}

Rešenje:

​Proveriti da se kontrolna promenljiva pravilno menja unutar svake iteracije
for (int i = 0; i < 5; i++) {
cout << i << endl;
}

2. Nepravilno Inicijalizovane Promenljive

Ako promenljiva koja kontroliše petlju nije pravilno inicijalizovana, može izazvati neočekivane rezultate.

Primer greške

int j;
for (int i = 0; i < 3; i++) {
j += i; // Promenljiva 'j' nije inicijalizovana
}

Rešenje: 

Inicijalizovati promenljive pre njihove upotrebe:

int j = 0;
for (int i = 0; i < 3; i++) {
j += i;
}

3. Nepotrebno Velik Broj Iteracija

​Kada su uslovi za iteraciju pogrešno definisani, petlja može izvršiti više iteracija nego što je potrebno, što značajno usporava program.

Primer greške:

for (int i = 0; i < 1000; i++) {
for (int j = 0; j < 1000; j++) {
cout << i * j << endl;
}
}

Rešenje:

Proveriti uslove i optimizovati iteracije, koristeći samo one koje su neophodne.

4. Zavisnost Kontrolnih Promenljivih

​Kada jedna petlja koristi kontrolnu promenljivu druge petlje, može doći do nepredvidivog ponašanja.

Primer greške:

for (int i = 0; i < 5; i++) {
for (int j = 0; j < i; j++) {
i++; // 'i' se menja unutar unutrašnje petlje
}
}

Rešenje:

​Održavati nezavisnost kontrolnih promenljivih.

5. Prekid Izvršenja (Break Statement)

​Nepravilno korišćenje break može uzrokovati neočekivan prekid izvršenja unutrašnje petlje.

Primer greške:

for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (j == 1) break;
cout << j << endl;
}
}

Rešenje:

​Proveriti logiku uslova za prekid izvršenja.Više primera iz ove oblasti možete naći na web strani: Ugnježdene petlje u C/C++ primeri

Napredne primene ugnježdenih petlji u jeziku C++


Ugnježdene petlje u algoritmima sortiranja


Ugnježdene petlje se često koriste u algoritmima sortiranja, kao što je Bubble Sort. 


#include<iostream>void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main() {
    int niz[] = {5, 3, 8, 4, 2};
    int n = sizeof(niz) / sizeof(niz[0]);
    
    bubbleSort(niz, n);
    
    std::cout << "Sortirani niz: ";
    for (int i = 0; i < n; i++) {
        std::cout << niz[i] << " ";
    }
    std::cout << "\n";
    
    return 0;
}

Pronalaženje trojki brojeva sa zadatim zbirom

Ugnježdene petlje se često koriste u kombinatoričkim problemima. Sledeći primer pronalazi sve trojke brojeva u nizu čiji zbir daje zadatu vrednost. 


#include<iostream>void findTriplets(int arr[], int n, int target) {
    for (int i = 0; i < n - 2; i++) {
        for (int j = i + 1; j < n - 1; j++) {
            for (int k = j + 1; k < n; k++) {
                if (arr[i] + arr[j] + arr[k] == target) {
                    std::cout << "Trojka: " << arr[i] << ", " << arr[j] << ", " << arr[k] << "\n";
                }
            }
        }
    }
}

int main() {
    int niz[] = {1, 4, 6, 8, 3, 7};
    int target = 15;
    int n = sizeof(niz) / sizeof(niz[0]);
    
    findTriplets(niz, n, target);
    
    return 0;
}

Zaključak

Ugnježdene petlje omogućavaju rešavanje kompleksnih problema kao što su sortiranje i kombinatorički zadaci. Efikasnost algoritma zavisi od broja iteracija, te je važno razmotriti optimizacije pri radu sa velikim skupovima podataka.

Objašnjenje koda


Ovaj kod pretražuje sve moguće kombinacije trojki iz niza i proverava da li njihov zbir odgovara zadatoj vrednosti.


Prva petlja (i od 0 do n-2)

Postavlja prvi broj trojke.


Druga petlja (j od i + 1 do n-1)

Postavlja drugi broj trojke.


Treća petlja (k od j + 1 do n)

Postavlja treći broj trojke.


Provera uslova (arr[i] + arr[j] + arr[k] == targetSum)

Ako je zbir brojeva jednak targetSum, trojka se ispisuje.


Primer rada sa nizom

Niz: [1, 5, 3, 7, 2, 4, 6], targetSum = 12


Moguće trojke koje daju zbir 12 su:

  • (1, 5, 6)
  • (1, 4, 7)
  • (3, 4, 5)

Vezanost za kombinatoriku


Ovaj problem spada u kombinatoričke probleme jer zahteva ispitivanje svih mogućih kombinacija od tri elementa iz skupa.


Broj mogućih kombinacija

Ako imamo n elemenata, broj načina da izaberemo tri elementa (bez obzira na redosled) može se izračunati pomoću kombinatornog koeficijenta:

C(n, 3) = n! / (3!(n − 3)!) = n(n − 1)(n − 2) / 6


U kodu

Trostruka petlja prolazi kroz sve moguće kombinacije, što rezultuje vremenskom složenošću O(n³).


Optimizacija problema

Sortiranje + Dva Pokazivača (Two Pointers metoda) – O(n²)
Može se poboljšati tako što se niz prvo sortira, a zatim koristi metoda sa dva pokazivača umesto treće petlje.

Hash Map metoda – O(n²)
Umesto treće petlje možemo koristiti heš tabelu za bržu proveru razlike targetSum - (arr[i] + arr[j]).


Zaključak

Ovaj primer pokazuje kako se ugnježdene petlje koriste u kombinatoričkim problemima. Iako je ovaj pristup jednostavan, može biti neefikasan za velike nizove. Optimizacije kao što su "Two Pointers" metoda ili korišćenje heš tabele mogu poboljšati performanse.

U sledećem primeru optimizovane verzije koda za pronalaženje trojki koje sumiraju na zadati broj, koristi se tehnika sortiranja i dvoje pokazivača kako bi se postigla bolja efikasnost u poređenju sa tri ugnježdene petlje.

#include <iostream>#include <algorithm>// Za funkciju sort()void findTriplets(int arr[], int n, int targetSum) {
            // Prvo sortiramo nizstd::sort(arr, arr + n);

            for (int i = 0; i < n - 2; i++) {
                // Ako je trenutni element isti kao prethodni, preskočimo ga da bismo izbegli duplikateif (i > 0 && arr[i] == arr[i - 1]) {
                    continue;
                }

                int left = i + 1; // Početni pokazivačint right = n - 1; // Krajnji pokazivačwhile (left < right) {
                    int sum = arr[i] + arr[left] + arr[right];

                    if (sum == targetSum) { // Ako je zbir jednak ciljanom broju, ispisujemo trojkustd::cout << "Trojka: (" << arr[i] << ", " << arr[left] << ", " << arr[right] << ")\n";
                        left++;
                        right--;

                        // Preskačemo duplikatewhile (left < right && arr[left] == arr[left - 1]) left++;
                        while (left < right && arr[right] == arr[right + 1]) right--;
                    }
                    else if (sum < targetSum) { // Ako je zbir manji od ciljanog, pomeramo levi pokazivač
                        left++;
                    }
                    else { // Ako je zbir veći, pomeramo desni pokazivač
                        right--;
                    }
                }
            }
        }

        int main() {
            int arr[] = {1, 5, 3, 7, 2, 4, 6};
            int n = sizeof(arr) / sizeof(arr[0]);
            int targetSum = 12;

            findTriplets(arr, n, targetSum);

            return 0;
        }

Objašnjenje optimizovanog koda:

  • Sortiranje niza: Prvo sortiramo niz, što omogućava korišćenje dvoje pokazivača.
  • Preskakanje duplikata: Ako je trenutni element jednak prethodnom, preskačemo ga da bismo izbegli duplikate u ispisu.
  • Two-pointer tehnika: Nakon što odaberemo prvi element trojke, postavljamo dva pokazivača, jedan na sledeći element, a drugi na poslednji. Zatim, pomeramo pokazivače na osnovu zbiranja brojeva u odnosu na ciljani zbir.
  • Vremenska složenost: Ova optimizacija smanjuje složenost sa \(O(n^3)\) na \(O(n^2)\), što značajno poboljšava efikasnost za veće nizove.

Ova optimizovana verzija je znatno brža za veće nizove, jer koristi sortiranje i dvoje pokazivača kako bi smanjila broj provera.

​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