Discussion :

[pazze]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[Spout]

Salut,

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

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?

[pazze]

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 .

[koala01]

Salut,

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

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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é , et au moins, ca permettra de comprendre l'idée )

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

[pazze]

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.

[koala01]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[pazze]

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 ?

[koala01]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 */
    }
}

[pazze]

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,...

[yan]

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.

[pazze]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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,...

[yan]

y as une erreur ici

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

regarde bien ta formule

[pazze]

J'aurais tendance à mettre

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

mais apparemment c'est pas ça.

[yan]

Dans

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

je dirais que ce qui est en gras est faux

[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

[yan]

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

[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...

[yan]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[pazze]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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...

[pazze]

Ah si voila c'est somme=0;



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

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.