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).
Sa standardnog ulaza se unosi realan broj x (0.8 ≤ x ≤ 1.2) i ceo broj n (0 ≤ n ≤ 20).
Izlaz:
1.1
5
Na standardni izlaz ispiši vrednost Xn zaokruženu na 5 decimala.
Primer:
Ulaz:1.1
5
Izlaz:
1.61051Reš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.
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:
5
70
95
75
30
99
95
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
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
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 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)
}
int main()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;{
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;
}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.
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
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
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: