Fonction récursive et algorithme

[Manaus]

J'ai cette fonction récursive :
C(0) = 1
C(n+ 1) = ;) C(i). C(n - i)

Je dois calculer C(n) pour n ;) [1...5]
ensuite écrire un algorithme qui calcule C(n).

Je ne sais cependant pas du tout comment commencer pour calculer C(n) :mur:

Merci pour votre aide!!

[ampholyte]

Bonjour,

On te demande en fait de calculer C(1), C(2), C(3), C(4) et C(5)

Pour le premier il suffit de remplacer dans la formule :



Pour C(2), même principe :



etc sachant que tu connais C(0)

[Manaus]

Bonjour,

On te demande en fait de calculer C(1), C(2), C(3), C(4) et C(5)

Pour le premier il suffit de remplacer dans la formule :



Pour C(2), même principe :



etc sachant que tu connais C(0)

Oh d'accord je vois! Je n'avais pas compris ça comme ça. Merci beaucoup :++:

As tu une idée pour l'algorithme?

[ampholyte]

Pour l'algorithme, il suffit d'appliquer ce que tu fais à la main.

Personnellement je verrais une double boucle :

- La première te permettant d'accéder à ton rang n et stockant le résultat de la seconde dans un tableau.

- La seconde te permettant de calculer pour chaque valeur de la boucle précédente, C(i) (donc jusqu'à ton C(n), ce que tu cherches).

[fatal_error]

elo,

ou bien juste appliquer betement la formule donnée :

Code: Tout sélectionner

procedure C(Entier n): Entier
 si n = 0
   retourner 1
 finsi
 Entier resultat = 0;
 pour i=0 à n
  Entier = Entier + C(i)*C(n-i)
 finpour
 retourner resultat
fin

c'est pas optimisé tout ca, mais c'est pas non plus demandé d'optimiser...

[ampholyte]

elo,

ou bien juste appliquer betement la formule donnée :

Code: Tout sélectionner

procedure C(Entier n): Entier
 si n = 0
   retourner 1
 finsi
 Entier resultat = 0;
 pour i=0 à n
  Entier = Entier + C(i)*C(n-i)
 finpour
 retourner resultat
fin

c'est pas optimisé tout ca, mais c'est pas non plus demandé d'optimiser...

Oui tout à fait, c'est vrai que la version récursif est sûrement plus visuelle, mais la version avec tableau est peut-être plus rapide (mais comme on ne cherche pas forcément une version optimisée ...).

Après vu le titre du sujet, je pense que ta solution est la plus pertinante =).

[Manaus]

Merci beaucoup à vous deux!! fatal error je pense que la solution que tu me propose est très bien

[Ben314]

Tel quel :

Code: Tout sélectionner

procedure C(Entier n): Entier
 si n = 0
   retourner 1
 finsi
 Entier resultat = 0;
 pour i=0 à n
  Entier = Entier + C(i)*C(n-i)
 finpour
 retourner resultat
fin

j'ai un peu peur que ça boucle... un bon moment... vu que la fonction C(?) se réapelle elle même pour... la même valeur du paramètre (lorsque i=0 et i=n)

Manaus a pas précisé d'où à où il fallait faire la somme, mais un "somme de i=1 à n-1" semblerais plus plausible.
Ou alors c'est de 0 à n-1 et on fait le produit C(i)*C(n-1-i)