Programski jezici → C → Ugnježdene petlje u jeziku C

Ugnježdene petlje u jeziku C

Kako radi petlja u petlji

Ako spoljašnja petlja ima n prolaza, a unutrašnja m, telo unutrašnje petlje izvrši se n · m puta. Promenljiva spoljašnje petlje (i) menja se sporo – kao kazaljka za sate, a unutrašnja (j) brzo – kao kazaljka za minute.

#include <stdio.h>

int main(void) {
    /* spoljašnja petlja: i = 1, 2, 3 */
    for (int i = 1; i <= 3; i++) {
        /* unutrašnja petlja: za svako i, j ide od 1 do 2 */
        for (int j = 1; j <= 2; j++) {
            printf("i=%d j=%d\n", i, j);
        }
    }
    return 0;
}

Ispis ima 3 · 2 = 6 redova. Uoči da se j svaki put ponovo kreće od 1, jer se unutrašnja petlja svaki put pokreće iz početka.

Primer 1: brojevi od 1 do 100 u 10 redova

Spoljašnja petlja broji redove, unutrašnja kolone. Broj u redu i i koloni j je (i − 1) · 10 + j. Posle svakog reda ispisuje se prelazak u novi red \n.

#include <stdio.h>

int main(void) {
    for (int i = 1; i <= 10; i++) {          /* red */
        for (int j = 1; j <= 10; j++) {      /* kolona */
            int broj = (i - 1) * 10 + j;
            printf("%4d", broj);             /* svaki broj zauzima 4 mesta */
        }
        printf("\n");                        /* kraj reda */
    }
    return 0;
}

Format %4d poravnava brojeve u kolone. Isti zadatak može i jednom petljom (novi red posle svakog desetog broja) – vidi Petlje u C/C++ – primeri.

Tablica množenja dobija se istim kosturom – u preseku reda i i kolone j je i * j:

#include <stdio.h>

int main(void) {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            printf("%4d", i * j);
        printf("\n");
    }
    return 0;
}

Primer 2: šare od zvezdica

Kod šara je ključno pitanje: koliko znakova ima red i? Unutrašnja petlja zavisi od i.

#include <stdio.h>

int main(void) {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        /* razmaci ispred zvezdica */
        for (int j = 1; j <= n - i; j++)
            printf(" ");
        /* zvezdice: 1, 3, 5, ... */
        for (int j = 1; j <= 2 * i - 1; j++)
            printf("*");
        printf("\n");
    }
    return 0;
}

U jednom redu mogu biti i dve unutrašnje petlje jedna za drugom – prva za razmake, druga za zvezdice.

Primer 3: svi parovi brojeva

Mnogi zadaci traže proveru svakog para elemenata. Da se par ne broji dva puta (1+4 i 4+1), unutrašnja petlja kreće od i + 1:

#include <stdio.h>

int main(void) {
    int n, k, a[100];
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);

    int broj = 0;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)      /* samo parovi i < j */
            if (a[i] + a[j] == k) {
                printf("%d + %d\n", a[i], a[j]);
                broj++;
            }
    printf("Ukupno parova: %d\n", broj);
    return 0;
}

Ovakvih parova ima n·(n−1)/2. Za n = 1000 to je oko pola miliona provera – brzo. Za n = 100 000 već je 5 milijardi, pa na takmičenjima treba bolji algoritam (npr. tehnika dva pokazivača).

Prekid unutrašnje petlje: prosti brojevi

Naredba break prekida samo petlju u kojoj se nalazi – unutrašnju. Spoljašnja nastavlja sa sledećim brojem.

#include <stdio.h>

int main(void) {
    int n;
    scanf("%d", &n);
    for (int x = 2; x <= n; x++) {           /* svaki kandidat */
        int prost = 1;
        for (int d = 2; d * d <= x; d++) {   /* delioci do korena iz x */
            if (x % d == 0) {
                prost = 0;
                break;                        /* izlazi samo iz petlje po d */
            }
        }
        if (prost)
            printf("%d ", x);
    }
    printf("\n");
    return 0;
}

Uslov d * d <= x je dovoljan: ako x ima delilac veći od korena, ima i manji. Više o tome: Prosti brojevi i faktorizacija.

Koliko puta se izvrši telo?

Gruba procena za takmičenja: računar uradi oko 10⁸ prostih operacija u sekundi. Ako je n = 10 000, dve ugnježdene petlje (10⁸) su na granici, a tri su prespore.

Zadaci za vežbu

Za svaki zadatak postoji primer, uputstvo i rešenje. Rešenja su provereno tačna na primerima iz teksta.

Proveri znanje