Inscription / Connexion Nouveau Sujet
Niveau enseignement
Partager :

Programmation du triangle de Pascal en Python

Posté par
manu_du_40
17-10-18 à 19:51

Bonsoir tout le monde,

je suis professeur dans une classe de Terminale où il y a pas mal de bons élèves qui sont passionnés d'informatiques.
Du coup, j'aimerais sortir un peu des sentiers battus et leur proposer une activité dont le but serait d'écrire une fonction en Python qui, pour un entier naturel donné, renvoie le triangle de Pascal jusqu'à l'ordre n. Cela me permet également de leur parler un peu de récursivité.
Ma question est purement technique car je maîtrise mal les tableaux sous Python.

Voici mon code Python :

import numpy as np

def binom(n,k):
    if k>n:
        return(0) # 1er cas de base de récursivité
    elif k==0:
        return(1) # 2e cas de base de récursivité
    elif k==1:
        return(n) # 3e cas de base de récursivité
    else :
        return(binom(n-1,k-1)+binom(n-1,k))  #on remonte à l'ordre n-1 grâce à la formule de Pascal

def dev(n):
    L=[]
    for k in range (n+1):
        L.append(binom(n,k))
    return(L)


def pascal(n):
    tableau=np.zeros((n,1))
    for k in range (n+1):
        tableau[k]=dev(k)
    return(tableau)

Les fonctions "binom" et "dev" fonctionnent bien : dev renvoie en fait une liste avec tous les coefficients binomiaux pour un n donné et 0kn.

Pour, la fonction pascal, je  souhaiterais obtenir un tableau qui, en fait, contiendrait les listes dev(1), dev(2), .... , dev(n) mais Python me donne une erreur de dimension. Est-ce un souci lié au fait que j'essaie de mettre des listes dans un tableau ?

Je vous remercie de m'avoir lu et j'attends vos suggestions.

Posté par
manu_du_40
re : Programmation du triangle de Pascal en Python 17-10-18 à 19:51

Sorry pour le "s" à informatiques à la 2e ligne

Posté par
carpediem
re : Programmation du triangle de Pascal en Python 17-10-18 à 20:47

salut

python accepte quasiment tout et vu ton erreur de dimension ce n'est pas le pb que tu penses ...

je ne m'y connais pas beaucoup en python mais suffisamment pour dire que :

que ce soit les listes ou la fonction range elles sont indicées à partir de 0 c'est peut-être plutôt de ce côté là qu'il faut chercher

PS : qu'est-ce que la fonction zero (première ligne de la fonction pascal) ?

Posté par
manu_du_40
re : Programmation du triangle de Pascal en Python 17-10-18 à 20:56

Bonsoir carpediem :

k in range (n+1) signifie que k prend les valeurs entières dans l'intervalle [0,n+1[, c'est un peu bizarre mais c'est ainsi.

Cela dit, il faut bien une liste de 3 éléments pour l'ordre 2 puisqu'il y a 3 termes dans le développement de (a+b)². C'est pour ça que je mets range(n+1) et non range(n).

La fonction 0 sert à créer un tableau rempli de 0 (à condition d'avoir chargé le package numpy au préalable). Dans ma fonction, je cherche à créer une matrice colonne à n lignes

Posté par
carpediem
re : Programmation du triangle de Pascal en Python 17-10-18 à 21:25

ok merci

mais je persiste (peut-être à tord (et j'en suis désolé par avance)) mais je pense toujours que c'est un pb d'indice

ton tableau (de une colonne à n + 1 lignes) devrait commencer avec dev(0) qui correspond à (a + b)^0 = 1

donc peut-être que la première ligne de la fonction pascal il faudrait

tableau = np.zeros(n + 1, 1)

en plus j'y vois des doubles parenthèses :

Citation :
def pascal(n):
    tableau=np.zeros((n,1))
    for k in range (n+1):
        tableau[k]=dev(k)
    return(tableau)
le pb ne viendrait-il pas de là ?

Posté par
alb12
re : Programmation du triangle de Pascal en Python 17-10-18 à 21:53

salut, je vois 2 problemes:
1/ tes dev(k) n'ont pas la meme taille
2/ k varie de 0 à n et ton tableau a n lignes (vu par carpediem)

Posté par
manu_du_40
re : Programmation du triangle de Pascal en Python 17-10-18 à 21:59

J'ai corrigé les doubles parenthèses (en effet inutiles ici) et j'ai également essayé de remplacer tableau = np.zeros(n , 1)  en tableau = np.zeros(n + 1, 1) .

Dans les 2 cas, voici le message renvoyé dans la console lorsque l'on appelle Pascal(5).

tableau[k+1]=dev(k)
ValueError: cannot copy sequence with size 2 to array axis with dimension 1.

Bon après, à défaut d'autre chose, il me reste toujours la solution suivante :

def pascal(n):
    for k in range (n+1):
        print(dev(k))

qui affichera les différentes listes , le défaut majeur étant que ma fonction pascal ne renvoie plus rien à présent...
Je reste preneur de toute solution plus propre.

Merci pour ton aide carpediem.

Manu

Posté par
alb12
re : Programmation du triangle de Pascal en Python 17-10-18 à 22:01

il faudrait creer des listes de meme taille en les completant par des 0 ou mieux des ""

Posté par
manu_du_40
re : Programmation du triangle de Pascal en Python 17-10-18 à 22:03

@alb 12 :

lorsque l'on fait des  tableaux de listes, elles doivent nécessairement avoir la même taille ?

Posté par
alb12
re : Programmation du triangle de Pascal en Python 17-10-18 à 22:07

c'est ce que semble dire le message d'erreur. Ce serait logique.
Mais je ne suis pas un specialiste de python.

Posté par
alb12
re : Programmation du triangle de Pascal en Python 17-10-18 à 22:09

pascal(0) marche mais pas pascal(1)

Posté par
manu_du_40
re : Programmation du triangle de Pascal en Python 17-10-18 à 22:15

alb12 @ 17-10-2018 à 22:09

pascal(0) marche mais pas pascal(1)

en effet, je viens de faire le test et je confirme.
Bon je réfléchis à comment créer des listes de même taille...

Merci alb12

Posté par
alb12
re : Programmation du triangle de Pascal en Python 17-10-18 à 22:18

cela dit ton sujet est extra, il illustre bien comment utiliser les fonctions pour decomposer un probleme en sous problemes.
Du coup il est facile de trouver le bug !

Posté par
manu_du_40
re : Programmation du triangle de Pascal en Python 17-10-18 à 22:28

Je viens de trouver une solution avec une double boucle for. Ca a l'air de marcher

def pascal(n):
    tableau=np.zeros((n+1,n+1))
    for k in range (n+1):
        for i in range (k+1):
            tableau[k,i]=(dev(k))[i]
    return(tableau)


Pas évident pour des terminales mais je suis joueur, j'ai envie de tenter .

Posté par
manu_du_40
re : Programmation du triangle de Pascal en Python 17-10-18 à 22:28

Merci à tous les deux, votre aide m'a été précieuse

Posté par
alb12
re : Programmation du triangle de Pascal en Python 17-10-18 à 22:41

Avec un autre logiciel, Xcas
c'est moins bien (une seule fonction)

Posté par
manu_du_40
re : Programmation du triangle de Pascal en Python 17-10-18 à 22:44

PS : avec ceci, ma fonction "dev" devient inutile du coup et elle augmente énormément la complexité (du fait des appels inutiles à la fonction binom en recalculant à chaque fois tous les coefficients binomiaux pour un ordre donné).

il faut donc modifier tableau[k,i]=(dev(k))[i]  en tableau[k,i]=binom(k,i)

Posté par
manu_du_40
re : Programmation du triangle de Pascal en Python 17-10-18 à 22:47

Sympa aussi l'algo sur Xcas. C'est pas forcément moins bien mais mon idée de départ était surtout de leur parler de récursivité.

Merci encore

Posté par
carpediem
re : Programmation du triangle de Pascal en Python 17-10-18 à 22:53

peut-être que alb12 a raison mais c'est étonnant ... peut-être qu'un tableau nécessite effectivement un dimensionnement constant des objets en argument ...

ou alors il ne faut  ... bon je vois qu'entre-temps vous avez causé ...

en fait j'ai été me documenter : effectivement un tableau n'accepte que des objets identiques

et je pense que ton programme initial marche si tu utilises une liste au lieu d'un tableau

et une liste est "mutable" donc tu en fais ce que tu veux

je t'invite donc à essayer cela :

Citation :
def pascal(n):
    tableau = []
    for k in range (n+1):
        tableau.append(dev(k))
    return(tableau)


par contre il va t'afficher le résultat sous la forme d'une ligne ... de toutes les lignes du triangle

mais à  la rigueur tu peux toujours finir par une petite boucle pour faire afficher en colonne les éléments de ta liste

Posté par
manu_du_40
re : Programmation du triangle de Pascal en Python 17-10-18 à 23:03

Merci carpediem.

Votre solution revient à écrire simplement

def pascal(n):
    for k in range (n+1):
        print(dev(k))

mais la fonction pascal n'en est plus une puisqu'elle ne renvoie rien. Je crois qu'on appelle ça une procédure si je me souviens bien de mes cours d'informatique en prépa (mais c'est bien loin tout ça ...)

Posté par
carpediem
re : Programmation du triangle de Pascal en Python 17-10-18 à 23:38

ouais tout simplement ... mais tu ne l'as pas en mémoire

Posté par
alb12
re : Programmation du triangle de Pascal en Python 18-10-18 à 07:52

"mais la fonction pascal n'en est plus une puisqu'elle ne renvoie rien. Je crois qu'on appelle ça une procédure"
oui c'est ça. On transforme une procedure en fonction en finissant par return(0) ce qui permet de verifier que la fonction a bien travaille.

Posté par
alb12
re : Programmation du triangle de Pascal en Python 18-10-18 à 11:08

je ferais ainsi:


import numpy as np

def binom(n,k):
    if k==0 or k==n:
        return(1)
    else:
        return(binom(n-1,k-1)+binom(n-1,k))

def pascal(n):
    tableau=np.zeros((n+1,n+1)) #comment faire une matrice avec des "" ?
    for k in range (n+1):
        for i in range (k+1):
            tableau[k,i]=binom(k,i)
    return(tableau)

Posté par
alb12
re : Programmation du triangle de Pascal en Python 18-10-18 à 11:27

et en Xcas (et en français)


fonction Coefficient(n,p)
  si p==0 ou p==n alors
    retourne 1;
  sinon
    retourne Coefficient(n-1,p)+Coefficient(n-1,p-1)
  fsi
ffonction:;

fonction TrianglePascal(n)
  var T;
  T:=[[""$(n+1)]$(n+1)];
  pour j de 0 jusque n faire
    pour k de 0 jusque j faire
      T[j][k]:=Coefficient(j,k);
    fpour
  fpour
  retourne T
ffonction:;

Posté par
alb12
re : Programmation du triangle de Pascal en Python 18-10-18 à 12:59

il faudra surement montrer aux eleves que l'appel à une fonction recursive augmente tres rapidement le temps de calcul.

Posté par
manu_du_40
re : Programmation du triangle de Pascal en Python 18-10-18 à 13:24

Merci alb12, j'ai procédé de cette façon également.
Je garde ton idée xcas car il peut en effet être intéressant de comparer les temps de calcul.

Posté par
manu_du_40
re : Programmation du triangle de Pascal en Python 18-10-18 à 13:27

Les 0 ne me dérangent pas (en effet \begin{pmatrix} n\\k \end{pmatrix} est bien nul lorsque k>n).
De toute façon, il me semble que dans un tableau, chaque élément doit être de même type en Python.

Posté par
manu_du_40
re : Programmation du triangle de Pascal en Python 18-10-18 à 13:28

Citation :
De toute façon, il me semble que dans un tableau, chaque élément doit être de même type en Python.

C'est d'ailleurs ce que dit carpediem à 22h53

Posté par
alb12
re : Programmation du triangle de Pascal en Python 18-10-18 à 14:04

Peut-on en terminale justifier que les k parmi n sont nuls pour k>n ?

Posté par
manu_du_40
re : Programmation du triangle de Pascal en Python 18-10-18 à 15:05

Les exercices de dénombrement n'étant plus au programme de 1èreS, l'expression des coefficients binomiaux à l'aide des factorielles n'est plus un attendu de terminale (le cas k>n fait partie de la définition ensembliste du nombre k parmi n).

Cette notion est abordée en probabilités. Le coefficient k parmi n est defini comme le nombre de chemins à k succès dans l'arbre pondéré associé à des épreuves de Bernoulli répétées n fois de façon identique et indépendantes.

Il est donc intuitivement assez simple de comprendre que si k>n, ce nombre de chemin est nul.

Posté par
alb12
re : Programmation du triangle de Pascal en Python 18-10-18 à 15:22

oui j'avoue que j'hesiterais entre nul et n'a pas de sens ... tout est pb de definition.

Posté par
carpediem
re : Programmation du triangle de Pascal en Python 18-10-18 à 18:31

on peut le poser comme une convention ce qui est d'ailleurs le cas

mais une interprétation concrète peut se faire :

soit en terme ensembliste : on ne peut pas choisir k > n objets dans un ensemble à n éléments
soit en terme de chemin : il n'y a pas de chemin permettant de choisir k > n éléments parmi n

bon ça se ressemble un peu mais ils connaissent les arbres donc la deuxième vision est assez naturelle

j'aurai aussi fait l'algo comme alb12 ... en remarquant que la fonction pascal n'est simplement une fonction que parce qu'on lui demande de nous renvoyer le tableau

mais sinon c'est essentiellement une procédure pour conserver les éléments dans un tableau

il eut été tout aussi équivalent de mémoriser les lignes du triangle dans une liste : une liste de listes ... que python traite sans pb

l'avantage c'est qu'une liste est dynamique et ne nécessite donc aucun dimensionnement initial

Posté par
alb12
re : Programmation du triangle de Pascal en Python 19-10-18 à 22:26

@manu_du_40
tu nous raconteras comment s'est passe la seance

Posté par
manu_du_40
re : Programmation du triangle de Pascal en Python 21-10-18 à 16:17

Promis, j'essaierai d'y penser lorsque je mettrai ça en oeuvre.

Posté par
alb12
re : Programmation du triangle de Pascal en Python 29-10-18 à 13:33

j'ai oublie un point essentiel, on peut programmer en python dans Xcas

Posté par
carpediem
re : Programmation du triangle de Pascal en Python 29-10-18 à 13:42

alb12 : ça marchait l'autre fois ... mais ça ne marche plus non plus ...

je pense que cela vient de mon ordi ...

Posté par
alb12
re : Programmation du triangle de Pascal en Python 29-10-18 à 15:22

essayer ceci ?
dans Cookies et données de sites>effacer les donnees
cocher Accepter les cookies et les données de site

Posté par
manu_du_40
re : Programmation du triangle de Pascal en Python 14-11-18 à 19:34

Bonsoir,

alors comme promis, petit compte-rendu de séance.

J'ai en amont un petit peu parlé de récursivité , en leur présentant quelques exemples classique (PGCD ou calcul de n!) et en les comparant à leurs homologues en itératif.
Cela a été plutôt bien accueilli, ils ont surtout remarqué l'économie du nombre d'affectations nécessaires pour le PGCD.

Maintenant, concernant la fonction "binom" plus compliqué :

- Oubli de certains cas de bases de récursivité (notamment k=1). Certains pensaient en effet que la formule de Pascal permettait toujours de "remonter le triangle" jusqu'à tomber sur un coefficient du type 0 parmi n, ce qui n'est pas le cas.
Le cas k>n a parfois posé problème. La raison donnée par les élèves : ça sert à rien d'ajouter 0 dans une somme (intéressant cela dit comme remarque).

- Certains, qui n'ont pas bien compris le principe, tentent d'instaurer de l'itératif dans une fonction récursive. Ca ne fait pas très bon ménage apparemment et je n'ai pas vu une seule solution satisfaisante avec ce genre de procédures.

- A noter un petit malin qui a été cherché la formule de k parmi n sur internet et qui a reprogrammé ma fonction factorielle pour la réutiliser dans la fonction binom.

Voilà voilà pour ce bref compte rendu.
Si vous avez d'autres questions, n'hésitez aps

Manu

Posté par
alb12
re : Programmation du triangle de Pascal en Python 14-11-18 à 21:46

Avez vous compare les temps d'execution avec la fonction iterative et la fonction recursive ?

Posté par
manu_du_40
re : Programmation du triangle de Pascal en Python 16-11-18 à 14:36

Oui, c'est déjà assez flagrant pour l'ordre 20.
Par contre, je n'ai pas eu le temps de leur faire chercher le nombre d'appels dans la fonction récursive.

Posté par
HulkRojo
re : Programmation du triangle de Pascal en Python 26-12-18 à 15:54

Bonjour,
Je voulais savoir si il était possible de faire la même fonction pascal sans importer numpy ?
Merci à vous.

Posté par
alb12
re : Programmation du triangle de Pascal en Python 26-12-18 à 21:54

salut, je ne sais pas si ceci repond à ta question ?



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !