Différences
Ci-dessous, les différences entre deux révisions de la page.
Prochaine révision | Révision précédente Prochaine révisionLes deux révisions suivantes | ||
teaching:progappchim:algos_entiers [2015/04/13 08:32] – créée villersd | teaching:progappchim:algos_entiers [2020/02/06 03:48] – [Références] villersd | ||
---|---|---|---|
Ligne 5: | Ligne 5: | ||
===== Recherche du PGCD (plus grand commun diviseur) ===== | ===== Recherche du PGCD (plus grand commun diviseur) ===== | ||
+ | Explication géométrique : en comprenant un nombre entier comme une longueur et un couple d' | ||
+ | Cela donne ceci en Python : | ||
+ | <code python pgcd.py> | ||
+ | # | ||
+ | # -*- coding: UTF-8 -*- | ||
+ | def gcd(a, b): | ||
+ | """ | ||
- | ===== Recherche | + | Unless b==0, the result will have the same sign as b (so that when |
+ | b is divided by it, the result comes out positive). | ||
+ | """ | ||
+ | while b: | ||
+ | a, b = b, a%b | ||
+ | return a | ||
+ | |||
+ | n1=210 | ||
+ | n2=126 | ||
+ | print(gcd(n1, | ||
+ | </ | ||
+ | |||
+ | Si on dispose des décompositions en facteurs premiers d'un nombre entier, on peut aussi établir la valeur | ||
+ | |||
+ | |||
+ | ==== Références | ||
+ | |||
+ | * [[http:// | ||
+ | * [[http:// | ||
+ | * [[https:// | ||
+ | * [[http:// | ||
===== 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' | ||
+ | |||
+ | |||
+ | ===== Références ===== | ||
+ | * [[http:// | ||
+ | * [[http:// | ||
+ | * [[http:// | ||
+ | * [[http:// | ||
+ | * [[http:// | ||
+ | * [[http:// | ||
+ | * [[http:// | ||
+ | * [[http:// | ||
+ | * [[http:// | ||
+ | ===== 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 | + | ===== Applications chimiques |
+ | * formules CHON(S) | ||
* protéines | * protéines | ||
- | * spectro | + | * spectrométrie |
+ | |||
+ | ===== 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:// | ||
+ | * [[https:// | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | ===== Références diverses ===== | ||
+ | * [[http:// | ||
+ | * [[https:// | ||