Imprimă pagina - combinari(n,p) [versiune recursiva, python]

Stim ca (definitia generala a combinari de n luate cate p):
(http://bocan.andrei.googlepages.com/comb.jpg)

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:
(http://bocan.andrei.googlepages.com/comb1.jpg)

si ca definitia generala se poate rescrie sub forma:
(http://bocan.andrei.googlepages.com/comb2.jpg)

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

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++ !

infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: Bocan Andrei din Februarie 13, 2009, 16:33:45