Partage
  • Partager sur Facebook
  • Partager sur Twitter

[Exercice] Tableau de Pascal

facile et classique

Sujet résolu
    5 juillet 2010 à 4:13:11

    Bonjour,

    Je propose un petit exercice facile à l'intention des débutants.

    Soit le tableau de Pascal :

    . 1   1
      1   2   1
      1   3   3   1
      1   4   6   4   1
      1   5  10  10   5   1
      1   6  15  20  15   6   1
      1   7  21  35  35  21   7   1
      1   8  28  56  70  56  28   8   1
      1   9  36  84 126 126  84  36   9   1
      1  10  45 120 210 252 210 120  45  10   1


    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 :

    *) Les boucles
    *) Les listes et tuples (1/2)


    • Partager sur Facebook
    • Partager sur Twitter
      5 juillet 2010 à 7:27:52

      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.
      • Partager sur Facebook
      • Partager sur Twitter
        5 juillet 2010 à 10:31:31

        Ce qui donne :

        ** Correction, "int" au lieu de "ceil" ligne 4 **

        >>> from math import factorial as fact, ceil
        >>> def pas(n):
        ...     p = ceil(n/2)
        ...     return int(fact(n)/(fact(p)*fact(n-p)))
        ... 
        >>> pas(9)
        126
        
        • Partager sur Facebook
        • Partager sur Twitter
        Zeste de Savoir, le site qui en a dans le citron !
          5 juillet 2010 à 10:41:46

          NoHaR> Pas besoin de ceil() à la ligne 4, l'expression est déjà entière.
          • Partager sur Facebook
          • Partager sur Twitter
            5 juillet 2010 à 10:44:52

            Le ceil à cette ligne est là pour renforcer le type de retour.

            Si je le vire, ça donne :

            >>> def pas(n):
            ...     p = ceil(n/2)
            ...     return fact(n)/(fact(p)*fact(n-p))
            ... 
            >>> pas(9)
            126.0
            


            Je préfère garantir à l'utilisateur qu'il récupèrera bien un entier en sortie. ;)
            • Partager sur Facebook
            • Partager sur Twitter
            Zeste de Savoir, le site qui en a dans le citron !
              5 juillet 2010 à 10:53:15

              En plus court encore :
              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
              • Partager sur Facebook
              • Partager sur Twitter
              Anonyme
                5 juillet 2010 à 11:04:28

                ou encore

                >>> from math import factorial as fact, ceil
                >>> pascal = lambda n : fact(n) / (fact(ceil(n / 2)) * fact(n - ceil(n / 2)))
                
                >>> map(pascal, range(11))
                [1, 1, 2, 3, 6, 10, 20, 35, 70, 126, 252]
                
                • Partager sur Facebook
                • Partager sur Twitter
                  5 juillet 2010 à 11:14:26

                  NoHaR, pour être sûr de renvoyer un entier, je pense que int est plus sémantique que ceil.
                  • Partager sur Facebook
                  • Partager sur Twitter
                    5 juillet 2010 à 11:19:00

                    Citation : NoHaR

                    Le ceil à cette ligne est là pour renforcer le type de retour.

                    Si je le vire, ça donne :

                    >>> def pas(n):
                    ...     p = ceil(n/2)
                    ...     return fact(n)/(fact(p)*fact(n-p))
                    ... 
                    >>> pas(9)
                    126.0
                    



                    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)
                    
                    • Partager sur Facebook
                    • Partager sur Twitter
                      5 juillet 2010 à 11:21:33

                      Citation : Maxibolt

                      NoHaR, pour être sûr de renvoyer un entier, je pense que int est plus sémantique que ceil.



                      Ah, t'as raison. Je corrige.
                      • Partager sur Facebook
                      • Partager sur Twitter
                      Zeste de Savoir, le site qui en a dans le citron !
                        5 juillet 2010 à 11:24:51

                        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.
                        • Partager sur Facebook
                        • Partager sur Twitter
                          5 juillet 2010 à 11:27:57

                          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. :D



                          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.
                          • Partager sur Facebook
                          • Partager sur Twitter
                            5 juillet 2010 à 11:29:52

                            Je me demande quand même comment Candide envisageait la réponse.
                            • Partager sur Facebook
                            • Partager sur Twitter
                              5 juillet 2010 à 11:31:37

                              @entwanne

                              Ca retourne juste n! / (k! * (n - k)!) sans faire de calcul inutiles.

                              @Maxibolt

                              Oé, la faute de frappe n'a pas été corrigée à temps (huhu, faudra que j'apprenne à écrire). Sinon, c'est python, pas ma récursivité qui pose problème.
                              • Partager sur Facebook
                              • Partager sur Twitter
                                5 juillet 2010 à 11:34:39

                                Teste ton code, tu verras qu'il ne renvoie pas ce que tu recherches. Essaie avec 10 et 20 par exemple.
                                • Partager sur Facebook
                                • Partager sur Twitter
                                  5 juillet 2010 à 11:36:02

                                  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 ^^.
                                  • Partager sur Facebook
                                  • Partager sur Twitter
                                    5 juillet 2010 à 11:37:28

                                    Citation : Maxibolt

                                    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).
                                    • Partager sur Facebook
                                    • Partager sur Twitter
                                    Anonyme
                                      5 juillet 2010 à 11:50:10

                                      Avec scipy et sa doc on fait des miracles :)

                                      >>> from scipy import comb
                                      >>> from math import ceil
                                      >>> maxi=lambda n : ceil(comb(n, ceil(n/2)))
                                      


                                      >>> maxi(9)
                                      126.0
                                      • Partager sur Facebook
                                      • Partager sur Twitter
                                        5 juillet 2010 à 11:50:16

                                        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.
                                        • Partager sur Facebook
                                        • Partager sur Twitter
                                          5 juillet 2010 à 11:58:08

                                          Maxibolt> C'est peut-être faux avec 20 et 10, mais pas avec 20. et 10., il précise d'utiliser des flottants.
                                          • Partager sur Facebook
                                          • Partager sur Twitter
                                            5 juillet 2010 à 12:02:45

                                            Maxibolt: Mon algorithme est plus performant lorsque k est un nombre proche de n.
                                            • Partager sur Facebook
                                            • Partager sur Twitter
                                              5 juillet 2010 à 12:13:12

                                              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).
                                              • Partager sur Facebook
                                              • Partager sur Twitter
                                                5 juillet 2010 à 12:32:39

                                                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.
                                                • Partager sur Facebook
                                                • Partager sur Twitter
                                                  5 juillet 2010 à 13:14:24

                                                  Citation : candide

                                                  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 :p :

                                                  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)]
                                                  

                                                  • Partager sur Facebook
                                                  • Partager sur Twitter
                                                  Zeste de Savoir, le site qui en a dans le citron !
                                                    5 juillet 2010 à 15:04:58

                                                    Citation : NoHaR


                                                    Que ce soit ceil ou floor, ça ne change strictement rien, puisque chaque ligne présente une symétrie. >_<



                                                    ????
                                                    Ou bien c'est du 25ème degré que je ne comprends pas ou bien c'est vous qui vous compliquez la vie inutilement :


                                                    from math import factorial as f
                                                    
                                                    def p(n): return f(n)//(f(n//2)*f(n-n//2))
                                                    
                                                    print (p(1000))
                                                    


                                                    1
                                                    2
                                                    3
                                                    6
                                                    10
                                                    20
                                                    35
                                                    70
                                                    126
                                                    252
                                                    462
                                                    924
                                                    1716
                                                    3432
                                                    6435
                                                    12870
                                                    24310
                                                    48620
                                                    92378


                                                    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)

                                                    • Partager sur Facebook
                                                    • Partager sur Twitter
                                                      5 juillet 2010 à 16:43:23

                                                      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)]
                                                      
                                                      • Partager sur Facebook
                                                      • Partager sur Twitter
                                                      Zeste de Savoir, le site qui en a dans le citron !
                                                        5 juillet 2010 à 17:42:15

                                                        Citation : NoHaR


                                                        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.
                                                        • Partager sur Facebook
                                                        • Partager sur Twitter
                                                          5 juillet 2010 à 17:47:00

                                                          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...
                                                          • Partager sur Facebook
                                                          • Partager sur Twitter
                                                          Zeste de Savoir, le site qui en a dans le citron !
                                                            5 juillet 2010 à 18:14:59

                                                            Citation : NoHaR

                                                            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.
                                                            • Partager sur Facebook
                                                            • Partager sur Twitter

                                                            [Exercice] Tableau de Pascal

                                                            × 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.
                                                            • Editeur
                                                            • Markdown