REKURZIVNI ALGORITMI- PRIMERI

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

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

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

Rešenje

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

3. Ispisivanje brojeva inverzno pa direktno

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

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

5. Broj permutacija

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

6. Fiboač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.

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

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

Figure 1: Rekurzivne funkcije: Broj presečenih kvadrata dijagonalom pravougaonika koji ih sadrži

Rešiti zadatak po sledećem algoritmu:

Učitati dva cela broja koji predstavljaju dužinu i sirinu pravougaonika a i b
Izdeliti pravougaonik na kvadratiće stranice 1cm, tako da pravougaonik izgleda kao šahovska tabla koja ima b kolona i a redova.
Odrediti koeficijent pravca dijagonale kao tangens ugla(odnos širine i dužine pravougaonika b/a)
Napraviti rekurzivnu funkciju koja vraća broj kvadrata presečenih dijagonalom pravougaonika
Funkciji proslediti početnu vrednost dužine pravougaonika, maksimalnu vrednost ymax koordinate u prvoj koloni kvadrata, kao i koeficijent pravca.
Unutar funkcije prenetu vrednost za ymax postaviti sada da bude ymin. Odrediti ymax na osnovu kednacine prave ymax = ymin + k*1, gde je k, koeficijent pravca prenesen kao parametar, a 1 duzina stranice kvadrata.
Unutar funkcije, takoće, odrediti najmanju celobrojnu vrednost manju od minimuma i najmanju celobrojnu vrednost veću od maksimuma ymax,
odrediti broj kvadrata presečenih dijagonalon samo u tekućoj koloni i sabrati sa ukupnim brojem presečenih kvadrata u narednim kolonama.
Ovaj broj se dobija ponovnim pozivom iste rekurzivne funkcije prilikom dobijanja povratne vrednosti iste.
Ovaj izračunavanje uraditi pod uslovom da je broj preostalih kolona veći od 1
U svakom sledecem pozivu rekurzivne funkcije:
- Smanjiti preostali broj kolona za 1
- maksimalnu vrednost u tekucoj rekurziji treba da postane minimalna vrednost ymin za narednu rekurziju

/Resenje u programskom jeziku 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;

}

9. Algoritam brzog stepenovanja

Napisati rekurzivnu funkciju za brzo stepenovanje Xⁿ

Uneti ceo broj n i iskoristiti funkciju za izračunavanje pomenutog stepena.

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.

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

Kompletno rešenje je objašnjeno na web lokaciji:

Rekurzivni algoritmi

/Resenje u programskom jeziku 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 < m; 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 {

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;

}

REKURZIVNI ALGORITMI- PRIMERI

Uvod u rekurzivne algoritme

Šta je Rekurzija?

Prednosti Rekurzivnih Algoritama

Praktična primena

1. Izračunavanje stepena Xn

2. Prvi i drugi na rang listi

3. Ispisivanje brojeva inverzno pa direktno

4. Sabiranje brojeva rekurzivno

5. Broj permutacija

6. Fiboačijev niz

7. Iz decimalnog u binaran oblik

8. Broj kvadrata presečenih dijagonalom

/*Resenje u programskom jeziku C*/

9. Algoritam brzog stepenovanja

10. Soliter

11. Inverzna matrica

/*Resenje u programskom jeziku C*/

Podešavanja kolačića

1. Izračunavanje stepena Xⁿ

/Resenje u programskom jeziku C/

/Resenje u programskom jeziku C/