а) Функција што се повикува самата себе.
б) Променлива што чува повеќе броеви.
в) Наредба за печатење текст.
г) Операција за бришење елемент од стек.
2. Во стек се додаваат вредностите 10, 20 и 30, по тој редослед. Која вредност е на врвот?
а) 10
б) 20
в) 30
г) 0
3. Што прави операцијата pop()?
а) Додава елемент на врвот.
б) Го отстранува елементот од врвот.
в) Ги печати сите елементи.
г) Го сортира стекот.
4. Што ќе испечати следниот код ако се повика f(3)?
void f(int n) {
if (n == 0)
return;
cout << n << " ";
f(n - 1); }
а) 1 2 3
б) 3 2 1
в) 0 1 2 3
г) 3 3 3
5. Кои две тврдења се точни?
а) Рекурзивната функција треба да има услов за запирање.
б) LIFO значи прв влезен, прв излезен.
в) push() додава елемент во стекот.
г) pop() секогаш го печати отстранетиот елемент.
6. Точно или неточно?
Во стек се додаваат 4, 7 и 9, по тој редослед. Првиот повик на pop() го отстранува бројот 9.
7. Точно или неточно?
Рекурзивна функција што нема базен случај секогаш ќе заврши правилно ако започне со n = 5 и при секој повик го намалува n за 1.
8. Што ќе испечати следниот код при повикот f(3)?
void f(int n) {
if (n == 0)
return;
f(n - 1);
cout << n << " ";
}
а) 3 2 1
б) 0 1 2 3
в) 1 2 3
г) 3 2 1 0
Самооценување
Кој поим најдобро го разбрав?
Кој дел ми беше најтежок?
Што би сакал/а дополнително да вежбам?
Примери
Бактериите се размножуваат со делење на две на секој саат. Напишете програма којa ќе го испише бројот на бактерии по 12 часа
0.sat: A 1 1.sat: B C 2 2.sat: B1 B2 C1 C2 4 3.sat:B11 B12 B21 B22 C11 C12 C21 C22 8 |
#include<iostream>
using namespace std;
int rekurzija (int n)
{
if(n>1)
return 2*rekurzija(n-1);
else
return 1;
}
int main ()
{
int n;
n=12;
n=rekurzija(n);
cout<<n;
return 0;
}
Функцијa која внесен број го испишува наназад
#include <iostream>
using namespace std;
void rekurzija(int x)
{ cout<<x%10;
if (x/10>0) rekurzija(x/10);
}
int main()
int main()
{ int n;
cin>>n;
rekurzija(n);
return 0; }
Провери дали даден природен број е палиндром
#include <iostream>
using namespace std;
int reverse_digits(int n, int temp)
{
if (n == 0)
return temp;
temp = (temp * 10) + (n % 10);
return reverse_digits(n / 10, temp);
}
int main()
{
int num;
cout<<"Vnesi broj :"; cin>>num;
int result = reverse_digits(num, 0);
if (result == num)
cout << "Brojot "<<num<<" e palindrom" << endl;
else
cout << "Brojot "<<num<<" ne e palindrom"<< endl;
return 0;
}
1
1+2
1+2+3
1+2+3+4
.......
1+2+3+....+n
На пример, за n=5
suma(5) = 5+suma(4) = 5+4+suma(3) = 5+4+3+suma(2) – 5+4+3+2+suma(1) = 5+4+3+2+1+suma(0) = 5+4+3+2+1+0 = 15
for(i=1; i<=n; i++)
suma(1)
suma(2)
suma(3)
suma(4)
suma(5)
1+2
1+2+3
1+2+3+4
.......
1+2+3+....+n
На пример, за n=5
suma(5) = 5+suma(4) = 5+4+suma(3) = 5+4+3+suma(2) – 5+4+3+2+suma(1) = 5+4+3+2+1+suma(0) = 5+4+3+2+1+0 = 15
for(i=1; i<=n; i++)
suma(1)
suma(2)
suma(3)
suma(4)
suma(5)
#include<iostream>
using namespace std;
long int suma(int n)
{
long s;
if(n==0)
s=0;
else
s=n+suma(n-1);
return s;
}
int main()
{
int i,n;
cout<<"Vnesete go brojot na sumi, n=";
cin>>n;
for(i=1;i<=n;i++)
cout<<"Suma do "<<i<<" suma("<<i<<")="<<suma(i)<<endl;
return 0;
}
using namespace std;
long int suma(int n)
{
long s;
if(n==0)
s=0;
else
s=n+suma(n-1);
return s;
}
int main()
{
int i,n;
cout<<"Vnesete go brojot na sumi, n=";
cin>>n;
for(i=1;i<=n;i++)
cout<<"Suma do "<<i<<" suma("<<i<<")="<<suma(i)<<endl;
return 0;
}
Програма која со рекурзивна функција ги печати фибоначиевите броеви од 1 до n
#include <iostream>
using namespace std;
int fibonaci_niza(int broj)
{
if(broj==0 || broj==1 )
{ return 1; }
return fibonaci_niza(broj-1) + fibonaci_niza(broj-2);
}
int main()
{
int n,i;
cout << "vnesi go n" << endl;
cin>>n;
for(i=0;i<=n;i++)
cout<<fibonaci_niza(i)<<" ";
return 0;
}
Ливчињата рози се распоредени во редови
1- ред 1 лист
2- ред 1 лист
секој нареден ред има онолку ливчиња колку што имаат двете претходни заедно. Напиши програма која ќе пресмета број на листови во н-тиот ред
F0=1
F1=1
....Fn=Fn -1 +Fn -2 , za n >2 , односно бројот на лливчиња е еднаков на Фибоначиевиот број
#include<iostream>
using namespace std;
int fibonaci(int n)
{
if ((n == 0) || (n == 1))
return 1;
else
return fibonaci(n-1) + fibonaci(n-2);
}
int main()
{
int n;
cout<<"Vnesi n=" ;cin>>n;
if (n<0)
cout<<"Ne moze da e negativen broj!";
else
cout<<"Broj livcinja: "<< fibonaci(n);
return 0;
}
Напиши рекурзивна функција за пресметување на сумата на првите 5 броеви
Да се напише програма која ќе го одреди збирот на цифри на даден број. Задачата да се реши со рекурзивна функција
#include<iostream>
using namespace std;
int ZbirCifri(int n)
{
if(n!=0)
return n%10+ZbirCifri(n/10);
else
return 0;
}
int main()
{
int a;
int b;
int suma;
cout<<"Vnesete broj: ";
cin>>a;
suma=ZbirCifri(a);
cout<<"Zbir na cifrite e: "<<suma<<endl;
return 0;
}
Програма која со рекурзивна функција пресметува збир на парните цифри на природен број н
#include <iostream>
using namespace std;
int zbir(int n)
{
int k;
if (n==0) return 0;
else
{
k=n%10;
if(k%2==0)
return k+zbir(n/10);
else return 0+zbir(n/10);
}
}
int main()
{
int n;
cout << "vnesi go n" << endl;
cin>>n;
cout << "zbirot na parnite cifri e " <<zbir(n)<< endl;
return 0;
}
Програма која со рекурзивна функција пресметува дали производите на цифрите на два цели броја се исти. Производ на цифри да се одреди со рекурзија.
#include <iostream>
using namespace std;
int proizvod(int n)
{
if (n<10) return n;
else return n%10*proizvod(n/10);
}
int main()
{
int n,m,a1,a2;
cout << "vnesi go prviot broj" << endl;
cin>>n;
cout << "vnesi go vtoriot broj" << endl;
cin>>m;
a1=proizvod(n);
a2=proizvod(m);
if(a1==a2) cout<<"da";
else cout<<"ne";
return 0;
}
Напиши рекурзивна функција која ги собира кубовите на цифрите на цел број.
Пример ; влез: 1005 излез: 126
#include <iostream>
using namespace std;
int suma_cifra(long int n)
{ int cifra=n%10;
int cifrakub=cifra*cifra*cifra;
if (n/10) // if (n/10 !=0)
return cifrakub + suma_cifra(n/10);
else
return cifrakub;
}
int main()
{
int br;
cout<<"Vnesete broj ";
cin>>br;
if (br<0) br=-br;
cout<<"Suma na kubovite na cifri e " <<suma_cifra(br);
return 0;
}
Програма која за внесен цел број ги печати само цифрите од бројот кои се помали од 5 и бројот на отпечатени цифри. Печатењето на цифрите на бројот помали од 5 да се реализира со рекурзивна функција.
#include <iostream>
using namespace std;
void rekurzija(int m, int b)
{
int c;
if(m==0)
{
cout<<endl;
cout<<"ima "<<b<<" cifri";
}
else
{
c=m%10;
if(c<5)
{
cout<<c<<" ";
b++;
return rekurzija (m/10,b);
}
else
return rekurzija (m/10,b);
}
}
int main()
{
int m,i,b=0;
cout << "vnesi go m" << endl;
cin>>m;
rekurzija(m,b);
return 0;
}
Напиши рекурзивна функција која ја определува најголемата цифра во број
#include <iostream>
using namespace std;
int pogolem(int a, int b)
{
if (a > b) return a;
else return b;
}
int najgolem(int n)
{
if (n<10) return n;
else return pogolem(najgolem(n/10), n%10);
}
int main()
{
int n;
cout<<"Vnesi broj\n";
cin>>n;
cout<<"Najgolema cifra e:"<< najgolem(n);
return 0;
}
Напиши програма која со рекурзивна функција пресметува збир на цифрите на природен број н. Да се провери и испечати дали збирот е прост број (проверката дали бројот е прост направи ја со функција).
#include <iostream>
using namespace std;
int zbir(int n)
{
if (n<10) return n;
else return n%10+zbir(n/10);
}
void prost(int m)
{
int i, t=0;
for(i=2;i<=m/2;i++)
{
if (m%i==0)
{
t=1;
break;
}
}
if (t==0) cout<<"brojot e prost";
else cout<<"brojot ne e prost";
}
int main()
{
int n,k;
cout << "vnesi go n" << endl;
cin>>n;
k=zbir(n);
cout<<"zbirot na cifrite e "<<zbir(n)<<endl;
prost(k);
return 0;
}
Да се пресмета 1!+(1+2)!+(1+2+3)!+…+(1+2+…+n)!
#include <iostream>
using namespace std;
int factorial(int n) {
if (n == 0)
return 1;
else
return n * factorial(n - 1);
}
int sum(int k) {
if (k == 0)
return 0;
else
return k + sum(k - 1);
}
int main() {
int i, n, result = 0;
cin>>n;
if (n > 0)
{
for (i = 1; i < n; i++)
{
int s = sum(i);
result += factorial(s);
cout<< s<<endl;
}
int s = sum(n);
result += factorial(s);
cout<< s<< endl <<result;
}
else
cout<<"Wrong input\n";
return 0;
}
Postoje tri štapa označena s A,B i C. Na prvom štapu su cilindrični diskovi promjenljive veličine. Zadatak je premjestiti sve diskove s štapa A na štap B u redoslijedu
kako se nalaze na štapu A.
Pri prebacivanju diskova treba poštovati sljedeće pravila:
§ Odjednom se smije pomicati samo jedan disk
§ Ne smije se stavljati veći disk iznad manjeg diska
§ Može se koristiti štap C za privremeni smještaj diskova, ali uz poštovanje prethodna dva pravila
- U čemu je ovaj problem rekurzivan? Pokušajmo definirati temeljni slučaj i pravilo rekurzije.
- Temeljni slučaj - je najjednostavniji slučaj kojeg svatko može riješiti. Ako kula sadrži samo jedan disk,tada je rješenje jednostavno: prebaci se taj disk na ciljni štap B.
- Rekurzivno pravilo - Ako kula sadrži N diskova, pomicanje diskova se može izvesti u tri koraka:
- pomaknuti gornjih N-1 diskova na pomoćni štap C
- preostali donji disk s štapa A pomaknuti na ciljni štap B
- zatim kulu od N-1 diska s pomoćnog štapa C treba prebaciti na ciljni štap B
- koristimo funkciju pomakni_kulu, a argumenti koji će nam biti potrebni su: broj diskova koje treba pomaknuti, ime početnog štapa , ime ciljnog štapa, ime pomoćnog štapa.
void pomakni_kulu(int n, char A, char B char C);
- funkcija koja će označiti prebacivanje jednog diska:
void pomakni_disk(char sa_kule, char na_kulu)
- Korištenjem ove funkcije i pravila rekurzije, funkcija pomakni_kulu se može napisati na sljedeći način:
void pomakni_kulu(int n, char A, char B, char C)
{
if (n == 1) {
pomakni_disk(A, B);
}
else {
pomakni_kulu (n - 1, A, C, B);
pomakni_disk (A, B);
pomakni_kulu (n - 1, C, B, A);
}
}
Ili još jednostavnije:
void pomakni_kulu(int n, char A, char B, char C)
{
if (n > 0)
{
pomakni_kulu (n - 1, A, C, B);
pomakni_disk (A, B);
pomakni_kulu (n - 1, C, B, A);
}
}
jer za slučaj kada je n=1 pomakni_kulu(0, ....) ne izvršava ništa pa se u tom slučaju izvršava funkcija pomakni_disk(A,B), što je pravilo temeljnog slučaja.
No comments:
Post a Comment