Le même algo en plus short, je trouve pas forcément ça plus lisible... :

def pascal(ligne):
    tab = [[1]]
    for n in range(1, ligne+1):
        tab.append([1] + [tab[n-1][p]+tab[n-1][p-1] for p in range(1,n)] + [1])
    return tab[ligne][ligne//2]

Par contre j'ai atteint ma limite en compression de code pour cette implémentation... la relation de récurrence d'une ligne à l'autre me bloque.

Citation : NoHaR

Le même algo en plus short, je trouve pas forcément ça plus lisible... :

def pascal(ligne):
    tab = [[1]]
    for n in range(1, ligne+1):
        tab.append([1] + [tab[n-1][p]+tab[n-1][p-1] for p in range(1,n)] + [1])
    return tab[ligne][ligne//2]

Le problème est justement que l'algo est exactement le même. Sinon, je trouve pas que tab.append([1] + [tab[n-1][p]+tab[n-1][p-1] for p in range(1,n)] + [1])
soit particulièrement lisible.

Je sais, l'algo à la base est moisi parce qu'il fait construire tout le triangle en mémoire.
Tu préfères peut-être la solution récursive qui applique directement la formule du binôme ?

def pascal(ligne):
    binom = lambda n,p: 1 if p==0 or p==n or n==0 else binom(n-1, p) + binom(n-1, p-1)
    return binom(ligne, ligne//2)

Comme cela a été dit précédemment, les solutions récursives sont à éviter en Python parce qu'elles font vite exploser la pile, m'enfin c'est vrai que c'est un peu plus élégant que de construire explicitement le triangle de Pascal en mémoire.

Citation : NoHaR

Je sais, l'algo à la base est moisi parce qu'il fait construire tout le triangle en mémoire.

"moisi", le terme est un peu fort mais c'est effectivement ça le problème.

Citation : NoHaR

Tu préfères peut-être la solution récursive qui applique directement la formule du binôme ?

Non, je n'avais pas en tête une solution récursive pour les trois raisons suivantes :

-- il existe une solution itérative simple
-- les débutants ne sont pas forcément à l'aise avec les fonctions récursives qui ont leurs côtés un peu magiques
-- il est vrai que Python oblige à utiliser la récursivité avec précautions pour la raison que tu as indiquée.

"les débutants ne sont pas forcément à l'aise avec les fonctions récursives qui ont leurs côtés un peu magiques"

Ça dépend quels débutants. Les débutants qui ont commencé par Python, probablement, parce que tous les tutos commencent par les boucles. Mais en soi, ce n'est pas plus difficile à comprendre qu'une boucle (voire même plus simple).

Citation : Maxibolt

Mais en soi, ce n'est pas plus difficile à comprendre qu'une boucle (voire même plus simple).

"en soi", autrement dit en théorie, peut-être. En pratique, je ne suis pas sûr qu'il en soit de même. On dit souvent :



ça exprime bien la magie de la récursivité. Une fois que tu connais le truc, ce n'est plus magique, c'est sûr. En attendant, faut arriver à comprendre le truc. La récursivité c'est un état d'esprit, ça se travaille et ce n'est pas donné à tout le monde (certain font un blocage complet).

"On dit", effectivement, quelqu'un l'a dit. Sans doute quelqu'un qui avait commencé par les boucles.

Pour un débutant complet, la récursivité n'a aucune raison d'être plus compliquée. Il y a aussi des gens qui font des blocages complets sur les boucles (et j'en connais de ceux là qui ont bien compris la récursivité).

Citation : candide

ce n'est pas donné à tout le monde (certain font un blocage complet).

Je me reconnaîs dans cette phrase Je haïs la récursivité, j'ai beau lire les tutoriels, ça ne rentre pas ...

Citation

Je haïs la récursivité

Pourquoi? Qu'est-ce qui te gêne? Connais-tu la particularité d'une fonction récursive?

Citation

lire les tutoriels

Avant de lire le tuto, il faut voir l'intérêt d'une fonction récursive

Bon, j'ai réfléchi dans le train à la solution qui te conviendrait le plus.
Il a fallu pour ça que je me demande comment j'implémenterais intelligement le truc en C sans les combinaisons.
J'ai abouti à la solution en-place suivante, je vois pas "mieux" dans les critères que tu as fixés :

def pascal(n):
    tab = [0 for _ in range(0,n//2)] + [1] # Tableau de longueur n/2+1 [0,0,...,1]
    for _ in range(n):                     # Calcul de la demi-ligne d'indice n
        for i in range(n//2):         
            tab[i] += tab[i+1]
    return tab[0]

Sinon, pour le fun, un petit one-liner basé sur la solution récursive.

pas = lambda n,p=None: 1 if p is not None and p*n==0 or p==n else pas(n,n//2) if p is None else pas(n-1,p) + pas(n-1, p-1)

C'est peut-etre une question bête, mais au moins je le saurais, car je l'ai déjà vu.



Merci

Le underscore sert à 'ignorer'.

En gros, dans la première boucle, si j'avais mis 'k' à la place, j'aurais collé la valeur dans ma variable k à chaque itération, mais je ne l'aurais pas utilisée. Pour éviter ce genre de truc (le fameux warning "unused variable k" de pylint), on peut placer des underscores.

On peut l'utiliser aussi pour sélectionner les éléments d'un tuple qui nous intéressent :

>>> _, _, valeur, _ = ("m'en fous", "m'en fous aussi", "ma valeur", "rien à battre")
>>> print(valeur)
ma valeur

Citation : NoHaR

Bon, j'ai réfléchi dans le train à la solution qui te conviendrait le plus.
Il a fallu pour ça que je me demande comment j'implémenterais intelligement le truc en C sans les combinaisons.

Cette fois tu as poussé la réduction de code un peu loin et cela nuit à la lisibilité même si je reconnais c'est subjectif . Effectivement on a juste besoin d'une demi-ligne.

Voilà comment moi j'aurais écrit le code :

n = 30 # juste un exemple
p = [1, 1]

for lig in range(2, n + 1):
    q = [1] * (lig + 1)
    for col in range(1, lig):
        q[col] = p[col] + p[col - 1]
    p = q
print (max(q))

155117520

Citation : NoHaR

Sinon, pour le fun, un petit one-liner basé sur la solution récursive.

Concernant ta première fonction récursive, crois-tu qu'il faut la donner telle quelle, non accompagnée d'une petite explication ?

Pourquoi "lig" et "col" ? On aurait largement la place d'écrire "ligne" et "colonne" sur les lignes, et ce serait plus clair et lisible (là, on commence par lire le code pour se demander ce qu'est lig, avant de voir le col).

Citation : candide

Cette fois tu as poussé la réduction de code un peu loin et cela nuit à la lisibilité même si je reconnais c'est subjectif . Effectivement on a juste besoin d'une demi-ligne.

Ben je n'ai même pas réduit explicitement le code... j'ai traduit l'algo tel que j'y ai pensé dans le train :
-> on alloue une demi-ligne remplie de 0 qui termine par un 1
-> on la remplace 'n' fois de suite par la ligne 'en-dessous d'elle' en suivant l'algo donné dans l'énoncé
-> la première valeur est celle qu'on cherche

Citation : candide

Voilà comment moi j'aurais écrit le code :

n = 30 # juste un exemple
p = [1, 1]

for lig in range(2, n + 1):
    q = [1] * (lig + 1)
    for col in range(1, lig):
        q[col] = p[col] + p[col - 1]
    p = q
print (max(q))

Pour le coup, c'est moi qui ai plus de mal à lire ta version. C'est très subjectif en effet.

Citation : candide

Concernant ta première fonction récursive, crois-tu qu'il faut la donner telle quelle, non accompagnée d'une petite explication ?

OK, je poste l'explication.

Dans le triangle de pascal, le nombre à la colonne 'p' et à la ligne 'n' est ce que l'on appelle le binôme (n,p).
Sans chercher à le calculer directement, le binôme se caractérise par la "formule du binôme" :
bin(n,p) = bin(n-1,p-1) + bin(n-1,p)

En regardant bien cette formule, on voit bien que c'est de cette manière que l'on construit chaque élément du tableau de Pascal.

Pour trouver la fonction récursive, il faut d'abord déterminer la condition d'arrêt :
bin(n,p) == 1 si:
- n = 0
- p = 0
- n = p (p ne peut jamais être plus grand que n)

Si l'on n'est pas dans le cas "d'arrêt", il suffit d'appliquer la formule du binôme, qui est récursive.
La fonction se traduirait donc, lisiblement en Python, par:

def binome(n,p):
    if n * p = 0 or p >= n:
        return 1
    else:
        return binome(n-1, p-1) + binome(n-1, p)

Dans le one-liner, j'ai collé tout ça en une seule ligne, et j'ai rajouté une condition: si on ne fournit pas l'argument p, alors on calcule binome(n, n/2), c'est-à-dire le coefficient le plus élevé de la ligne n.

Voilà.

Citation

Le underscore sert à 'ignorer'.

Je m'en doutais, je trouve ça très moche dans un code, je préfère une bonne vieille variable malgré tout

C'est moins sémantique... Et moins propre.

En console :

>>> _,_,a,_=4,2,5,8
>>> a
5
>>> _
8
>>> del _
>>> del _
Traceback (most recent call last):
  File "<interactive input>", line 1, in <module>
NameError: name '_' is not defined
>>> _
8
>>> 7
7
>>> _
7

En console, il faut faire attention : _ sert aussi à récupérer le dernier résultat renvoyé par Python. Mais de toute façon, on n'utilise la console que pour faire des tests en temps normal, donc on n'a pas ce genre de problème

_ est aussi un nom de variable valide. Il n'ignore pas une valeur; n'est pas comparable au _ d'Ocaml, Haskell & Co.

Citation : EMC1

_ est aussi un nom de variable valide. Il n'ignore pas une valeur; n'est pas comparable au _ d'Ocaml, Haskell & Co.

Mais c'est comme ça que l'on s'en sert, sémantiquement et par convention en Python.
Disons que c'est une "bonne pratique" qui se traduit dans une boucle par le fait que l'on va juste faire 'n' fois la même opération exactement. C'est une manière conventionnelle de le dire aux autres programmeurs qui vont lire le code.

EMC1, explique moi :

L'intérêt d'ignorer une valeur si c'est vouloir la connaître par la suite?

Ce que je pense :

a=5 # la seule variable qui nous intéresse

Un intérêt peut-être, rendre une variable anonyme et encore

Voila

Bonsoir,

Voilà ce que j'ai codé en 3 min. J'espère que ce code sera conforme au KISS tant apprécié ici!

def pascal(n, liste = [1]):
    if len(liste) > 1 and liste[1] >= n:
        return max(liste)
    else:
        liste = [0] + liste + [0]
        newliste = []
        for i in range(0, len(liste)-1):
            newliste = newliste + [liste[i]+liste[i+1]]
        return pascal(n,newliste)

print pascal(10)

Je planche sur une seconde version sans succès ce qui me laisse croire que cette dernière n'est pas KISS

Citation : fred1599

Ce que je pense :

a=5 # la seule variable qui nous intéresse

Un intérêt peut-être, rendre une variable anonyme et encore

Voila

Ouais... mais nan.
Imagine que tu utilises une API dont une fonction te retourne un tuple (mettons, une couleur en HSV: (h, s, v)), mais que tu ne veux travailler que sur la teinte (h). Sémantiquement, la manière la plus claire de l'appeler serait :

h, _, _ = get_color_hsv(mon_image, x, y)

De cette manière, les programmeurs qui lisent ton code, en voyant cette ligne, peuvent se dire directement « Ah ok, dans son algo, on ne travaille que sur la teinte et on ne tient pas compte du reste. »
Ça rend le programme plus clair, plus facile à comprendre. C'est le but de Python.

Ok là c'est plus clair, c'est juste utile à la compréhension du lecteur du code.

Merci de ta réponse

Citation : iNaKoll

Bonsoir,

Voilà ce que j'ai codé en 3 min. J'espère que ce code sera conforme au KISS tant apprécié ici!

def pascal(n, liste = [1]):
    if len(liste) > 1 and liste[1] >= n:
        return max(liste)
    else:
        liste = [0] + liste + [0]
        newliste = []
        for i in range(0, len(liste)-1):
            newliste = newliste + [liste[i]+liste[i+1]]
        return pascal(n,newliste)

print pascal(10)

Je planche sur une seconde version sans succès ce qui me laisse croire que cette dernière n'est pas KISS

Ton code peut être plus simple:

def pascal(n, liste = [1]):
    if not n: #Il ne reste plus de lignes à calculer
        return max(liste)
    else:
        newliste = [1]
        for i in range(0, len(liste)-1):
            newliste.append(liste[i]+liste[i+1]) #append est plus clair et adapté
        return pascal(n-1,newliste+[1]) #Utilisation de n pour savoir jusqu'où
                    #aller dans le calcul, nombre de lignes restantes à calculer.
print pascal(10)

Merci, maintenant c'est "KISS" ! Très fort ce petit python, j'aime beaucoup!

Perso, j'ai un code plus complique et j'ai pris plus de 3mins.
Je dois etre pas doue...

Citation : fred1599

Citation

Je haïs la récursivité

Pourquoi? Qu'est-ce qui te gêne? Connais-tu la particularité d'une fonction récursive?

Elle est belle.

Citation : NoHaR

Pour le coup, c'est moi qui ai plus de mal à lire ta version. C'est très subjectif en effet.

Tout à fait, à chacun d'apprécier selon ses goûts et son niveau.

Citation : NoHaR

OK, je poste l'explication.
(...)
Voilà.

Oui mais ce n'est pas du tout ce genre d'explication que j'attendais. As-tu testé ton code ?

Citation : Maxibolt

Pourquoi "lig" et "col" ? On aurait largement la place d'écrire "ligne" et "colonne"

C'est trop long à mon goût. J'aurais volontiers choisi i et j mais il était important que mes identificateurs témoignent de l'action (ligne ou colonne). Le choix de variable au nom court est assez répandu, typiquement ce que recommandent Kernighan et Pike dans leur livre "The practice of Programming" et dont je suis les recommandations d'assez près. De toutes façons, c'est quand même largement une affaire de choix personnel, entre i, j ou lig, col ou encore ligne et colonne, tout est est acceptable du moment que ce n'est pas imposé et que c'est cohérent.

Citation : Maxibolt

là, on commence par lire le code pour se demander ce qu'est lig, avant de voir le col

En effet, je comprends que ça puisse étonner. Mais un nom plus long heurte ma façon de penser.

Citation : NoHaR

Mais c'est comme ça que l'on s'en sert, sémantiquement et par convention en Python.
Disons que c'est une "bonne pratique"

Disons que j'ai déjà rencontré cet emploi néanmoins je ne suis pas sûr que l'usage en soit très répandu. Cet usage est-il documenté quelque part ?
J'ai stocké pas mal de code source Python que je consulte régulièrement (Cpython, Django, matplotlib, PyQt, etc) et je le trouve environ 250 fois (ce qui est pas mal) mais sur un total de 13500 fichiers (ce qui relativise ...).