Programski jezici → C++ → Ugnježdene petlje

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?

• Spoljašnja petlja započinje prvu iteraciju.
• Kada spoljašnja petlja uđe u telo, unutrašnja petlja se pokreće i završava sve svoje iteracije.
• Nakon završetka unutrašnje petlje, kontrola se vraća na spoljašnju petlju, koja prelazi na sledeću iteraciju.
• Ovaj proces se ponavlja dok spoljašnja petlja ne završi sve svoje iteracije.

Kada se koriste?

Ugnježdene petlje su korisne u sledećim situacijama:

• Iteracija kroz dvodimenzionalne strukture podataka, poput matrica.
• Generisanje obrazaca ili tablica.
• Implementacija algoritama, kao što su sortiranje ili pretraga u strukturama podataka.
• Obrada višedimenzionalnih podataka u igrama, grafici, ili simulacijama.

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ž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 <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!

Unesite podatke za program:

Run Code

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

• 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.
  

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

• 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.
  

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:

• Spoljašnja petlja ponavlja proces sortiranja za svaki element.
• Unutrašnja petlja poredi susedne elemente i menja im mesta ako nisu u ispravnom redosledu.

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:

• Zaboravljena promena vrednosti kontrolne promenljive.
• Pogrešno definisani uslovi za izlazak iz petlje.

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 niz
    std::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 duplikate
        if (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 trojku
                std::cout << "Trojka: (" << arr[i] << ", " << arr[left] << ", " << arr[right] << ")\n";
                left++;
                right--;

                // Preskačemo duplikate
                while (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.

Srodni članci

Petlje u c/c++ programskom jeziku-primeri

Petlje u programskom jeziku JAVA

Nizovi-primeri

Fibonačijev niz

Podaci u C/C++ jeziku

Proveri znanje