Nombre de Catalan

Bonjour ,

Je dois créer une fonction qui calcule les nombres de Catalan de façon récursive à partir de cette formule http://upload.wikimedia.org/math/b/a...e376993a27.png

J'ai déjà essayé de la créer mais je n'y arrive pas

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

void catalan (int solution[],int taille) { int k=0,l=1,somme=0; solution[0]=1; /*   solution[1]=solution[0]*solution[0];   solution[2]=solution[0]*solution[1]+solution[1]*solution[0];   solution[3]=solution[0]*solution[2]+solution[1]*solution[1]+solution[2]*solution[0];   solution[4]=solution[0]*solution[3]+solution[1]*solution[2]+solution[2]*solution[1]+solution[3]*solution[0];*/     for (int i=1;i<=taille-1;i++) {   somme+=solution[k]*solution[i-l]; k++; l++; solution[i]=somme;   } affichageVecteurDEntier(solution,taille);   }

---

pour le moment , j'ai ce code mais ça ne fonctionne pas , et je ne vois pas de quelle façon résoudre mon problème.

Une idée ?

merci.

Salut,

Ton lien ne fonctionne pas. Est-ce la même chose que le nombre de Catalan décrit ici?

Citation:

---

Envoyé par pazze

j'ai ce code mais ça ne fonctionne pas

---

Qu'entends-tu par là? Tu as des erreurs? Des plantages?
Est-ce un problème de codage C++ que tu rencontres ou est-ce un problème d'adaptation de l'algorithme?

Le lien devrait marcher maintenant.

en fait , je n'arrive pas à trouver la bonne suite.
Je crois que c'est un problème d'adaptation de l'algorithme .

Salut,

Déjà, si tu dois effectuer un traitement récursif, il faudrait peut etre utiliser une fonction... récursive :aie:

En programmation, une fonction est dite récursive quand... elle s'appelle elle-même ;)

Pour sortir de cet appel qui pourrait, si les capacités de l'ordinateur le permettaient, durer jusqu'au jugement dernier, il y a lieu de tester ce que l'on appelle "le cas de base", qui, typiquement, renvoie 1 ou 0 (ici, le cas de base est C0 qui renvoie 1), et de veiller, en dehors de ce cas de base, à rappeler la fonction de manière à tendre vers ce cas de base.

Ainsi, et bien que la récursivité ne soit clairement pas la meilleure solution pour ce calcul précis, tu pourrais envisager une fonction récursive qui calcule la factorielle d'un nombre comme suit:

Code:

---

1 2 3 4 5 6 7 8 9 10 11

int factorielle( int i) { /*le cas de base : si i = 1, on renvoie 1 */ if(i == 1) return 1; /* dans tous les autres cas, on appelle la fonction en faisant en sorte   * que i tende vers 1, mais en respectant le principe de la factorielle   */ return i*factorielle(i-1); }

---

(je sais, il y a quantité d'autres exemples qui auraient pu servir à meilleur escient, mais je suis un peu fatigué :aie:, et au moins, ca permettra de comprendre l'idée :D)

Maintenant que tu as (je l'espere) compris le principe, "YAPUKA" l'adapter à ton problème de calcul des nombres catalans :D

Le problème , c'est que je dois utiliser une fonction void qui reçoit un vecteur et sa taille. Et je dois faire tout les calculs dans ce même vecteur.

Ca peut aussi fonctionner avec une fonction qui ne renvoie rien... le tout étant que la fonction ne soit pas rappelée une fois le cas de base atteind ;)

Cela pourrait donner quelque chose comme

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

void Catalant(int* tab, int size) { /* testons le cas de base */ if(size==0) { tab[0]= 1; } else { /*remplir le tableau en tendant vers un size == 0   * avec les appels à Catalan ici   */   } }

---

Lorsque je parle du retour de la fonction, cela peut aussi impliquer qu'elle ne se rappelle simplement pas elle-même ;)

Je ne comprend pas comment on pourrait remplir le tableau en tendant vers 0 puisque pour chaque nombre de catalan , on a besoin du précédent , on devrait donc partir du cas 0 ,non ?

C'est là que la magie opère...

Si tu appelle la fonction en lui passant size-1 AVANT d'essayer de remplire une case, la case précédente sera remplie quand tu tentera d'y accéder...

Cela donnerait quelque chose dans le genre de

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

void Catalan(int *tab, int size) { /* le cas de base: size == 0 */ if(size == 0) { tab[0]= 1; } /* si ce n'est pas le cas de base */ { /*nous appelons la fonction en tendant vers le cas de base   */ Catalan(tab,size-1); /* à partir d'ici, tu peux calculer la case qui t'intéresse */ } }

---

Je n'arrive pas à appliquer cette façon de faire.

Mais je me souviens qu'on avait aussi du chercher les nombres de Fibonacci par récurrence et nous n'avions pas du faire comme tu me le dis.

En fait , selon moi , j'ai juste commis quelques erreurs dans le "for" de mon code, mais je me trompe peut-être.

Je devrais obtenir comme suite : 1,1,2,5,14,42,132,429,1430,...

mais j'obtiens les puissance de 2 : 1,1,2,4,8,16,...

Salut
Il ne manquerais pas une boucle dans ton code??
Même si dans ton cas, tu peut te passer d'une fonction récursive,

+1 pour lafonction récursive.

j'ai essayé de rajouter une boucle , ça ne marche toujours pas.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

void catalan (int solution[],int taille) { int somme=0; solution[0]=1; /*   solution[1]=solution[0]*solution[0];   solution[2]=solution[0]*solution[1]+solution[1]*solution[0];   solution[3]=solution[0]*solution[2]+solution[1]*solution[1]+solution[2]*solution[0];   solution[4]=solution[0]*solution[3]+solution[1]*solution[2]+solution[2]*solution[1]+solution[3]*solution[0];*/ for (int i=0;i<taille;i++) { for (int j=i;j>=0;j--) { somme+=solution[i]*solution[j]; } solution[i+1]=somme; } }

---

j'obtiens : 1,1,3,18,432,...

y as une erreur ici

Code:

---

1 2	somme+=solution[i]*solution[j];

---

regarde bien ta formule

J'aurais tendance à mettre

somme+=solution[i]*solution[j-1]

mais apparemment c'est pas ça.

Dans

Citation:

---

somme+=solution[i]*solution[j];

---

je dirais que ce qui est en gras est faux

j'ai essayé presque tout , je me rapproche de la bonne suite mais c'est toujours pas ça

somme+=solution[j]*solution[j];

donne la suite la plus proche de la bonne

Citation:

---

Envoyé par pazze

j'ai essayé presque tout , je me rapproche de la bonne suite mais c'est toujours pas ça

somme+=solution[j]*solution[j];

donne la suite la plus proche de la bonne

---

Regarde bien les indices utilisés pour faire la somme

D'après la formule , chez moi :

le n = i +1;
donc n-1 = i;
mais j'ai du mal à voir à quoi correspond le i=0.

ce qui me pose problème pour la formule...

Citation:

---

Envoyé par pazze

D'après la formule , chez moi :

le n = i +1;
donc n-1 = i;
mais j'ai du mal à voir à quoi correspond le i=0.

ce qui me pose problème pour la formule...

---

ton problème est surtout dans les indices que tu utilise dans ta multiplication...
Si je t'écrit ta formule comme cela, peut être comprendra tu mieux
C[n] = somme( i =[0;n-1]) { C[a] * C[b]};
avec
a = i
b = n-1-i

Tu devrais renommé les variables de tes boucles.

Code:

---

1 2 3 4 5 6 7 8 9

for (int n=___;n<taille;++n) { ______ for (int i=____;i< ___ ;++i) { somme+=solution[__] * solution[__]; } _________ }

---

As toi de comprendre ce qui faut remplacer et adapter

pour le moment , j'ai complété comme cela

Code:

---

1 2 3 4 5 6 7 8 9

for (int n=;n<taille;++n) { _______ for (int i=;i < ;++i) { somme+=solution[] * solution[]; } ______; }

---

Je suis bien parti ou pas ? Ensuite , je vois pas ce que je pourrais mettre sur le _____ restant...:cry:

Ah si voila c'est somme=0;

:lol:

Merci beaucoup pour ton aide ^^ tu m'as sauvé :D

Enfin c'est pas vraiment terminé , maintenant quand je demande un grand nombre d'éléments , j'en obtiens des négatifs , je crois pas que ça soit normal.

Tu as donc les bon résultats?
peut tu mettre ta solution?

Code:

---

1 2 3 4 5

void catalan (int solution[],int taille) { solution[0]=1;   }

---

Voila ma fonction.

Citation:

---

Envoyé par pazze

Voila ma fonction.

---

:king:
Maintenant, tu devrais essayer avec une fonction récursive.
Et utilise un std::vector, mais je ne pense pas que tu es déjà le droit :roll:

Je devais le faire obligatoirement avec cette fonction la définie telle qu'elle et avec la formule que j'ai donnée , sinon je l'aurais fais avec les factorielles , mais je vais essayer avec une fonction récursive ;)

tu sais pourquoi j'obtiens des négatifs dans ma suite ?

Citation:

---

Envoyé par pazze

tu sais pourquoi j'obtiens des négatifs dans ma suite ?

---

?
dépassement de capacité du int peut être?
Y as déjà une chose que tu peut faire, c'est d'utiliser des unsigned int au lieu des int car tout est positif

[edit]
c'est bien un dépassement de capacité du int. avec les unsigned int, tu auras le même problème

ok merci beaucoup , je vais faire ça.

merci encore pour ton aide.

ho le nombre catalan tu ne serais pas à ULB en Ba 1 :yaisse2:
bonne chance . . . .:arf: