REKURZIVNI ALGORITMI- PRIMERI

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

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*/

1. Izračunavanje stepena Xⁿ

/Resenje u programskom jeziku C/

/Resenje u programskom jeziku C/