Rekurzivni algoritmi – primeri

Strana 3 od 5 · Primeri algoritama

Uvod u rekurzivne algoritme

Rekurzija je moćan koncept u programiranju koji omogućava funkcijama da se pozivaju same unutar svog tela. Ovaj pristup često se koristi za rešavanje problema koji mogu biti podeljeni na manje, slične podprobleme. Rekurzivni algoritmi su izuzetno korisni u mnogim oblastima, uključujući matematičke proračune, pretragu i sortiranje podataka, kao i za rešavanje kompleksnih problema koji imaju prirodne strukture stabala ili grafova.

Šta je Rekurzija?

Rekurzija se dešava kada funkcija poziva samu sebe kako bi rešila manji deo problema. Svaka rekurzivna funkcija mora imati osnovni slučaj koji zaustavlja dalje pozive, i rekurzivni slučaj koji razlaže problem na manje delove. Ključ uspešne primene rekurzije je dizajniranje funkcije na način da pravilno obrađuje osnovni slučaj i efikasno rešava rekurzivne slučajeve.

Prednosti Rekurzivnih Algoritama

Jednostavnost: Rekurzija može pojednostaviti kod za složene probleme koji bi u iterativnoj verziji bili teži za razumevanje i implementaciju.
Elegancija: Mnoge prirodne i matematičke strukture (kao što su stabla i grafovi) se prirodno predstavljaju rekurzivno.
Modularnost: Korišćenje rekurzije može pomoći u organizovanju koda na modularan i čitljiv način.

Praktična primena

Na ovoj stranici ćete pronaći zadatke koji koriste rekurziju za rešavanje različitih problema. Od jednostavnih zadataka kao što su izračunavanje stepena broja i sabiranje prirodnih brojeva, do složenijih izazova kao što su pronalaženje permutacija i rad sa matricama. Svaki zadatak je dizajniran da vam pomogne da poboljšate svoje veštine u programiranju koristeći rekurziju.
Pre nego što pristupite rešavanju zadataka, preporučujemo da proučite osnovne koncepte rekurzije kako biste bolje razumeli pristupe i tehnike koje će vam biti potrebne. Srećno sa rešavanjem! Pre nego što pristupite rešavanju zadataka, pročitajte lekciju na strani: Rekurzivni algoritmi

Pre nego što počneš: pročitaj lekciju Rekurzivni algoritmi.
Kako da vežbaš: prvo pokušaj sam/a da rešiš zadatak (makar na papiru), zatim otvori uputstvo, a rešenje tek na kraju. Rešenja su najčešće u jeziku C ili C++; ako učiš Javu ili Python, prepiši ideju u svoj jezik.

ZADATAK 01

Izračunavanje stepena xⁿ

Napiši program koji pomoću rekurzije rešava stepena Xⁿ

Ulaz:
Sa standardnog ulaza se unosi realan broj x (0.8 ≤ x ≤ 1.2) i ceo broj n (0 ≤ n ≤ 20).Izlaz:

Na standardni izlaz ispiši vrednost Xⁿ zaokruženu na 5 decimala.

Primer:

Ulaz:
1.1
5

Izlaz:

1.61051
Rešenje: Zadatak je objašnjen detaljno na stranici: Rekurzivni algoritmi

ZADATAK 02

Prvi i drugi na rang listi

Na atletskom takmičenju učestvovalo je N učesnika . Na kraju takmičenja se sumiraju rezultati i formira se lista
u nerastućem poretku po broju osvojenih poena, od najviše do najmanje osvojenih poena. Napisati program
kojim se određuje broj poena takmičara koji su prvi i drugi na rang listi.Ulaz:

Prva linija standardnog ulaza sadrži prirodan broj N (1 ≤ N ≤ 20000) koji predstavlja broj takmičara. U svakoj od narednihN linija nalazi se ceo broj iz intervala [0, 20000], ti brojevi predstavljaju poene takmičara, koji nisu sortirani.

Izlaz:

U jednoj liniji standardnog izlaza prikazati broj poena prvog i drugog takmičara na rang listi.

Primer:

Ulaz:
5
70
95
75
30
99

Izlaz:

99
95
Pogledati sličan zadatak na sajtu petlja: petlja.org/biblioteka/r/Zbirka2/drugi_na_rang_listi

Otvori rešenje

ZADATAK 03

Ispisivanje brojeva inverzno pa direktno

Napisati rekurzivnu funkciju koja ispisuje brojeve od 1 do n u inverznom pa u direktnom poretku.

ZADATAK 04

Sabiranje brojeva rekurzivno

Napraviti funkciju koja sabira prvih n prirodnih brojeva rekurzivno. U glavnoj metodi učitati n i pozvati rekurzivnu funkciju za izračunavanje zbira tih brojeva.

ZADATAK 05

Broj permutacija

Uneti ceo broj n, a zatim odrediti broj permutacija od n elemenata, koristeći rekurziju

ZADATAK 06

Fibonačijev niz

Uneti ceo broj n, a zatim ispisati Fibonačijev niz brojeva od n elemenata pomoću rekurzije. Odrediti takođe i zbir svih tih elemenata.

ZADATAK 07

Iz decimalnog u binaran oblik

Napisati rekurzivnu funkciju kojom se prirodni broj napisan u dekadnom obliku n ispisuje u binarnom obliku u direktnom poretku.
Primer 1:
Ulaz
22
Izlaz
0000 0000 0001 0110
Primer 2:
Ulaz
2147483647
Izlaz
1111 1111 1111 1111

ZADATAK 08

Broj kvadrata presečenih dijagonalom

Pravougaonik čije su širina i visina m[cm] i n[cm] redom sastavljen je od m*n kvadrata čije su stranice po 1cm. Napraviti program koji pomoću rekurzije određuje koliko će kvadrata biti presečeno sa glavnom dijagonalom tog pravougaonika.
Primer:
Ulaz
5
3
Izlaz
7Figure 1: Rekurzivne funkcije: Broj presečenih kvadrata dijagonalom pravougaonika koji ih sadrži

Rešenje (C)

#include <stdio.h>
#include <math.h>

int brkv(float n, float ymin,float k)
{
    int x;/*broj presečenih kvadrata u tekućoj koloni*/
    int a,b;
    float ymax=ymin + k; //y=k*x
    a=floor(ymin); /*prvi manji ceo broj*/
    b=ceil(ymax);/* prvi veci ceo broj*/
    x=b-a;
    if(n > 1)
        x=x+brkv(n-1,ymax,k); /*Ono sto je ovde ymax u sledecoj ce biti ymin*/
    return x;
}                   int main()
{
    float a,b,k;
    scanf("%f%f",&a,&b);
    k=b/a;/* koeficijent pravca dijagonale, tj, tangens ugla koji zaklapa dijagonala sa stranicom pravougaonika*/
    printf("%d",brkv(a,0,k));

    return 0;
}

ZADATAK 09

Algoritam brzog stepenovanja

Napisati rekurzivnu funkciju za brzo stepenovanje XⁿUneti ceo broj n i iskoristiti funkciju za izračunavanje pomenutog stepena.

ZADATAK 10

Soliter

Soliter od n spratova treba da se kreči pod sledećim uslovima:

svaki sprat se kreči ili belo ili plavo
ne smeju biti 3 bela sprata jedan iznad drugog.

Na koliko se načina može okrečiti jedna n-to spratnica.

ZADATAK 11

Inverzna matrica

Učitati n, a zatim učitati matricu reda n*n. Napraviti program koji računa determinantu te matrice i njenu inverznu matricu.
Primer:
Ulaz
3
3 5 6
2 -6 3
0 1 7
Izlaz
-193

Rešenje:
Rad sa matricama je objašnjen detaljno na web strani: Dvodimenzioni dinamički nizovi-matrice
Izračunavanje determinante matrice je detaljno objašnjeno na web strani: Rekurzivni algoritmi

Rešenje (C)

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

/*Određuje determinantu matrice a
parametri:
a-matrica početna n*n
n-dimenzija kvadratne matrice
r-red za razvijanje matrice ili -1 ako se ne razvija po redu
c-kolona za razvijanje matrice ili -1 ako se ne razvija po koloni
redP-niz precrtanih redova u matrici
colP-niz precrtanih kolona u matrici
*/
float ** inverzna(int ** aT, int det, int n)
{
    float **aI;
    aI = (float **)malloc(n*sizeof(float*));
    for(int i=0; i < n; i++)
    {
        aI[i]=(float *)malloc(n*sizeof(float));

        for(int j=0; j < n; j++)
        {
            aI[i][j]=(float)aT[i][j]/det;
        }
    }
    return aI;
}

int ** copyMatrix(int ** aT, int n)
{
    int **aC;
    aC = (int**)malloc(n*sizeof(int*));
    for(int i=0; i < n; i++)
    {
        aC[i]=(int*)malloc(n*sizeof(int));
        for(int j=0; j < n; j++)
        {
            aC[i][j]=aT[i][j];
        }
    }
    return aC;
}
void transponovana(int ** a, int n)
{
    for(int i=0; i < n; i++)
    {
        for(int j=i; j < n; j++)
        {
            /*zamena*/
            int b=a[i][j];
            a[i][j]=a[j][i];
            a[j][i]=b;
        }
    }
}

void ispisatiMatricuF( float ** a, int n)
{
    for(int i=0; i < n; i++)
    {
        for(int j=0; j < n; j++)
            {
            printf("%.2f ",a[i][j]);
        }
        printf("\n");
    }
}

/*Funkcija za ispisivanje matrice
* parametri su
* a- pokazivač na matricu(pokazivač na pokazivač)
* n -dimenzija matrice
*/
void ispisatiMatricu( int ** a, int n)
{
    for(int i=0; i < n; i++)
    {
        for(int j=0; j < n; j++)
        {
            printf("%d ",a[i][j]);
        }
        printf("\n");
    }
}
/*Određuje determinantu matrice a
parametri:
a-matrica početna n*n
n-dimenzija kvadratne matrice
r-red za razvijanje matrice ili -1 ako se ne razvija po redu
c-kolona za razvijanje matrice ili -1 ako se ne razvija po koloni
redP-niz precrtanih redova u matrici
colP-niz precrtanih kolona u matrici
*/
int determinanta(int ** a,int n, int r,int c,int dim, int * redP, int * colP)
{
    int rez=0;
    if(dim==1)
    {
        int i=0,j=0;
        while(redP[i])
        {
            i++;
        }
        while(colP[j])
        {
            j++;
        }
        rez=a[i][j];
    }
    else
    {
        int k=1;
        if(r!=-1 && c==-1) //ako se determinanta razvija po redu
        {
            int pom=n-dim;//smanjenje broja posmatranih redova u originalnoj matrici
            while(redP[r]){
                r++;
            }
            r=r%n;//korekcija ako je r > n
            for(int j = 0,t = 0; j < n; j++)
            {
                if(colP[j])
                {
                    continue;
                }
                k=(int)pow(-1,(r-pom+t));//koeficijent kofaktora(1 ili -1)
                colP[j]=1;//precrtana kolona u velikoj matrici
                redP[r]=1;//precrtan red u velikoj matrici

                /*Rekurzivni poziv iste funkcije*/
                int d=determinanta(a,n,0,-1,dim-1,redP,colP);
                printf("red %d, col %d: %d * %d * %d\n",r,j,k,a[r][j],d);
                rez=rez+k*a[r][j]*d;
                colP[j]=0;//vracena precrtana kolona u velikoj matrici
                redP[r]=0;//vracen precrtan red u velikoj matrici
                t++;
                }
            }
            else if(c!=-1 && r==-1)
            {
                int pom=n-dim;//smanjenje broja posmatranih redova u originalnoj matrici
                while(colP[c]){
                    c++;
                }
                c=c%n;//korekcija ako je r>n
                for(int i=0,h=0; i < n; i++)
                {
                    if(redP[i])
                    {
                        continue;
                    }
                    k=(int)pow(-1,(c-pom+h));//koeficijent kofaktora(1 ili -1)
                    colP[c]=1;//precrtana kolona u velikoj matrici
                    redP[i]=1;//precrtan red u velikoj matrici
                    int d=determinanta(a,n,-1,0,dim-1,redP,colP);
                    printf("red %d, col %d: %d * %d * %d\n",i,c,k,a[i][c],d);
                    rez=rez+k*a[i][c]*d;
                    colP[c]=0;//vracena precrtana kolona u velikoj matrici
                    redP[i]=0;//vracen precrtan red u velikoj matrici
                    h++;
                }
            }
            else /*Greska*/
            {
                printf("Greska");
                return -1;
            }
        }
        return rez;
    }
    void adjugovana(int ** a, int n)
    {
        int **aA;
        aA= copyMatrix(a,n);
        int k=1;

        for(int i=0; i < n; i++)
        {
            for(int j=0; j < n; j++)
            {
                int * colP=(int*) malloc(n*sizeof(int));
                for(int i=0; i < n; i++)
                {
                    colP[i]=0;
                }
                int * redP=(int*) malloc(n*sizeof(int));
                for(int i=0; i < n; i++)
                {
                    redP[i]=0;
                }
                redP[i]=1;
                colP[j]=1;
                int kofA;
                kofA=determinanta(aA,n,0,-1,n-1,redP,colP);
                k=(int)pow(-1,(i+j));
                a[i][j]=k*kofA;
                free(redP);
                free(colP);
            }
        }
    }
    int main()
    {
        int n;
        int **A;
        float ** AI;
        printf("n=?\n");
        scanf("%d",&n);
        A=(int**)malloc(n*sizeof(int*));
        printf("Matrica?\n");
        for(int i=0; i < n; i++)
        {
            A[i]=(int*)malloc(n*sizeof(int));
            for(int j=0; j < n; j++)
{
                scanf("%d",&A[i][j]);
            }
        }
        printf("Matrica ispis:\n");
        ispisatiMatricu(A,n);
        int * colP=(int*) malloc(n*sizeof(int));
        for(int i=0; i < n; i++)
        {
            colP[i]=0;
        }
        int * redP=(int*) malloc(n*sizeof(int));
        for(int i=0; i < n; i++)
        {
            redP[i]=0;
        }
        int d=determinanta(A,n,0,-1,n,redP,colP);/*parametri: matrica n*n(A), red po kome ce se razvijati,
        kolona=-1 znaci da se ne razvija po koloni, niz precrtanih redova, niz precrtanih kolona*/
        free(colP);
        free(redP);
        printf("Determinanta(A): %d\n",d);
        if(d==0)
        {
            printf("Matrica je singularna");
            return 0;
        }
        transponovana(A,n);
        ispisatiMatricu(A,n);

        printf("Adjugovana matrica A:\n");
        adjugovana(A,n);

        ispisatiMatricu(A,n);
        AI=inverzna(A,d,n);
        ispisatiMatricuF(AI,n);
        return 0;
    }

Rešenje (C)

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

/*Određuje determinantu matrice a
parametri:
a-matrica početna n*n
n-dimenzija kvadratne matrice
r-red za razvijanje matrice ili -1 ako se ne razvija po redu
c-kolona za razvijanje matrice ili -1 ako se ne razvija po koloni
redP-niz precrtanih redova u matrici
colP-niz precrtanih kolona u matrici
*/
float ** inverzna(int ** aT, int det, int n)
{
    float **aI;
    aI = (float **)malloc(n*sizeof(float*));
    for(int i=0; i < n; i++)
    {
        aI[i]=(float *)malloc(n*sizeof(float));

        for(int j=0; j < n; j++)
        {
            aI[i][j]=(float)aT[i][j]/det;
        }
    }
    return aI;
}

int ** copyMatrix(int ** aT, int n)
{
    int **aC;
    aC = (int**)malloc(n*sizeof(int*));
    for(int i=0; i < n; i++)
    {
        aC[i]=(int*)malloc(n*sizeof(int));
        for(int j=0; j < n; j++)
        {
            aC[i][j]=aT[i][j];
        }
    }
    return aC;
}
void transponovana(int ** a, int n)
{
    for(int i=0; i < n; i++)
    {
        for(int j=i; j < n; j++)
        {
            /*zamena*/
            int b=a[i][j];
            a[i][j]=a[j][i];
            a[j][i]=b;
        }
    }
}

void ispisatiMatricuF( float ** a, int n)
{
    for(int i=0; i < n; i++)
    {
        for(int j=0; j < n; j++)
            {
            printf("%.2f ",a[i][j]);
        }
        printf("\n");
    }
}

/*Funkcija za ispisivanje matrice
* parametri su
* a- pokazivač na matricu(pokazivač na pokazivač)
* n -dimenzija matrice
*/
void ispisatiMatricu( int ** a, int n)
{
    for(int i=0; i < n; i++)
    {
        for(int j=0; j < n; j++)
        {
            printf("%d ",a[i][j]);
        }
        printf("\n");
    }
}
/*Određuje determinantu matrice a
parametri:
a-matrica početna n*n
n-dimenzija kvadratne matrice
r-red za razvijanje matrice ili -1 ako se ne razvija po redu
c-kolona za razvijanje matrice ili -1 ako se ne razvija po koloni
redP-niz precrtanih redova u matrici
colP-niz precrtanih kolona u matrici
*/
int determinanta(int ** a,int n, int r,int c,int dim, int * redP, int * colP)
{
    int rez=0;
    if(dim==1)
    {
        int i=0,j=0;
        while(redP[i])
        {
            i++;
        }
        while(colP[j])
        {
            j++;
        }
        rez=a[i][j];
    }
    else
    {
        int k=1;
        if(r!=-1 && c==-1) //ako se determinanta razvija po redu
        {
            int pom=n-dim;//smanjenje broja posmatranih redova u originalnoj matrici
            while(redP[r]){
                r++;
            }
            r=r%n;//korekcija ako je r > n
            for(int j = 0,t = 0; j < n; j++)
            {
                if(colP[j])
                {
                    continue;
                }
                k=(int)pow(-1,(r-pom+t));//koeficijent kofaktora(1 ili -1)
                colP[j]=1;//precrtana kolona u velikoj matrici
                redP[r]=1;//precrtan red u velikoj matrici

                /*Rekurzivni poziv iste funkcije*/
                int d=determinanta(a,n,0,-1,dim-1,redP,colP);
                printf("red %d, col %d: %d * %d * %d\n",r,j,k,a[r][j],d);
                rez=rez+k*a[r][j]*d;
                colP[j]=0;//vracena precrtana kolona u velikoj matrici
                redP[r]=0;//vracen precrtan red u velikoj matrici
                t++;
                }
            }
            else if(c!=-1 && r==-1)
            {
                int pom=n-dim;//smanjenje broja posmatranih redova u originalnoj matrici
                while(colP[c]){
                    c++;
                }
                c=c%n;//korekcija ako je r>n
                for(int i=0,h=0; i < n; i++)
                {
                    if(redP[i])
                    {
                        continue;
                    }
                    k=(int)pow(-1,(c-pom+h));//koeficijent kofaktora(1 ili -1)
                    colP[c]=1;//precrtana kolona u velikoj matrici
                    redP[i]=1;//precrtan red u velikoj matrici
                    int d=determinanta(a,n,-1,0,dim-1,redP,colP);
                    printf("red %d, col %d: %d * %d * %d\n",i,c,k,a[i][c],d);
                    rez=rez+k*a[i][c]*d;
                    colP[c]=0;//vracena precrtana kolona u velikoj matrici
                    redP[i]=0;//vracen precrtan red u velikoj matrici
                    h++;
                }
            }
            else /*Greska*/
            {
                printf("Greska");
                return -1;
            }
        }
        return rez;
    }
    void adjugovana(int ** a, int n)
    {
        int **aA;
        aA= copyMatrix(a,n);
        int k=1;

        for(int i=0; i < n; i++)
        {
            for(int j=0; j < n; j++)
            {
                int * colP=(int*) malloc(n*sizeof(int));
                for(int i=0; i < n; i++)
                {
                    colP[i]=0;
                }
                int * redP=(int*) malloc(n*sizeof(int));
                for(int i=0; i < n; i++)
                {
                    redP[i]=0;
                }
                redP[i]=1;
                colP[j]=1;
                int kofA;
                kofA=determinanta(aA,n,0,-1,n-1,redP,colP);
                k=(int)pow(-1,(i+j));
                a[i][j]=k*kofA;
                free(redP);
                free(colP);
            }
        }
    }
    int main()
    {
        int n;
        int **A;
        float ** AI;
        printf("n=?\n");
        scanf("%d",&n);
        A=(int**)malloc(n*sizeof(int*));
        printf("Matrica?\n");
        for(int i=0; i < n; i++)
        {
            A[i]=(int*)malloc(n*sizeof(int));
            for(int j=0; j < n; j++)
{
                scanf("%d",&A[i][j]);
            }
        }
        printf("Matrica ispis:\n");
        ispisatiMatricu(A,n);
        int * colP=(int*) malloc(n*sizeof(int));
        for(int i=0; i < n; i++)
        {
            colP[i]=0;
        }
        int * redP=(int*) malloc(n*sizeof(int));
        for(int i=0; i < n; i++)
        {
            redP[i]=0;
        }
        int d=determinanta(A,n,0,-1,n,redP,colP);/*parametri: matrica n*n(A), red po kome ce se razvijati,
        kolona=-1 znaci da se ne razvija po koloni, niz precrtanih redova, niz precrtanih kolona*/
        free(colP);
        free(redP);
        printf("Determinanta(A): %d\n",d);
        if(d==0)
        {
            printf("Matrica je singularna");
            return 0;
        }
        transponovana(A,n);
        ispisatiMatricu(A,n);

        printf("Adjugovana matrica A:\n");
        adjugovana(A,n);

        ispisatiMatricu(A,n);
        AI=inverzna(A,d,n);
        ispisatiMatricuF(AI,n);
        return 0;
    }

Još zadataka za vežbu

Kombinatorni problemi – primeri – generisanje varijacija, podskupova i permutacija (zadaci koji su ranije bili i na ovoj strani)
Algoritam brzog stepenovanja – detaljno objašnjenje

Rekurzivni algoritmi – primeri

Uvod u rekurzivne algoritme

Šta je Rekurzija?

Prednosti Rekurzivnih Algoritama

Praktična primena

Izračunavanje stepena xⁿ

Prvi i drugi na rang listi

Ispisivanje brojeva inverzno pa direktno

Sabiranje brojeva rekurzivno

Broj permutacija

Fibonačijev niz

Iz decimalnog u binaran oblik

Broj kvadrata presečenih dijagonalom

Uputstvo

Rešenje (C)

Algoritam brzog stepenovanja

Soliter

Inverzna matrica

Uputstvo

Rešenje (C)

Rešenje (C)

Sledeća varijacija

Sve varijacije

Sve reči od datih slova

Svi podskupovi

Još zadataka za vežbu

Rekurzivni algoritmi – primeri

Uvod u rekurzivne algoritme

Šta je Rekurzija?

Prednosti Rekurzivnih Algoritama

Praktična primena

Izračunavanje stepena xn

Prvi i drugi na rang listi

Ispisivanje brojeva inverzno pa direktno

Sabiranje brojeva rekurzivno

Broj permutacija

Fibonačijev niz

Iz decimalnog u binaran oblik

Broj kvadrata presečenih dijagonalom

Uputstvo

Rešenje (C)

Algoritam brzog stepenovanja

Soliter

Inverzna matrica

Uputstvo

Rešenje (C)

Rešenje (C)

Sledeća varijacija

Sve varijacije

Sve reči od datih slova

Svi podskupovi

Još zadataka za vežbu

Izračunavanje stepena xⁿ