SVET PROGRAMIRANJA
  • Početna
  • WEB APLIKACIJE
    • Trendovi u programiranju
    • Internet stvari
    • Kreiranje web aplikacija >
      • Kreiranje web aplikacija 2
      • Kreiranje web sajta >
        • Logo Kreator - naslovna
        • Klase za stil naslovne strane
      • Kreiranje Python web aplikacije >
        • Kreiranje Django Web Aplikacije-početak
        • Logo Kreator - Kreiranje Naslovne strane
        • Django aplikacija i baza podataka
        • Kreiranje aplikacije na Heroku Web Platformi >
          • Kreiranje aplikacije na Heroku Web Platformi 2
        • Dodavanje modula za registraciju >
          • Dodavanje web strane za logovanje
    • ASP.NET Core web aplikacije >
      • Servisiranje statičkih web strana pomoću web servera
      • Kreiranje sql web api servisa koji čita podatke iz baze
      • Kreiranje kontrolera u asp.net web API aplikaciji
      • Komunikacija Javascript web aplikacije sa API serverom
  • Algoritmi
    • Matematički algoritmi >
      • Fibonačijev niz
      • Prosti brojevi i faktorizacija
      • Eratostenovo sito
      • Euklidov algoritam
      • Maksimalna suma podniza
    • Osnovne strukture podataka
    • Sortiranje nizova >
      • Sortiranje objedinjavanjem
      • Brzo Sortiranje
    • Binarna pretraga
    • Rekurzivni algoritmi
    • Zamena iteracija formulom
  • Primeri - C,C++,Java
    • Osnovni primeri >
      • Podaci-primeri
      • Operatori-primeri
      • Grananje u programu - primeri
      • Petlje primeri >
        • Petlje - osnovni primeri
        • Ugnježdene petlje primeri
      • Stringovi - primeri
      • Nizovi primeri >
        • Nizovi-primeri
        • Sortiranje-primeri
      • Matrice primeri
      • Funkcije u C/C++ jeziku -primeri
      • Algoritmi-primeri >
        • Rekurzija-primeri >
          • Prvi i drugi na rang listi
        • Zamena iteracija formulom-primeri >
          • Nedostajući broj-uputstvo
    • Dodatni primeri sa rešenjima >
      • Podaci i tipovi podataka-dodatni primeri
      • Dodatni primeri za vezbu - Klase i objekti >
        • Ramovi za slike objekti-rešenje
        • Zadatak 2-Grupa radnika objekti
        • Salon Automobila rešenje
        • Zadatak 3. Kretanje automobila objekti-rešenje
      • Dodatni primeri za vezbu - grananje u programu
      • Kontrolni Podaci Priprema
      • Priprema za kontrolni zadatak iz petlji
      • Kombinovani primeri za vezbu >
        • Zadatak 6-Interval-rešenje
    • Takmičenja-primeri >
      • Priprema za okružna takmičenja
      • Kvalifikacije za okružna takmičenja >
        • Datum sa najvećom zaradom-rešenje
        • Zbirovi nakon podele - rešenje
        • Zadatak Mešalica-rešenje
      • Priprema za državna takmičenja
      • Opštinska takmičenja
      • Okružna takmičenja
    • Objektno programiranje-primeri >
      • Klase i objekti - primeri
    • Testovi >
      • Kontrolni podaci
      • Kontrolni selekcije
      • Kontrolni petlje
      • Kontrolni - objekti i metode
      • Kontrolni Nizovi
  • C i C++ PREDAVANJA
    • Uvod u C i C++
    • Elementi jezika C
    • Podaci u C/C++ jeziku
    • Operatori u C/C++ jeziku
    • Grananje u programu u C/C++
    • Petlje u programskom jeziku C/C++ >
      • Ugnježdene petlje u C/C++
    • Nizovi u jeziku C/C++ >
      • Dinamički niz-vector
      • Rečnik podataka-mape u C++
      • Dvodimenzionalni nizovi - matrice
      • Dvodimenzioni dinamički nizovi-matrice
    • Stringovi u C/C++ jeziku
    • Pokazivači u C/C++
    • Funkcije u C/C++
  • JAVA PREDAVANJA
    • Uvod u Javu
    • Java osnove >
      • Podaci u JAVA programskom jeziku
      • Operatori u JAVI
      • Grananje u programu u programskom jeziku Java
      • Petlje u Javi
      • Nizovi u Javi
    • Objektno programiranje >
      • Klase i objekti
      • Nasleđivanje klasa
      • Apstraktne klase i interfejsi
    • Grafika u Javi >
      • Grafički korisnički interfejs(GUI)
      • Događaji u JAVI
      • Crtanje u prozoru
      • Grafika u Javi-primer
      • Animacije u Javi-primer
      • Kreiranje 2D igrice u JAVI
      • Aplikacije u Javi-primeri
    • Java i simulacije u fizici >
      • Klase i objekti sa primenom u fizici
      • Upotreba ciklusa i nizova u simulacijama iz fizike
      • Primeri simulacija u EJS-u
    • Processing >
      • Processing - uvod
      • Osnove processinga sa Javom
      • Vektori u Processing-u >
        • Opracije sa vektorima
      • Processing u 2D >
        • Kosi hitac u Processing-u
        • Primer kosog hica u processingu
        • Strma ravan u Processing-u
        • Analiza klizanja tela niz strmu ravan primer
        • Animacija Kružnog kretanja
      • Processing u 3D >
        • Uvod u 3D processing
        • Kretanje 3D objekata u processing-u
  • Politika Privatnosti
  • Linkovi
  • Učenje na daljinu
    • Učenje na daljinu-osnovci takmicari

Srpski | English

REKURZIVNI ALGORITMI- PRIMERI


Pre nego što pristupite rešavanju zadataka, pročitajte lekciju na strani: Rekurzivni algoritmi

1. Izračunavanje stepena Xn

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

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 Xn 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
Rekurzivne funkcije: Broj presečenih kvadrata dijagonalom pravougaonika koji ih sadrži
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 Xn
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;
}

Powered by Create your own unique website with customizable templates.
  • Početna
  • WEB APLIKACIJE
    • Trendovi u programiranju
    • Internet stvari
    • Kreiranje web aplikacija >
      • Kreiranje web aplikacija 2
      • Kreiranje web sajta >
        • Logo Kreator - naslovna
        • Klase za stil naslovne strane
      • Kreiranje Python web aplikacije >
        • Kreiranje Django Web Aplikacije-početak
        • Logo Kreator - Kreiranje Naslovne strane
        • Django aplikacija i baza podataka
        • Kreiranje aplikacije na Heroku Web Platformi >
          • Kreiranje aplikacije na Heroku Web Platformi 2
        • Dodavanje modula za registraciju >
          • Dodavanje web strane za logovanje
    • ASP.NET Core web aplikacije >
      • Servisiranje statičkih web strana pomoću web servera
      • Kreiranje sql web api servisa koji čita podatke iz baze
      • Kreiranje kontrolera u asp.net web API aplikaciji
      • Komunikacija Javascript web aplikacije sa API serverom
  • Algoritmi
    • Matematički algoritmi >
      • Fibonačijev niz
      • Prosti brojevi i faktorizacija
      • Eratostenovo sito
      • Euklidov algoritam
      • Maksimalna suma podniza
    • Osnovne strukture podataka
    • Sortiranje nizova >
      • Sortiranje objedinjavanjem
      • Brzo Sortiranje
    • Binarna pretraga
    • Rekurzivni algoritmi
    • Zamena iteracija formulom
  • Primeri - C,C++,Java
    • Osnovni primeri >
      • Podaci-primeri
      • Operatori-primeri
      • Grananje u programu - primeri
      • Petlje primeri >
        • Petlje - osnovni primeri
        • Ugnježdene petlje primeri
      • Stringovi - primeri
      • Nizovi primeri >
        • Nizovi-primeri
        • Sortiranje-primeri
      • Matrice primeri
      • Funkcije u C/C++ jeziku -primeri
      • Algoritmi-primeri >
        • Rekurzija-primeri >
          • Prvi i drugi na rang listi
        • Zamena iteracija formulom-primeri >
          • Nedostajući broj-uputstvo
    • Dodatni primeri sa rešenjima >
      • Podaci i tipovi podataka-dodatni primeri
      • Dodatni primeri za vezbu - Klase i objekti >
        • Ramovi za slike objekti-rešenje
        • Zadatak 2-Grupa radnika objekti
        • Salon Automobila rešenje
        • Zadatak 3. Kretanje automobila objekti-rešenje
      • Dodatni primeri za vezbu - grananje u programu
      • Kontrolni Podaci Priprema
      • Priprema za kontrolni zadatak iz petlji
      • Kombinovani primeri za vezbu >
        • Zadatak 6-Interval-rešenje
    • Takmičenja-primeri >
      • Priprema za okružna takmičenja
      • Kvalifikacije za okružna takmičenja >
        • Datum sa najvećom zaradom-rešenje
        • Zbirovi nakon podele - rešenje
        • Zadatak Mešalica-rešenje
      • Priprema za državna takmičenja
      • Opštinska takmičenja
      • Okružna takmičenja
    • Objektno programiranje-primeri >
      • Klase i objekti - primeri
    • Testovi >
      • Kontrolni podaci
      • Kontrolni selekcije
      • Kontrolni petlje
      • Kontrolni - objekti i metode
      • Kontrolni Nizovi
  • C i C++ PREDAVANJA
    • Uvod u C i C++
    • Elementi jezika C
    • Podaci u C/C++ jeziku
    • Operatori u C/C++ jeziku
    • Grananje u programu u C/C++
    • Petlje u programskom jeziku C/C++ >
      • Ugnježdene petlje u C/C++
    • Nizovi u jeziku C/C++ >
      • Dinamički niz-vector
      • Rečnik podataka-mape u C++
      • Dvodimenzionalni nizovi - matrice
      • Dvodimenzioni dinamički nizovi-matrice
    • Stringovi u C/C++ jeziku
    • Pokazivači u C/C++
    • Funkcije u C/C++
  • JAVA PREDAVANJA
    • Uvod u Javu
    • Java osnove >
      • Podaci u JAVA programskom jeziku
      • Operatori u JAVI
      • Grananje u programu u programskom jeziku Java
      • Petlje u Javi
      • Nizovi u Javi
    • Objektno programiranje >
      • Klase i objekti
      • Nasleđivanje klasa
      • Apstraktne klase i interfejsi
    • Grafika u Javi >
      • Grafički korisnički interfejs(GUI)
      • Događaji u JAVI
      • Crtanje u prozoru
      • Grafika u Javi-primer
      • Animacije u Javi-primer
      • Kreiranje 2D igrice u JAVI
      • Aplikacije u Javi-primeri
    • Java i simulacije u fizici >
      • Klase i objekti sa primenom u fizici
      • Upotreba ciklusa i nizova u simulacijama iz fizike
      • Primeri simulacija u EJS-u
    • Processing >
      • Processing - uvod
      • Osnove processinga sa Javom
      • Vektori u Processing-u >
        • Opracije sa vektorima
      • Processing u 2D >
        • Kosi hitac u Processing-u
        • Primer kosog hica u processingu
        • Strma ravan u Processing-u
        • Analiza klizanja tela niz strmu ravan primer
        • Animacija Kružnog kretanja
      • Processing u 3D >
        • Uvod u 3D processing
        • Kretanje 3D objekata u processing-u
  • Politika Privatnosti
  • Linkovi
  • Učenje na daljinu
    • Učenje na daljinu-osnovci takmicari
SVET PROGRAMIRANJA