Différences
Ci-dessous, les différences entre deux révisions de la page.
Les deux révisions précédentes Révision précédente Prochaine révision | Révision précédente | ||
teaching:progappchim:algos_entiers [2015/04/14 04:11] – villersd | teaching:progappchim:algos_entiers [2023/01/10 09:04] (Version actuelle) – villersd | ||
---|---|---|---|
Ligne 7: | Ligne 7: | ||
Explication géométrique : en comprenant un nombre entier comme une longueur et un couple d' | Explication géométrique : en comprenant un nombre entier comme une longueur et un couple d' | ||
Cela donne ceci en Python : | Cela donne ceci en Python : | ||
- | <sxh python; title : gcd.py> | + | <code 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 34: | Ligne 34: | ||
* [[https:// | * [[https:// | ||
* [[http:// | * [[http:// | ||
- | |||
- | ===== Recherche du PPCM ===== | ||
===== Nombres premiers ===== | ===== Nombres premiers ===== | ||
+ | Un nombre premier est un entier naturel qui admet exactement deux diviseurs distincts entiers et positifs (qui sont alors 1 et lui-même) : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ... | ||
+ | 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' | ||
+ | |||
+ | <code python nombres_premiers-01.py> | ||
+ | # | ||
+ | # -*- coding: UTF-8 -*- | ||
+ | """ | ||
+ | Liste de nombres premiers strictement inférieurs à un entier donné | ||
+ | """ | ||
+ | def isprime(n): | ||
+ | for x in range(2, | ||
+ | if n % x == 0: | ||
+ | return False | ||
+ | return True | ||
+ | |||
+ | def primelist(n): | ||
+ | return [a for a in range(2,n) if isprime(a)] | ||
+ | |||
+ | p=primelist(1000) | ||
+ | print(p) | ||
+ | </ | ||
+ | |||
+ | L' | ||
+ | |||
+ | <code python nombres_premiers-03.py> | ||
+ | # | ||
+ | # -*- coding: UTF-8 -*- | ||
+ | """ | ||
+ | Liste de nombres premiers strictement inférieurs à un entier donné | ||
+ | """ | ||
+ | def primelist(n): | ||
+ | """ | ||
+ | Version avec crible d' | ||
+ | """ | ||
+ | li = range(n+1) | ||
+ | li[1] = 0 # 0 (déjà à 0) et 1 ne sont pas premiers | ||
+ | ncur = 2 # prochain nombre à tester | ||
+ | while ncur ** 2 <= n: # tant que ncur est inférieur à sqrt(n) | ||
+ | li[ncur*2:: | ||
+ | # les multiples de ncur | ||
+ | # ncur suivant (il ne doit pas être déjà mis à zéro) | ||
+ | ncur += 1 | ||
+ | while not li[ncur]: | ||
+ | ncur += 1 | ||
+ | return [a for a in li if a != 0] # renvoie une liste avec les élements non nuls | ||
+ | |||
+ | p=primelist(1000) | ||
+ | print(p) | ||
+ | </ | ||
+ | |||
+ | ==== Références ==== | ||
+ | * [[http:// | ||
+ | * [[http:// | ||
+ | * [[https:// | ||
+ | * [[http:// | ||
+ | * [[http:// | ||
+ | * [[http:// | ||
+ | * [[http:// | ||
+ | * [[http:// | ||
+ | * [[wp> | ||
+ | * [[https:// | ||
+ | * [[https:// | ||
+ | * [[https:// | ||
===== Factorisation en nombres premiers ===== | ===== Factorisation en nombres premiers ===== | ||
+ | |||
+ | Version élémentaires, | ||
+ | |||
+ | <code python; title : factorisation_nombres_premiers-01.py> | ||
+ | # | ||
+ | # -*- coding: UTF-8 -*- | ||
+ | """ | ||
+ | Factorisation en nombres premiers ; méthode par essais successifs | ||
+ | """ | ||
+ | |||
+ | def prime_factors(n): | ||
+ | li = [] | ||
+ | f = 2 # premier facteur à tester | ||
+ | while f*f <= n: | ||
+ | while (n % f) == 0: | ||
+ | li.append(f) | ||
+ | n = n/f # on divise par f | ||
+ | f = f+1 if f == 2 else f+2 # pour ne pas essayer les nombres pairs | ||
+ | if n > 1: # si on n'a pas obtenu n=1, alors le facteur restant est premier | ||
+ | | ||
+ | return li | ||
+ | |||
+ | |||
+ | p=prime_factors(1234567890) | ||
+ | print(p) | ||
+ | </ | ||
+ | |||
+ | Exercices : | ||
+ | * amélioration la recherche en combinant l' | ||
+ | * utiliser la décomposition en facteurs premiers de deux nombres (ou plus) pour trouver leur PGCD : pour l' | ||
+ | |||
+ | Techniques avancées : | ||
+ | * [[wp> | ||
+ | * [[https:// | ||
+ | * librairie sympy → pip install sympy (ou conda install sympy) | ||
+ | * Use the function sympy.ntheory.factorint : "Given a positive integer n, factorint(n) returns a dict containing the prime factors of n as keys and their respective multiplicities as values." | ||
+ | <code python> | ||
+ | from sympy.ntheory import factorint | ||
+ | factorint(10**20+1) → {73: 1, 5964848081: 1, 1676321: 1, 137: 1} | ||
+ | </ | ||
+ | |||
+ | ===== Références ===== | ||
+ | * [[http:// | ||
+ | * [[http:// | ||
+ | * [[http:// | ||
+ | * [[http:// | ||
+ | * [[http:// | ||
+ | * [[http:// | ||
+ | * [[http:// | ||
+ | * [[http:// | ||
+ | * [[http:// | ||
+ | * [[https:// | ||
+ | |||
+ | |||
+ | ===== Recherche du PPCM ===== | ||
+ | Explication de la relation entre PGCD et PPCM via les facteurs premiers des nombres | ||
+ | |||
+ | Voici un exemple utilisant les décompositions en facteur premier de 1470 et 252 : | ||
+ | |||
+ | ^ Facteurs premiers de 1470 ^ Facteurs premiers de 252^ | ||
+ | | __2__ | **2< | ||
+ | | __3__ | **3< | ||
+ | | **5** | | | ||
+ | | **7< | ||
+ | |||
+ | Le PGCD est 42, obtenu par le produit des facteurs communs (soulignés), | ||
+ | |||
===== Problème des apéritifs ===== | ===== Problème des apéritifs ===== | ||
+ | |||
+ | Énoncé en version " | ||
+ | |||
+ | < | ||
+ | |||
+ | Illustration : | ||
+ | {{ http:// | ||
+ | |||
+ | En chimie, un problème tout à fait équivalent consiste, en masses entières (donc en nombre de nucléons), à trouver une formule chimique incluant différents atomes d' | ||
+ | donnée. En voici une solution : | ||
+ | |||
+ | <code python; title : aperitif_initial-02.py> | ||
+ | # | ||
+ | # -*- coding: utf-8 -*- | ||
+ | """ | ||
+ | http:// | ||
+ | https:// | ||
+ | https:// | ||
+ | """ | ||
+ | |||
+ | def aperitif(total, | ||
+ | """ | ||
+ | |||
+ | version sans itérateur | ||
+ | |||
+ | :arg total int: Prix total à atteindre. | ||
+ | :arg prix list: Liste des prix disponibles. | ||
+ | |||
+ | :return: liste des solutions, ces solutions étant des | ||
+ | | ||
+ | """ | ||
+ | | ||
+ | if len(prix) == 0: | ||
+ | return [] | ||
+ | if len(prix) == 1: | ||
+ | if total % prix[0] == 0: | ||
+ | return [[int(total // prix[0])]] | ||
+ | liste=[] | ||
+ | for nombre in range(int((total // prix[0])+1)): | ||
+ | for solution in aperitif(total - prix[0]*nombre, | ||
+ | liste.append([nombre] + solution) | ||
+ | return liste | ||
+ | |||
+ | atomes=[1, | ||
+ | # atomes=atomes[:: | ||
+ | masse=59 | ||
+ | print(atomes, | ||
+ | print(masse, | ||
+ | print(aperitif(masse, | ||
+ | </ | ||
+ | |||
+ | |||
+ | ==== Références ==== | ||
* [[http:// | * [[http:// | ||
* [[http:// | * [[http:// | ||
+ | |||
+ | |||
+ | ===== Applications chimiques ===== | ||
+ | * formules CHON(S) | ||
+ | * protéines | ||
+ | * spectrométrie de masse (en masses entières) | ||
===== Problème du sac à dos ===== | ===== Problème du sac à dos ===== | ||
+ | L’énoncé | ||
+ | |||
+ | < | ||
+ | |||
+ | En voici une illustration (source wikimedia) : | ||
+ | {{ http:// | ||
+ | |||
+ | Ce problème revêt une importance économique dans de nombreux secteurs tels que la découpe de matériaux (afin de minimiser les pertes) ou le chargement de cargaisons (avions, camions, bateaux, | ||
+ | |||
+ | Solutions en Python : | ||
+ | * [[http:// | ||
+ | * [[http:// | ||
+ | * [[http:// | ||
+ | * [[https:// | ||
* [[http:// | * [[http:// | ||
+ | * [[https:// | ||
+ | |||
+ | |||
- | ==== Applications chimiques ==== | ||
- | * formules CHON | ||
- | * protéines | ||
- | * spectro de masse ? | ||
===== Références diverses ===== | ===== Références diverses ===== |