Subiecte pe pagină :
FUNCTII C++
RECURSIVITATE(recursivitate directă,fct Fibonacci) RECURSIVITATE INDIRECTA/referintă forward
Metoda Backtracking
Metoda Divide et impera
FUNCTIA
poate fi declarata de programator sau este predefinita .
·
Cele predefinite presupun o includere
in program a unui fisier antet(header) .
Exemplu
#include<conio.h> pt functiile predefinite
getch() si getche().
#include<math.h> pt functii sin,cos ,sqrt,sqr etc
#include<stdio.h> pt fprintf,fscanf,fopen etc
· Funcțiile realizate de programatori presupun declararea in zona de declaratii a programului inaintea utilizarii sub forma de
Antet + Instructiuni
Concret avem declaratia functiei max
int
max(int a,int b) {if (a>b) return a; else return b;}
antet
cu parametrii formali a si b si intre acolade sunt instructiunile functiei
daca in programul principal-functia
main apare un apel de forma max(2,5) acesta declanseaza comparatia intre 2 si 5
si functia max are valoarea 5.
·
Functiile pot avea cuvantul void in fata numelui (identificatorului)
si atunci nu sunt purtatoare de valoare
·
Dupa numele de functie nu lasam
spatiu ,punem direct parantezele intre care se afla parametrii
·
Parametrii pot lipsi uneori si in
aceasta situatie putem scrie void sau nu scriem nimic intre paranteze.
·
Exemplu de fct predefinite fara parametrii sunt cls(), getch().
·
La declarare folosim parametrii
formali
·
La apel avem parametrii actuali
·
F(2,5) are ca parametrii actuali pe 2 si 5
·
Parametrii au tipul precizat atunci
cand exista si daca sunt mai multi parametrii de acelasi tip se separa prin virgula.
·
Functiile se pot autoapela (avem posibilitatea recursivitatii)
in scopul crearii unor programe extreme de simple
Test Identificati prin subliniere cu o linie declaratia , prin subliniere cu doua linii apelul functiei putere p:
#include<iostream.h>
int
a,b;
int
p(int x,int n)
{if(x==0)
return 0;
if((x!=0)&&(n==0))
return
1;
if((x!=0)&&(n!=0))
return
p(x,n-1)*x;
}
int main()
{cin>>a;
{cin>>a;
cin>>b;
cout
<<p(a,b); return 0;
}
(Aceeași problemă ca pagină WEB în javascript :
<script language="javascript">
var a=eval(window.prompt("dati a ","0"));
var b=eval(window.prompt("dati b ","0"));
a=Math.pow(a,b);
document.writeln("rez=",a);
</script>
OBSERVAM ca avem o serie de functii predefinite eval, pow, prompt prefixate uneori de numele clasei in care sunt definite - Math , window
)
O variantă C++ cu biblioteca math :
#include <iostream>
#include <math.h>
using namespace std;
int a,b;
int main()
{
cin>>a;
cin>>b;
cout <<pow(a,b);
return 0;
}
Recursie directa
(Aceeași problemă ca pagină WEB în javascript :
<script language="javascript">
var a=eval(window.prompt("dati a ","0"));
var b=eval(window.prompt("dati b ","0"));
a=Math.pow(a,b);
document.writeln("rez=",a);
</script>
OBSERVAM ca avem o serie de functii predefinite eval, pow, prompt prefixate uneori de numele clasei in care sunt definite - Math , window
)
O variantă C++ cu biblioteca math :
#include <iostream>
#include <math.h>
using namespace std;
int a,b;
int main()
{
cin>>a;
cin>>b;
cout <<pow(a,b);
return 0;
}
Recursie directa
-functia se autoapeleaza
-f(..)-->f(..)
Sageata semnifica apelul
Functia lui Fibonacci e un exemplu de aplicatie pt
recursivitate directa
#include<iostream>
int n;
int fib(int n) { if(n==0) return 1 ;
if(n==1) return 1 ;
if(n>1) return fib(n-1)+fib(n-2);
}
int main()
{
cout<<”n=”;cin>>n; cout<<”rez=”<<fib(n) ;return 0;
}
OBSERVATIE – functia lui Fibonacci este utilizata in
modelare economica , modelare a tendintelor bursiere , indica capacitatea de calcul a unui sistem .
La calc din laboratoare scolare pt n sub 200 avem o
sansa acceptabila sa nu blocam sistemul !
Memoria este de multe ori alocată la compilare sub forma de blocuri de memorie multiplii de 64 kB . Apelul recursiv înscrie în acest bloc adrese de revenire , date și de aceea ocupă multă memorie la concurenta cu stiva sistemului.Poate bloca
sist de calcul.
Memoria este de multe ori alocată la compilare sub forma de blocuri de memorie multiplii de 64 kB . Apelul recursiv înscrie în acest bloc adrese de revenire , date și de aceea ocupă multă memorie la concurenta cu stiva sistemului.Poate bloca
sist de calcul.
Apelurile recursive utilizeaza la maxim memoria
sistemului dupa un mecanism de stiva in care sunt trecute adrese de revenire ,
valori etc .
Avem un program mai jos pt x la puterea n :
#include<iostream>
int i,n,x;
int putere(int x,int n)
{ if((x==0)&&(n>0)) return 0;
if((x>0) &&(n>0)) return x*putere(x,n-1);
if((x>0) &&(n==0)) return 1;
}
int main()
{
cout<<"n=";cin>>n;
cout<<"x=";cin>>x;
cout<<"rez="<<putere(x,n);return 0;
}
Observatii - avem recursie directa , am evitat situația cu 0 la puterea 0 , trebuie să limităm x , n și rezultatul returnat de funcție la intervalul [0,65567]
Avem un program mai jos pt x la puterea n :
#include<iostream>
int i,n,x;
int putere(int x,int n)
{ if((x==0)&&(n>0)) return 0;
if((x>0) &&(n>0)) return x*putere(x,n-1);
if((x>0) &&(n==0)) return 1;
}
int main()
{
cout<<"n=";cin>>n;
cout<<"x=";cin>>x;
cout<<"rez="<<putere(x,n);return 0;
}
Observatii - avem recursie directa , am evitat situația cu 0 la puterea 0 , trebuie să limităm x , n și rezultatul returnat de funcție la intervalul [0,65567]
Recursia indirecta
-f(..)-->g(…)-->f(..)
Functia f se autoapeleaza prin intermediul altei functii , g in acest caz!
Utilizarea
recursiei este de preferat sa fie mai limitata cand sunt la
indemana modalitati de codificare cu instructiuni repetitive(iterative) deoarece nu se supraincaraca stiva sistemului .
Avem un program mai jos pt x la puterea n :
Test practic. Să punem în program o funcție G care nu face nimic ! Doar redirecteaza apelul functiei putere.
Trebuie declarată inainte de fct putere cu int G(int x,int n); - adică i se scrie doar antetul fără instrucțiuni .
#include<iostream>
int i,n,x;
int G(int x,int n);//prototipul functiei dat inainte de utilizarea sa de alta functie
int putere(int x,int n)
{ if((x==0)&&(n>0)) return 0;
if((x>0) &&(n>0)) return x*G(x,n-1);
if((x>0) &&(n==0)) return 1;
}
int G(int x,int n){ return putere(x,n);}
int main()
{
cout<<"n=";cin>>n;
cout<<"x=";cin>>x;
cout<<"rez="<<putere(x,n);return 0;
}
Avem o declaratie forward a funcţiei G.
TEMĂ
Numele variabilelor locale și unde apar ?
Numele variabilelor globale si locatia?
PROBLEME REZOLVATE ca MODEL si TEMA SUBIECTUL 3
-se rețin variantele recursivă și cea iterativă pentru algoritmul generic .
Mai intai
-Se genereaza o solutie partiala cu k componente (x1, ...., xk) si se verifica daca sunt indeplinite conditii de generare a urmatorului element al solutiei partiale (x1, ... .., xk +1)
Se continua cat timp k<=n , adica nu putem avea decat n elemente intr-o solutie .
S-multimea solutiilor , formata din elemente -perechi ordonate (x1. ... xn) unde
S este inclus in produsul cartezian de multimi X1xX2 .... xXn ceea ce inseamna ca primul element este intotdeauna ales din multimea-X1
al doilea din X2 ... ... ... .. ultimul din Xn.
Obs. In multe situatii practice multimile X1,....,Xn sunt identice (*generare de permutari ,aranjamente,combinari spre exemplu)
Se considera pt algoritmii generici de regula ca X = {1, ..., n}
Avem un program mai jos pt x la puterea n :
Test practic. Să punem în program o funcție G care nu face nimic ! Doar redirecteaza apelul functiei putere.
Trebuie declarată inainte de fct putere cu int G(int x,int n); - adică i se scrie doar antetul fără instrucțiuni .
#include<iostream>
int i,n,x;
int G(int x,int n);//prototipul functiei dat inainte de utilizarea sa de alta functie
int putere(int x,int n)
{ if((x==0)&&(n>0)) return 0;
if((x>0) &&(n>0)) return x*G(x,n-1);
if((x>0) &&(n==0)) return 1;
}
int G(int x,int n){ return putere(x,n);}
int main()
{
cout<<"n=";cin>>n;
cout<<"x=";cin>>x;
cout<<"rez="<<putere(x,n);return 0;
}
Avem o declaratie forward a funcţiei G.
TEMĂ
Numele variabilelor locale și unde apar ?
Numele variabilelor globale si locatia?
PROBLEME REZOLVATE ca MODEL si TEMA SUBIECTUL 3
Metoda Backtracking (Metoda căutării cu revenire)
Algoritmul este prezentat de regulă în mod sintetic sub forma unui subprogram (o funcție) , se învață reținând doi algoritmi generici prezentati după cum se vede mai jos :-se rețin variantele recursivă și cea iterativă pentru algoritmul generic .
Mai intai
-Se genereaza o solutie partiala cu k componente (x1, ...., xk) si se verifica daca sunt indeplinite conditii de generare a urmatorului element al solutiei partiale (x1, ... .., xk +1)
Se continua cat timp k<=n , adica nu putem avea decat n elemente intr-o solutie .
S-multimea solutiilor , formata din elemente -perechi ordonate (x1. ... xn) unde
S este inclus in produsul cartezian de multimi X1xX2 .... xXn ceea ce inseamna ca primul element este intotdeauna ales din multimea-X1
al doilea din X2 ... ... ... .. ultimul din Xn.
Obs. In multe situatii practice multimile X1,....,Xn sunt identice (*generare de permutari ,aranjamente,combinari spre exemplu)
Se considera pt algoritmii generici de regula ca X = {1, ..., n}
ALGORITMUL RECURSIV
BACK void (int k);
if k = (n+1 )cout<< scrie Solutia altfel
init (k) / / reinitializeaza while succ (xk)
if condcont(k) back (k +1);
}
ALGORITMUL ITERATIV
k = 1;
init (k) / / componena xk a solutiei partiale pleaca de regula cu valoarea 0
while (k> 0) / / genereaza variante de posibile solutii
{
if (k == (n+1) / / A gasit o solutie
{
k = k-1;cout<<"scrie Solutia "<<x1..xn ;
while (k> 0) / / genereaza variante de posibile solutii
{
if (k == (n+1) / / A gasit o solutie
{
k = k-1;cout<<"scrie Solutia "<<x1..xn ;
}
else / / se continua cu generarea solutiilor partiale
if (xk) xk = succ (xk)
if condcont(k) k = k +1;
else / / au fost parcurse toate elementele din Xk
{
xk = 0 / / valoare de start
k = k-1
}
else / / se continua cu generarea solutiilor partiale
if (xk) xk = succ (xk)
if condcont(k) k = k +1;
else / / au fost parcurse toate elementele din Xk
{
xk = 0 / / valoare de start
k = k-1
}
}
Condcont - depinde de verificarea solutiei partiale - daca este true si solutia partiala cu k componte indeplineste conditiile de continuare se da startul pt gasirea componentei urmatoare x (k +1).
Reinițializarea lui xk se face de regulă cu 0 in cele mai multe aplicatii.
Aplicatia de mai jos va genera cu algoritmul iterativ toate permutarile de ordinul n :
Condcont - depinde de verificarea solutiei partiale - daca este true si solutia partiala cu k componte indeplineste conditiile de continuare se da startul pt gasirea componentei urmatoare x (k +1).
Reinițializarea lui xk se face de regulă cu 0 in cele mai multe aplicatii.
Aplicatia de mai jos va genera cu algoritmul iterativ toate permutarile de ordinul n :
Intrati pe https://www.onlinegdb.com si alegeti C++
Avem de generat toate permutarile de ordin n
#include<iostream>
using namespace std;
int x[200] , nr,i,n,k;
int condcont(int k)
{ int s=1;
for (i=1; i<= (k-1);i++)
if (x[i]==x[k]) s=0;
return s ;
}
int main()
{
cout<<"n= ";
cin>>n;
nr=0;
k=1;
//plecam cu generarea primei componente a SOLUTIEI
for (i=1;i<=n;i++) x[i]=0;
//initializare cu 0 a compontelor solutiei
while (k>0) {
if (k==n+1)
{
k=k-1;
nr=nr+1;
cout<<" solutia nr "<<nr<<": ";
//poti avea m multe solutii
for (i=1; i<=n;i++) cout<<x[i]<<" ";
cout<<"\n\a";
}
else {
if (x[k]<n)
{
x[k]=x[k]+1;
if (condcont (k))
k=k+1;
}
else
{
x[k]=0;
k=k-1;
};
}
}
return 0;
}
Avem de generat toate permutarile de ordin n
#include<iostream>
using namespace std;
int x[200] , nr,i,n,k;
int condcont(int k)
{ int s=1;
for (i=1; i<= (k-1);i++)
if (x[i]==x[k]) s=0;
return s ;
}
int main()
{
cout<<"n= ";
cin>>n;
nr=0;
k=1;
//plecam cu generarea primei componente a SOLUTIEI
for (i=1;i<=n;i++) x[i]=0;
//initializare cu 0 a compontelor solutiei
while (k>0) {
if (k==n+1)
{
k=k-1;
nr=nr+1;
cout<<" solutia nr "<<nr<<": ";
//poti avea m multe solutii
for (i=1; i<=n;i++) cout<<x[i]<<" ";
cout<<"\n\a";
}
else {
if (x[k]<n)
{
x[k]=x[k]+1;
if (condcont (k))
k=k+1;
}
else
{
x[k]=0;
k=k-1;
};
}
}
return 0;
}
Aplicații:
1.Problema incercati generarea tuturor permutărilor literelor de la a la z.
2.Se cere să generați toate aranjamentele de n luate câte m pt multimea {1,2,...n}
3.Se cere să generați toate combinările de n luate câte m pt multimea {1,2,....n}
4.Pt A,B,C - trei multimi cu cate 100 de elemente imaginati cum se vor genera toate perechiile ordonate de forma (ai,bi,ci)
INDICATIE
PT aranjamente : idee de rezolvare-observam ca trebuie adaptat codul la problemă
Pt combinări se iau elementele câte m distincte o singură dată.
La problema 4 functia de continuare (cea care verifica daca solutia partiala e corectă este tot timpul true, adică are mereu valoarea 1).
UN COD SIMPLIFICAT PENTRU GENERAREA COMBINARILOR ESTE :
GENERAREA COMBINARILOR DE N LUATE CATE M PT MULTIMEA {1,2,3,…n} SE observa ca se retin doar acele solutii care fata de codul de la generarea aranjamentelor sunt in ordine lexicografică.Urmăriți cu atenție zona marcată de mai jos
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<iostream>
using namespace std;
int x[200],
nr,i,j,n,k,m,s;
int condcont(int k)
{
int s=1;
for (i=1; i<=
(k-1); i++)
if (x[i]==x[k])
s=0;
return s ;
}
int main()
{
cout<<"comb de n=
";
cin>>n;
cout<<"luate cate m=
";
cin>>m;
nr=0;
k=1;
for (i=1; i<=n;
i++) x[i]=0;
while (k>0)
{
if
(k==n+1)
{ k=k-1; s=0;
for (i=1; i<=m; i++)
for(j=1; j<i; j++)
if(x[i]<x[i-1]) s=1;
if(s==0)
{nr=nr+1;printf("\n");cout<<" solutia nr "<<nr<<": ";
for(i=1;i<=m;i++) cout<<x[i];
}
}
else
{
if
(x[k]<n)
{
x[k]=x[k]+1;
if
(condcont (k))
k=k+1;
}
else
{
x[k]=0; k=k-1;
};
}
}
return 0;
}
PROBLEMA PROPUSĂ pt generarea combinărilor
INCERCATI sa preluati n si m din fisierul intrare.txt si sa
scrieti solutiile in iesire.txt
METODA Divide et impera
-algoritmul general al metodei se descrie cu o funcție in care A este un tablou , avem n elemente , avem un prim element p și un ultim element u și o soluție globală rez, solutii parțiale rez1. și rez2 . Metoda folosește recursivitatea in general .
Se utillizeaza si in implementari iterative .
METODA DIVIDE ET IMPERA
Algoritmul general al metodei :
void divimp(A,n,p,u,rez)
{
if u-p<€ atunci scrie rez //avem o rez directă a pb
else { divide(p,u,q);//împarte pb in doua subprobleme
divimp(A,n,p,q,rez1);
divimp(A,n,q+1,u,rez2);
Combine(rez1,rez2,rez);//combină rezultatele parțiale ale subproblemelor în rezultatul întregii probleme
}
Sa retinem ca imparte ca idee o problema foarte complicata in doua subprobleme mai simple , acestea se impart in continuare in alte subprobleme mai simple si asta recursiv pana se ajunge la o problema foarte usoara la care rezolvarea este foarte usor de realizat .
Aplicații
1. Pb turnurilor din Hanoi
Se pp că avem 3 tije și tb sa mutam n discuri de pe prima tija pe ultima , folosind că pivot tija din mijloc. Nu se pune un disc cu diametru mai mare peste altul cu diametru mai mic !
#include<iostream.h>
using namespace std;
using namespace std;
char a,b,c; //sunt cele 3 tije
int n ;
void h(int n , char a, char b , char c )
{
if(n==1) cout<<a<<c" "; // se muta direct
else
{
h(n-1,a,c,b);
cout<<a<<c;
h(n-1,b,a,c);
}
}
int main()
{
cout<<"n="; cin>>n;
h(n,'a','b','c'); return 0;
}
Explicatii - se creaza o schema foarte formala pentru a prelucra informatia folosind recursivitatea.
Astfel gandit formal algoritmul se poate vedea si asa ( util mai ales din punct de vedere mnemonic)
- se duc discurile mai mici de pe a pe b folosind ca disc pivot c-ul
-se duce discul cel mai mare de pe a pe c , unde c e destinatia
- se duc discurile mai mici ca diametru de pe b pe c folosind discul a ca pivot
Se poate demonstra inductiv acest algoritm daca se pleaca de la cazul cu 1 , apoi 2 discuri , apoi 3 si pp ca e adevarat pt un k oarecare si demonstram pt k+1.
Alt algoritm clasic al metodei este CAUTAREA BINARA .
Se presupune un vector sortat a cu n elemente si se da o cheie de cautare k .
Se cere sa gasiti elementul din vector cu aceeasi valoare cu k ( adica pozitia in vector i)
o functie care sa ilustreze metoda cautarii binare :
void binsearch(int p , int u, int k)
{
if (k==a [(u-p)/2] cout<<" pozitia este k ";
else
{
if(k<a[(u-p)/2] binsearch(p,(u-p)/2-1,k);
//cauta la stanga pe axa numerelor fata de mijlocul intervalului [p,u]
if(k>a[(u-p)/2] binsearch((u-p)/2+1,u,k);
//cauta la dreapta pe axa numerelor fata de mijlocul intervalului [p,u]
}
}
dupa ce declaram vectorul a cu n elemente apelul este binsearch(0,n-1,k)
PROBLEMĂ PROPUSĂ : SE CERE SĂ SCRIEȚI UN PROGRAM PENTRU aplicarea căutării binare pentru un sir sortat
!! Metodele de programare sunt ilustrate prin algoritmi generici. Acești algoritmi se aplică prin particularizarea codului sursa în funcție de problemă.
