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 0k
n.
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.
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) ?
Bonsoir carpediem :
k in range (n+1) signifie que k prend les valeurs entières dans l'intervalle , 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
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 à
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 :
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)
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
@alb 12 :
lorsque l'on fait des tableaux de listes, elles doivent nécessairement avoir la même taille ?
c'est ce que semble dire le message d'erreur. Ce serait logique.
Mais je ne suis pas un specialiste de python.
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 !
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 .
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)
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
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 :
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 ...)
"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.
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)
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:;
il faudra surement montrer aux eleves que l'appel à une fonction recursive augmente tres rapidement le temps de calcul.
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.
Les 0 ne me dérangent pas (en effet 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.
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.
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
alb12 : ça marchait l'autre fois ... mais ça ne marche plus non plus ...
je pense que cela vient de mon ordi ...
essayer ceci ?
dans Cookies et données de sites>effacer les donnees
cocher Accepter les cookies et les données de site
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
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.
Bonjour,
Je voulais savoir si il était possible de faire la même fonction pascal sans importer numpy ?
Merci à vous.
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :