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

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

​

12. Sledeća varijacija

Napomena: Zadatak iz zbirke cpp2-Metodička zbirka iz algoritmike sa sajta petlja.org/sr-Latn-RS/biblioteka/r/kursevi/Zbirka2
​
Napiši program koji određuje narednu varijaciju dužine k skupa {1, . . . , n} u leksikografskom poretku.
Ulaz:
Prva linija standardnog ulaza sadrži broj k (1 ≤ k ≤ 100), a druga broj n (1 ≤ n ≤ 100). U trećoj
liniji se nalazi varijacija opisana brojevima razdvojenim po jednim razmakom.

Izlaz:
Na standardni izlaz ispisati sledeću varijaciju u leksikografskom poretku, ako ona postoji, ili , ako je učitana varijacija leksikografski maksimalna.
Primer
Ulaz
5
4
1 1 2 3 4
Izlaz
1 1 2 4 1
​

13. Sve varijacije

Napomena: Zadatak iz zbirke cpp2-Metodička zbirka iz algoritmike sa sajta petlja.org/sr-Latn-RS/biblioteka/r/kursevi/Zbirka2

Napiši program koji određuje sve varijacije sa ponavljanjem dužine k skupa {1, . . . , n}.
Ulaz: Sa standardnog ulaza se učitava broj n (1 ≤ n ≤ 5) i u narednoj liniji broj k (1 ≤ k ≤ 5).
Izlaz: Na standardni izlaz ispisati sve varijacije, sortirane leksikografski.
Primer
Ulaz
2
3
Izlaz
1 1 1
1 1 2
1 2 1
1 2 2
2 1 1
2 1 2
2 2 1
2 2 2
​

14. Sve reči od datih slova

​Stringom s dat je skup malih slova engleskog alfabeta (slova su u stringu uređena u rastućem poretku) i prirodan broj k. Napisati program kojim se prikazuju u leksikografskom poretku sve reči dužine k koje se mogu formirati od datog skupa.

Ulaz:
Na standardnom ulazu u prvoj liniji nalazi se string s dužine najviše 10, u drugoj liniji nalazi se
prirodan broj k (k ≤ 6, k ≤ n).

Izlaz:
Na standardnom izlazu prikazati tražene reči u leksikografskom poretku, svaku reč u posebnoj
liniji.

Primer
Ulaz
amx
2
Izlaz
aa
am
ax
ma
mm
mx
xa
xm
xx​

15. Svi podskupovi

Napiši program koji ispisuje sve podskupove datog skupa.
Ulaz:
Sa standardnog ulaza se učitava broj n (važi 3 ≤ n ≤ 10), a zatim n prirodnih brojeva, rastuće sortiranih, razdvojenih po jednim razmakom.
Izlaz:
Na standardni izlaz ispisati sve podskupove učitanog skupa brojeva, svaki u posebnom redu, sa
elementima razdvojenim jednim razmakom. Prvo se ređaju podskupovi u kojima prvi element nije uključen, a zatim oni u kojima jeste. U svakoj od te dve grupe, prvo se ispisuju podskupovi u kojima drugi element nije uključen, a zatim oni gde jeste i tako dalje.
Primer
Ulaz
3
1 2 3
Izlaz
3
2
2 3
1
1 3
1 2
1 2