teaching:progappchim:algos_entiers

Différences

Ci-dessous, les différences entre deux révisions de la page.

Lien vers cette vue comparative

Les deux révisions précédentes Révision précédente
Prochaine révision		 Révision précédente
Prochaine révisionLes deux révisions suivantes
teaching:progappchim:algos_entiers [2015/04/20 10:04] – villersdteaching:progappchim:algos_entiers [2018/11/13 10:19] – [Problème du sac à dos] villersd
Ligne 7: Ligne 7:
 Explication géométrique : en comprenant un nombre entier comme une longueur et un couple d'entiers (a,b) comme un rectangle, leur PGCD est la longueur du côté du plus grand carré permettant de carreler entièrement ce rectangle. L'algorithme d'Euclide décompose ce rectangle en carrés, de plus en plus petits, par divisions euclidiennes successives, de la longueur par la largeur, puis de la largeur par le reste, jusqu'à un reste nul (**observez bien [[http://fr.wikipedia.org/wiki/Algorithme_d%27Euclide#Explications_g.C3.A9om.C3.A9triques|ici]] !**). Explication géométrique : en comprenant un nombre entier comme une longueur et un couple d'entiers (a,b) comme un rectangle, leur PGCD est la longueur du côté du plus grand carré permettant de carreler entièrement ce rectangle. L'algorithme d'Euclide décompose ce rectangle en carrés, de plus en plus petits, par divisions euclidiennes successives, de la longueur par la largeur, puis de la largeur par le reste, jusqu'à un reste nul (**observez bien [[http://fr.wikipedia.org/wiki/Algorithme_d%27Euclide#Explications_g.C3.A9om.C3.A9triques|ici]] !**).
 Cela donne ceci en Python : Cela donne ceci en Python :
-<sxh python; title : pgcd.py>+<code python pgcd.py>
 #!/usr/bin/env python #!/usr/bin/env python
 # -*- coding: UTF-8 -*- # -*- coding: UTF-8 -*-
Ligne 22: Ligne 22:
 n1=210 n1=210
 n2=126 n2=126
-print gcd(n1, n2) +print(gcd(n1, n2)) 
-</sxh>+</code>
  
 Si on dispose des décompositions en facteurs premiers d'un nombre entier, on peut aussi établir la valeur du PGCD en effectuant le produit de tous les facteurs communs. Si on dispose des décompositions en facteurs premiers d'un nombre entier, on peut aussi établir la valeur du PGCD en effectuant le produit de tous les facteurs communs.
Ligne 40: Ligne 40:
 Pour lister les nombres premiers strictement inférieur à un nombre N donné, un algorithme naïf (appelés tests de primalité) consiste à considérer les naturels un par un, en essayant de le diviser par tous les nombres inférieurs à sa racine carrée : s'il est divisible par l'un d'entre eux, il est composé, et sinon, il est premier. Voici une implémentation en Python de cette idée. Pour lister les nombres premiers strictement inférieur à un nombre N donné, un algorithme naïf (appelés tests de primalité) consiste à considérer les naturels un par un, en essayant de le diviser par tous les nombres inférieurs à sa racine carrée : s'il est divisible par l'un d'entre eux, il est composé, et sinon, il est premier. Voici une implémentation en Python de cette idée.
  
-<sxh python; title : nombres_premiers-01.py>+<code python nombres_premiers-01.py>
 #!/usr/bin/env python #!/usr/bin/env python
 # -*- coding: UTF-8 -*- # -*- coding: UTF-8 -*-
Ligne 56: Ligne 56:
  
 p=primelist(1000) p=primelist(1000)
-print p +print(p) 
-</sxh>+</code>
  
 L'algorithme peut être rendu plus efficace : il suggère beaucoup de divisions inutiles, par exemple, si un nombre n'est pas divisible par 2, il est inutile de tester s'il est divisible par 4. En fait, il suffit de tester sa divisibilité par tous les nombres premiers inférieurs à sa racine carrée. Le crible d'Ératosthène est une méthode, reposant sur cette idée, qui permet de trouver tous les nombres premiers inférieurs à un certain entier naturel donné N. En supprimant tous les multiples, à la fin il ne restera que les entiers qui ne sont multiples d'aucun entier, et qui sont donc les nombres premiers. Voici une implémentation en Python du crible d'Ératosthène : L'algorithme peut être rendu plus efficace : il suggère beaucoup de divisions inutiles, par exemple, si un nombre n'est pas divisible par 2, il est inutile de tester s'il est divisible par 4. En fait, il suffit de tester sa divisibilité par tous les nombres premiers inférieurs à sa racine carrée. Le crible d'Ératosthène est une méthode, reposant sur cette idée, qui permet de trouver tous les nombres premiers inférieurs à un certain entier naturel donné N. En supprimant tous les multiples, à la fin il ne restera que les entiers qui ne sont multiples d'aucun entier, et qui sont donc les nombres premiers. Voici une implémentation en Python du crible d'Ératosthène :
  
-<sxh python; title : nombres_premiers-03.py>+<code python nombres_premiers-03.py>
 #!/usr/bin/env python #!/usr/bin/env python
 # -*- coding: UTF-8 -*- # -*- coding: UTF-8 -*-
Ligne 84: Ligne 84:
    
 p=primelist(1000) p=primelist(1000)
-print p +print(p) 
-</sxh>+</code>
  
 ==== Références ==== ==== Références ====
Ligne 100: Ligne 100:
 Version élémentaires, par essais systématiques de diviseurs : Version élémentaires, par essais systématiques de diviseurs :
  
-<sxh python; title : factorisation_nombres_premiers-01.py>+<code python; title : factorisation_nombres_premiers-01.py>
 #!/usr/bin/env python #!/usr/bin/env python
 # -*- coding: UTF-8 -*- # -*- coding: UTF-8 -*-
Ligne 121: Ligne 121:
  
 p=prime_factors(1234567890) p=prime_factors(1234567890)
-print p +print(p) 
-</sxh>+</code>
  
 Exercices :  Exercices : 
Ligne 166: Ligne 166:
 donnée. En voici une solution : donnée. En voici une solution :
  
-<sxh python; title : aperitif_initial-02.py>+<code python; title : aperitif_initial-02.py>
 #!/usr/bin/env python #!/usr/bin/env python
 # -*- coding: utf-8 -*- # -*- coding: utf-8 -*-
Ligne 201: Ligne 201:
 # atomes=atomes[::-1] # atomes=atomes[::-1]
 masse=59 masse=59
-print atomes,type(atomes) +print(atomes,type(atomes)) 
-print masse, type(masse) +print(masse, type(masse)) 
-print aperitif(masse, atomes) +print(aperitif(masse, atomes)) 
-</sxh>+</code>
  
  
Ligne 231: Ligne 231:
   * [[http://codereview.stackexchange.com/questions/20569/dynamic-programming-solution-to-knapsack-problem|codereview.stackexchange.com]], programmation dynamique   * [[http://codereview.stackexchange.com/questions/20569/dynamic-programming-solution-to-knapsack-problem|codereview.stackexchange.com]], programmation dynamique
   * [[http://www.markhneedham.com/blog/2013/01/07/knapsack-problem-python-vs-ruby/]]   * [[http://www.markhneedham.com/blog/2013/01/07/knapsack-problem-python-vs-ruby/]]
 +  * [[https://medium.freecodecamp.org/if-you-have-slow-loops-in-python-you-can-fix-it-until-you-cant-3a39e03b6f35|If you have slow loops in Python, you can fix it…until you can’t]] (knapsack problem)
  
   * [[http://fr.wikipedia.org/wiki/Probl%C3%A8me_du_sac_%C3%A0_dos]]   * [[http://fr.wikipedia.org/wiki/Probl%C3%A8me_du_sac_%C3%A0_dos]]
  • teaching/progappchim/algos_entiers.txt
  • Dernière modification : 2023/01/10 09:04
  • de villersd