Bonjour, je suis nouveau ici mais je fréquente le sdz depuis déjà 3 ans facilement !

Je suis maintenant à l'université en informatique, mais je rencontre déjà un petit problème suite à mon manque de math au lycée ^^'

Je dois exprimer cette fonction exprimant le nème nombre de Catalan mais par récurrence... je n'y arrive pas =/ et je dois absolument l'exprimer de cette manière là.



Si quelqu'un pouvait me donner la formule ET me l'expliquer correctement, ce serait très sympa =)

A très bientôt sur le sdz

Ba la formule tu l'as, qu'est-ce que tu ne comprends pas?

Ben, c'est comment la mettre en python ^^' soit j'obtiens 1 soit ça me dis qu'il y a une erreur =/
Je comprend pas comment mettre ça sous forme de fonction récursive ^^' pour faire ça avec python.

Quelqu'un saurait me donner le code?

Montre nous déjà le code que tu as écrit, on ne va pas te donner la solution comme ça (ça ne t'aiderait pas du tout) mais on peut t'expliquer pourquoi tu n'y arrives pas et comment faire.

Maxibolt a raison, montre ton code, le but est de travailler, pas d'avoir la réponse toute cuite

Ok, voilà à peu près ce que j'ai (mon code se trouve sur mon pc qui est à 90km de moi... je squatte un pc là).

def catalan(n):
    if n == 0:
        return 1
    else : 
        i = 1
        rep = catalan(i)*catalan(n-i)
        i=i+1
        return rep

Je m'y retrouve pas avec ces trucs de récursivité >.< il doit y avoir une erreur quelque part...

Citation : kagurei

Je m'y retrouve pas avec ces trucs de récursivité >.< il doit y avoir une erreur quelque part...

Effectivement... comment faire la somme si tu ne fais pas de boucle ?

def catalan(n):
    if n <= 1:
        return 1
    else : 
        return sum( catalan(i)*catalan(n-i) for i in xrange(1,n) )

Note qu'une petite mise en cache ne serait pas de trop...

ah je vois, donc sum = grand sigma donc?

sum( catalan(i)*catalan(n-i) for i in xrange(1,<gras>n</gras>) )

ça ne dois pas être n-1 au lieu de n comme tu as mis? car au-dessus du sigma, il y a n-1 et pas n

Et il n'y a pas moyen de faire autrement qu'avec une boucle? Car on ne nous demande pas de boucle (on est pas censé les avoir vue... même si je les connais déjà grâce au PHP).

En tous cas merci beaucoup

wikipedia

Ils vous apprennent Python en mettant la récurrence avant les boucles ? Strange and stupid.

Sinon, ben, reprogramme la somme avec une fonction récursive. Ou essaie de triturer un peu la suite : on peut s'en sortir plus intelligemment.

Citation : Maxibolt

Ils vous apprennent Python en mettant la récurrence avant les boucles ? Strange and stupid.

Sinon, ben, reprogramme la somme avec une fonction récursive. Ou essaie de triturer un peu la suite : on peut s'en sortir plus intelligemment.

Oui, on nous apprend la récursivité avant les boucles... je comprend pas pourquoi, les boucles sont beaucoup plus simples...

je vois pas comment changer la boucle dans la fonction qu'on m'a donnée =/ la récursivité c'est pas trop mon truc...

C'est pas que c'est plus simple, c'est surtout que la récursivité n'est pas du tout bien implémentée en Python et que ça stack overflow dès qu'on va un peu trop loin. En ocaml (par exemple) on n'utilise presque que ça, au contraire.

Je suis un peu pressé là, mais essaie de te dire "si j'ai le résultat pour n - 1, comment avoir celui pour n ?"

Merci, en tous cas je viens de tester la formule (j'ai du installer python sur le pc que je squatte...) et ça marche, pas besoin de mon n-1 sinon ça foire =)

Je vais garder votre code et maintenant je vois comment faire des sigmas en python =)

merci à tous, si j'ai d'autres question, je n'hésiterai pas

- xrange( début, fin ) va de (début) à (fin-1) contrairement au sigma mathématique où les bornes sont incluses.

- sum() ne correspond pas vraiment au sigma, c'est juste la somme de la liste ou du générateur que tu lui donnes.

> Et il n'y a pas moyen de faire autrement qu'avec une boucle

Comme il y a des factorielles, et que le seul moyen de calculer une factorielle est ... de la calculer, tu auras obligatoirement une boucle quelque part (ou une boucle implémentée sous forme de récursion, mais en python c'est foireux, pas de tail recursion !)

J'ai encore une question, si on veut faire avec une boucle while, comment faire?
j'ai ça mais je n'obtiens pas les valeurs désirées...

def catalan(n):
    i = 1
    sum = 0
    while i < n:
        sum = sum + (catalan(i)*catalan(n-i))
        i = i + 1

    return sum

Où est mon erreur? car je la trouve pas =/

Réfléchis bien aux bornes de la somme et à la condition d'arrêt de ta boucle while.

Je ne vois toujours pas =/

def catalan(n):
    i = 1
    sum = 0
    while i != n-1:
        sum = sum + ((i)*(n-i))
        i = i + 1

    return sum

ce ne serait pas plutôt quelque chose comme ça? ça me met une erreur si je laisse catalan(i)*catalan(n-i) =/

Hum, j'ai mal lu la formule, il y a effectivement un -1 qui traîne (ce qui est logique d'ailleurs). Je ne vois pas où est le problème, tu es sûr de ne pas obtenir les bonnes valeurs ?

Oui, j'obtiens pour n = 10, 165 au lieu de 4862... petit problème >.< quelqu'un saurait me donner le code exact? car je galère trop >.<

Ah mais si je sais. Regarde le cas de base.

Comme Maxibolt l'a dit, ton cas de base est faux, enfin je dirais plutôt qu'il est inexistant. Du coup là catalan(1) va te retourner 0.
Si tu mets ensemble le premier code que tu as posté (en réglant le cas de base lorsque n est inférieur ou égal à 1 et non égal à 0:

Citation : kagurei

def catalan(n):
    if n == 0:
        return 1
    else : 
        i = 1
        rep = catalan(i)*catalan(n-i)
        i=i+1
        return rep

et le suivant :

Citation : kagurei

def catalan(n):
    i = 1
    sum = 0
    while i < n:
        sum = sum + (catalan(i)*catalan(n-i))
        i = i + 1

    return sum

tu devrais trouver la bonne réponse.
Par contre change le nom de ta variable sum , vu que c'est une fonction de Python. C'est pas dramatique pour ce programme là, mais si tu crées cette variable, tu ne pourras plus te servir de la fonction sum donc dans un cas où tu pourrais en avoir besoin par la suite ça risque de poser problème.

Sinon, i = i + 1 peut s'écrire i += 1 , c'est plus joli

J'ai ça maintenant :

def catalan(n):
    i = 1
    rep = 0
    while i < n:
        if n ==0:
            rep = 1
        else :
            rep = rep + (catalan(i)*catalan(n-i))
            i = i + 1

    return rep

mais ça me retourne 0 =/

C'est normal. Essaie de dérouler l'exécution de catalan (3) pour comprendre.

Je comprend d'un point de vue papier pourquoi j'botiens 0 can il y a le n-i qui me donne 0 à chaque fois... mais comment faire pour avoir la réponse souhaitée? Je bloque vraiment là...

Il y a deux problèmes. Le premier, c'est que si tu demandes catalan(1), il va te renvoyer 0 (je te laisse voir pourquoi). Mais changer la condition de la boucle ne va pas le résoudre, puisque tu as besoin de ce i < n pour les cas non-triviaux.
Le deuxième problème, qui est lié, c'est que tu as mis le cas de base dans la boucle. C'est inutile (si on arrive à ce cas là, on a le résultat et on peut le renvoyer directement, pas besoin de boucler), et ici ça t'empêche qu'il soit correctement utilisé (cf. problème précédent).

def catalan(n):
    if n == 0:
       rep = 1    
    else : 
        i = 1
        rep = 0
        while i < n:
            rep = rep + (catalan(i)*catalan(n-i))
            i = i + 1

    return rep

Voilà ce que j'ai en corrigeant ta deuxième suggestion mais pour le 1er cas, je ne vois vraiment pas =/ franchement, y a pas moyen de me donner la solution et de me l'expliquer? car je galère vraiment avec les boucles...

C'est justement parce que tu galères que je ne veux pas te la donner, tu apprendras beaucoup plus en l'écrivant toi-même (quitte à ce qu'on t'explique après, quelquefois on a du mal à comprendre ce qu'on écrit, mais ça reste bien plus utile).
Bon, là, c'est plus une faute d'inattention, tu t'es trompé sur le cas de base : c'est n == 1, pas n == 0. Si tu remplaces ça, tout marche nickel. Tu as compris ?

Si tu ne comprends pas les boucles, je te suggère de faire des exercices plus simples avant de commencer : là ça mélangeait récursivité et boucles, c'est pas évident quand on débute.

Déjà ton code colle pas avec la définition : tu as C(1) = 1, mais dans ton code tu renvoie 1 pour n == 0 (donc C(0) = 1)

EDIT

****** de m****... j'avais fait l'erreur dans le cas de base et je m'en suis pas rendu compte pendant tout ce temps J'suis trop con, mnt ça marche nickel...

Merci de me l'avoir fait remarqué =D

Hum, tu sais, avant ça ne devait pas marcher même avec cette correction. C'est du "détail" ça.