REKURZIVNI ALGORITMI- PRIMERI
Uvod u rekurzivne algoritme
Šta je Rekurzija?
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
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!
1. Izračunavanje stepena Xn
Napiši program koji pomoću rekurzije rešava stepena Xn
Sa standardnog ulaza se unosi realan broj x (0.8 ≤ x ≤ 1.2) i ceo broj n (0 ≤ n ≤ 20).
Na standardni izlaz ispiši vrednost Xn zaokruženu na 5 decimala.
Primer:
Ulaz:1.1
5
Izlaz:
1.610512. Prvi i drugi na rang listi
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.
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:
9995
3. Ispisivanje brojeva inverzno pa direktno
4. Sabiranje brojeva rekurzivno
5. Broj permutacija
6. Fiboačijev niz
7. Iz decimalnog u binaran oblik
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 |
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 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)
{
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
10. Soliter
- svaki sprat se kreči ili belo ili plavo
- ne smeju biti 3 bela sprata jedan iznad drugog.
11. Inverzna matrica
Primer:
Ulaz
3
3 5 6
2 -6 3
0 1 7
Izlaz
-193
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:
12. Sledeća varijacija
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
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
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
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