Je rappelle comment il est construit : chaque élément z d'une ligne s'obtient comme somme des deux termes au-dessus et à gauche de l'élément z. Par exemple, à la ligne 7, on a : 35 = 20 + 15. Les extrémités de chaque ligne valent toujours 1 (un).
Vous remarquerez que la plus grande valeur de chaque ligne se trouve pile au centre de la ligne. Par exemple, pour la ligne 9, la plus grande valeur est 126.
On demande d'écrire un programme en Python qui calcule la plus grande valeur de la ligne numéro n du tableau de Pascal.
Donc si on donne n=9 au programme, il devra renvoyer 126.
C'est un exercice relativement facile mais peut-être pas autant que cela à faire de façon propre.
Vous aurez besoin essentiellement des parties suivantes du cours :
C'est pas très précis : il faut se baser véritablement sur le triangle de Pascal ou plutôt utiliser la formule de combinaisons ? Qui de plus donnerait directement la plus grande valeur :
Soit <math>\(n\in \mathbb{N}\)</math> et <math>\(p \in \mathbb{N}\)</math> le plus grand possible tel que <math>\(p\leq \frac{n}{2}\)</math> (soit <math>\(p=E\left (\frac{n}{2} \right )\)</math>). Alors <math>\(\binom{p}{n}=\frac{n!}{p!(n-p)!}\)</math> est la plus grande valeur possible du triangle de Pascal de la ligne n, pas besoin de boucles, juste de l'opérateur factorielle.
from math import factorial as fact, ceil
pascal = lambda n : fact(n) / (fact(ceil(n / 2)) * fact(n - ceil(n / 2)))
for i in range(1,11):
print "n = {0} => max = {1}".format(i, pascal(i))
Qui retourne :
n = 1 => max = 1
n = 2 => max = 2
n = 3 => max = 3
n = 4 => max = 6
n = 5 => max = 10
n = 6 => max = 20
n = 7 => max = 35
n = 8 => max = 70
n = 9 => max = 126
n = 10 => max = 252
Je préfère garantir à l'utilisateur qu'il récupèrera bien un entier en sortie.
J'aime pas trop ton calcul de coefficient binomial ... il fait trop calculer l'ordinateur avec par exemple n = 100000000 et p = 9999999 ...
Voici comment je fait un coefficient binomial (matte la récursivité wéééé gros!)
def coefficient_binomial(n, k):
"""Préconditions: k plus petit ou égal à n ET n et k encodé en virgule flottante"""
if n == k:
return 1
else:
return n / (n - k) * coeficient_binomial(n - 1, k)
Le seul truc qui pose problème avec ton code djidis, c'est qu'il retourne tout sauf une combinaison.
EDIT : J'ai rien dit, j'utilisais des entiers, je me demandais pourquoi sur le papier ça marchait, et pas dans ton code, et je n'avais pas fais attention à la note.
djidis : en Python, avec l'interpréteur standard en tout cas, la récursivité est un mauvais choix. Pour des trop grandes valeurs, ton programme ne va pas seulement mettre longtemps, il va planter (enfin tel qu'il est écrit il va planter pour toutes les valeurs, mais c'est une faute de frappe ).
Pour n = 100000000 et p = 9999999, par exemple.
edit : oui et puis en plus, l'algorithme est faux. Là, tu calcules n! / (n - p)!, il te reste une division par p! à effectuer.
Et tant que j'y penses, la factorielle du module math ira bien plus vite que ton calcul récursif interprété (et s'il était itératif ça serait pareil d'ailleurs). Quand tu as la possibilité d'utiliser une fonction Python qui fait ce que tu recherches, il vaut mieux faire ça que la recoder, surtout si on recherche les performances.
Je pense qu'il voulait qu'on recrée le triangle pour ensuite récupérer ce qu'on cherche.
Et pas prendre ce qu'on cherche directement avec la formule ^^.
Teste ton code, tu verras qu'il ne renvoie pas ce que tu recherches. Essaie avec 10 et 20 par exemple.
T'as bien lu les préconditions ?
Citation : Maxibolt
Et tant que j'y penses, la factorielle du module math ira bien plus vite que ton calcul récursif interprété (et s'il était itératif ça serait pareil d'ailleurs). Quand tu as la possibilité d'utiliser une fonction Python qui fait ce que tu recherches, il vaut mieux faire ça que la recoder, surtout si on recherche les performances.
Osef O.o ... je calcule un coefficient binomial en essayent justement d'éviter faire un calcul de factorielle (qui peut etre tres lourd pour l'ordinateur).
Avec 20 et 10 si tu préfères... Je te promet que ton code ne renvoie pas le coefficient binomial en question. Mais fais le test, tu vas pouvoir le constater par toi-même. Tu n'as pas le bon algorithme. En fait, tu ne calcules même pas ce que j'ai dit plus haut. Ton code n'a rien à voir avec celui d'un coefficient binomial.
Maintenant, pour la factorielle : ton code est en O(n). Une factorielle écrite le plus naïvement possible, c'est en O(n) aussi. Sauf que celle de Python est très certainement largement optimisée, et la complexité réelle est sans doute inférieure. Niveau complexité, c'est donc plus efficace de calculer une factorielle que ton code à toi (ça n'est absolument pas lourd).
En plus, la fonction factorial a été compilée, et sera donc de très loin plus rapide que ta fonction qui est interprétée.
Donc finalement : niveau algorithmique, ton calcul est plus lent (plus lourd si tu préfères) que celui avec factorial, en plus d'être faux. Niveau implémentation (parce que c'est important aussi), il est catastrophique, tant parce qu'il est lent que parce que la récursivité va poser problème.
Ah, effectivement, je n'avais pas pensé à faire comme ça. L'algorithme est effectivement bon, et il est en fait en complexité O(n - k).
Il reste malgré tout qu'il s'agit d'une mauvaise implémentation dans un langage comme Python (ce qui est tout aussi important : la complexité ne suffit pas pour prédire les performances réelles d'un programme).
edit grillé : "Mon algorithme est plus performant lorsque k est un nombre proche de n." -> oui, mais ça n'a pas un grand intérêt, sauf si tu peux garantir que ton code ne sera utilisé qu'avec ces valeurs. En général, on n'a aucune information sur k ou n, et dans cet exercice en particulier, on fait le calcul avec k = n / 2, on arrive donc à une complexité en O(n), soit la même qu'un calcul utilisant la factorielle.
En plus, un algorithme n'est pas "performant" en soi : c'est son implémentation qui est performante, et ici, ton implémentation l'est beaucoup moins.
Ne pense pas par contre que je trouve ta solution sans intérêt : ton algorithme est très bien s'il s'agissait de recoder la combinaison en ne s'autorisant que les opérations de base (+, -, *, /), et plus efficace qu'un autre qui commencerait pas coder naïvement la factorielle. Le point que je souligne est son inefficacité en pratique : le calcul avec une fonction factorielle déjà existante et compilée est bien plus rapide que le tien, même en admettant que la récursivité ne pose pas de problème.
En fait, le code le plus intéressant ici sans se soucier des détails d'exécution est sans doute le tien, mais le plus efficace est à mon avis celui qui utilise scipy (et une fonction de combinaison à mon avis plus performante que toutes les autres).
Très étonné voire surpris et presque déçu par les réponses. Vous ne pouvez pas être KISS ? Qui vous a parlé de coefficient binomial ? Bien évidemment, pour faire mon exercice, il n'y a besoin de connaître aucune maths. C'est pour ça que j'ai rappelé la construction de Pascal et c'est pour ça que j'ai précisé de quoi on avait besoin dans le cours (boucle et liste). Ce n'est pas un exercice de maths ou d'algorithmique, c'est un exercice pour débutant en programmation Python. Retrouvez donc un peu de candeur.
Au passage, je suis stupéfait que toutes les solutions proposées et utilisant le coefficient binomial se sentent obligées d'utiliser ceil : c'est totalement impropre et inutile. Bon de toute façon ce n'est pas ce genre de solution que j'attendais et j'espère juste qu'un débutant naïf va passer et coder le problème suivant les indications que j'ai données.
Très étonné voire surpris et presque déçu par les réponses. Vous ne pouvez pas être KISS ? Qui vous a parlé de coefficient binomial ? Bien évidemment, pour faire mon exercice, il n'y a besoin de connaître aucune maths. C'est pour ça que j'ai rappelé la construction de Pascal et c'est pour ça que j'ai précisé de quoi on avait besoin dans le cours (boucle et liste). Ce n'est pas un exercice de maths ou d'algorithmique, c'est un exercice pour débutant en programmation Python. Retrouvez donc un peu de candeur.
Je crois que c'était fait exprès.
Citation : candide
Au passage, je suis stupéfait que toutes les solutions proposées et utilisant le coefficient binomial se sentent obligées d'utiliser ceil : c'est totalement impropre et inutile. Bon de toute façon ce n'est pas ce genre de solution que j'attendais et j'espère juste qu'un débutant naïf va passer et coder le problème suivant les indications que j'ai données.
Que ce soit ceil ou floor, ça ne change strictement rien, puisque chaque ligne présente une symétrie.
...
Bon, allez, pour te faire plaisir, mais c'est bien parce que c'est toi, voilà l'algo naïf :
from math import floor
def pascal(ligne):
triangle = [[1], [1, 1]]
for n in range(2, ligne+1):
triangle.append([1])
for p in range(1,n):
triangle[n].append(triangle[n-1][p] + triangle[n-1][p-1])
triangle[n].append(1)
return triangle[ligne][floor(ligne/2)]
aucun besoin d'un quelconque floor ou ceil ici. Sans compter que cette fonction pose des problèmes, sous Python 2.6 puisque ton code que je rappelle ci-dessous
Citation : NoHaR
from math import floor
def pascal(ligne):
triangle = [[1], [1, 1]]
for n in range(2, ligne+1):
triangle.append([1])
for p in range(1,n):
triangle[n].append(triangle[n-1][p] + triangle[n-1][p-1])
triangle[n].append(1)
return triangle[ligne][floor(ligne/2)]
for k in range(20): print pascal(k)
affiche le brillant message suivant :
Traceback (most recent call last):
File "pascal.py", line 12, in <module>
for k in range(20): print pascal(k)
File "pascal.py", line 10, in pascal
return triangle[ligne][floor(ligne/2)]
TypeError: list indices must be integers, not float
Comme on dit, KISS !
EDIT Suite à remarque de nahor, reprise de mon premier code pour le rendre python3 compatible (changer / en // et ajouter des parenthèses après print)
Essaye d'utiliser les 2 derniers codes avec Python 3:
>>> from math import factorial as f
>>>
>>> def p(n): return f(n)/(f(n/2)*f(n-n/2))
...
>>> for k in range(1,20): print(p(k))
...
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<stdin>", line 1, in p
ValueError: factorial() only accepts integral values
>>>
>>> from pascal import pascal
>>> for k in range(1,20): print(pascal(k))
...
1
2
3
6
10
20
35
70
126
252
462
924
1716
3432
6435
12870
24310
48620
92378
>>> 3/2
1.5
>>> from math import floor
>>> type(floor(3/2))
<class 'int'>
Ce n'est pas que je me complique la vie inutilement, c'est juste que j'utilise la même version de Python que les "vrais" débutants qui viennent du tutoriel officiel... Après, si en Python 2, une division entière retourne un entier et qu'une fonction qui arrondit à l'entier inférieur ou supérieur retourne un float, tant mieux (ou tant pis...), mais ne viens pas me chercher des poux alors que je fais simplement en sorte que mon programme ait un comportement correct dans la version de Python que j'utilise pour ces exercices.
Ceci dit. Sans rancune, voici une version de l'algo naïf qui passe à la fois avec Python 2.6.5 et avec Python 3.1.2, au prix d'une légère perte de sémantique sur la dernière ligne :
def pascal(ligne):
triangle = [[1], [1, 1]]
for n in range(2, ligne+1):
triangle.append([1])
for p in range(1,n):
triangle[n].append(triangle[n-1][p] + triangle[n-1][p-1])
triangle[n].append(1)
return triangle[ligne][int(ligne/2)]
Ceci dit. Sans rancune, voici une version de l'algo naïf qui passe à la fois avec Python 2.6.5 et avec Python 3.1.2, au prix d'une légère perte de sémantique sur la dernière ligne :
C'est exactement ce que j'essayais de te faire comprendre. La compatibilité entière entre les deux versions est impossible. Le tout est de produire du code qui ne nécessite que des transformations cosmétiques, par exemple pour la division remplacer / par // ou ajouter-retirer des parenthèses après print. D'ailleurs, tu as encore compliqué pour rien, la conversion en int est inutile :
def pascal(ligne):
triangle = [[1], [1, 1]]
for n in range(2, ligne+1):
triangle.append([1])
for p in range(1,n):
triangle[n].append(triangle[n-1][p] + triangle[n-1][p-1])
triangle[n].append(1)
return triangle[ligne][ligne//2]
Sinon, pour le reste du code, j'espère que d'autres réponses verront le jour. D'une façon générale, je suis partisan des solutions minimalistes : the simpler, the better.
Ah bah, j'ai simplement utilisé la solution naïve à la lettre "je construis les n premières lignes du triangle de Pascal et je retourne la valeur au milieu de la dernière". C'est difficile dans cet exemple d'avoir envie de trouver une solution plus élégante sachant qu'on obtient facilement un one-liner avec une combinaison...
Sinon, je n'avais effectivement pas en tête l'opérateur // qui réalise la division entière (c'est pas comme si je l'utilisais tous les jour au boulot), et il faut avouer que tu es beaucoup plus explicite quand tu te plains d'un code que tu trouves "moche" que pour proposer une piste d'amélioration...
Ah bah, j'ai simplement utilisé la solution naïve à la lettre "je construis les n premières lignes du triangle de Pascal et je retourne la valeur au milieu de la dernière".
OK mais en fait il y a tout un spectre de solutions naïves. Disons que tu as proposé une solution très naïve. Je pense qu'on peut proposer une solution encore naïve tout en étant plus simple, plus lisible. Rappelons-nous : Readability counts.
Citation : NoHaR
C'est difficile dans cet exemple d'avoir envie de trouver une solution plus élégante sachant qu'on obtient facilement un one-liner avec une combinaison...
Oui biens sûr mais il faut pas penser à se faire plaisir. Disons que je pense au débutant qui sera content de voir qu'il existe vraiment une solution simple et transparente.
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
entwanne — @entwanne — Un zeste de Python — La POO en Python — Notions de Python avancées — Les secrets d'un code pythonique
entwanne — @entwanne — Un zeste de Python — La POO en Python — Notions de Python avancées — Les secrets d'un code pythonique
entwanne — @entwanne — Un zeste de Python — La POO en Python — Notions de Python avancées — Les secrets d'un code pythonique
entwanne — @entwanne — Un zeste de Python — La POO en Python — Notions de Python avancées — Les secrets d'un code pythonique
entwanne — @entwanne — Un zeste de Python — La POO en Python — Notions de Python avancées — Les secrets d'un code pythonique
entwanne — @entwanne — Un zeste de Python — La POO en Python — Notions de Python avancées — Les secrets d'un code pythonique