Inscription / Connexion Nouveau Sujet
appels récursifs dans les coeeficients du binome
bonjour, je bloque sur un probleme: on ap rogrammé deux algorithmes de calcul de la combinaison "p parmi n"
1) soit binome = fonction
n 0 -> 1
n p quand n<p -> 0
n p -> binome (n-1) (p-1) + binome (n-1) p
2) Soit binome2 = fonction
n 0 -> 1
0 p -> 0
n p -> binome2 (n-1) (p-1) + binome (n-1) p.
Je dois compter le nombre d'appels récursifs pour chacune des deux fonctions (par ex pour 1 parmi 1 on fait 0 parmi 0 + 0 parmi 1 soit en tout trois appels récursifs).
Et j'arrive pas à trouver un résultat que je pourais essayer ensuite de motn rer pr récurrence j'ai jusdte compris que la premiere formule (binome) fait intervenir un seul nombre de combinaison et binome2 fait intervenir partie entiere (p/2) nombres de combinaisons...
Pourriez vous me guider svp 
merci d'avance.
Bonsoir !
pour les deux tu commence comme sa :
tu apelle Cpt(n,p) le nombre d'apelle de binome n p
tu a pas construction Cpt(n,p) = CPt(n-1,p)+Cpt(n-1,p-1) + 1
ie une recurence affine, il faut soustraire une sollution particulière pour ce ramener a l'equation homogène... ici -1 est sollution particuliere : -1 -1 +1 =-1
donc on pose U= Cpt(n,p)+1
et on a U(n,p)=U(n-1,p)+U(n-1,p-1)
cependant malheuresement cette equation contrairement au recurence lineaire habituelle a comme ensemble de sollution un espace vectorielle de dimmension infinit :S il est donc delicat de la ressoudre dans le cas general...
cependant tu peut remarqué que pour le premier probleme avec les valeur initial que tu a 2*(P parmi n+1) est sollution donc comme cette recurence definit une unique fonction
Cpt1 = 2*(p parmi n+1) - 1
pour le 2e c'est beaucoup plus sompliqué... il y a beaucoup de valeur initial a prendre en compte :S ...
Annuler
connectez vous
analyse en post-bac