combinari(n,p) [versiune recursiva, python] - need help

[•andress]

Stim ca (definitia generala a combinari de n luate cate p):



Pornind de la aceasta definitie putem scrie urmatoarea functie:

Cod:

def combinari1(n,p):
	return factorial(n)/(factorial(p)*factorial(n-p))

care se va folosi de o functie factorial(n) - consideram ca a fost declarata anterior.


Functia de mai sus mai poate fi scrisa intr-o versiune iterativa astfel:

Cod:

def combinari2(n,p):
	x=1
	for i in range(n-p+1,n+1):
        x*=i
    y=1
    for i in range(2,p+1):
        y*=i
    return x/y

Putem demonstra ca:


si ca definitia generala se poate rescrie sub forma:



Pornind de la aceasta ultima forma a definitiei, trebuie sa scriu o versiune recursiva a functiei combinari(n,p). Astept sugestii si propuneri. Multumesc

[•alexandru92]

II destul de ineficient sa calulezi recursiv deoarece se calculeaa de mai multe ori aceleasi valori
Uite aici o implementare

Cod:

long combinari(int n,int p)  //n-nr de  elemente, k-cate numere contine o combinatie
   {if(p==1) return n;   //luam cazutile particulare, si la cele care punem stop recursivitati.
    if(p==0||p==n) return 1;
    return combinari(n-1,p)+combinari(n-1,p-1) ;//si acuma apelez formula pe care ai scris-o u :)
   }

II in c++ !