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 Prochaine révisionLes deux révisions suivantes | ||
teaching:progappchim:algos_entiers [2015/04/14 16:04] – villersd | teaching:progappchim:algos_entiers [2017/02/24 13:23] – 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 : pgcd.py> | + | <code python pgcd.py> |
# | # | ||
# -*- 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' | 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' | ||
- | <sxh python; title : nombres_premiers-01.py> | + | <code python nombres_premiers-01.py> |
# | # | ||
# -*- coding: UTF-8 -*- | # -*- coding: UTF-8 -*- | ||
Ligne 56: | Ligne 56: | ||
p=primelist(1000) | p=primelist(1000) | ||
- | print p | + | print(p) |
- | </sxh> | + | </code> |
L' | L' | ||
- | <sxh python; title : nombres_premiers-03.py> | + | <code python nombres_premiers-03.py> |
# | # | ||
# -*- 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, | Version élémentaires, | ||
- | <sxh python; title : factorisation_nombres_premiers-01.py> | + | <code python; title : factorisation_nombres_premiers-01.py> |
# | # | ||
# -*- 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 : | ||
+ | * 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' | ||
- | FIXME : amélioration utilisant un crible | ||
===== Références ===== | ===== Références ===== | ||
Ligne 137: | Ligne 140: | ||
* [[http:// | * [[http:// | ||
===== Recherche du PPCM ===== | ===== Recherche du PPCM ===== | ||
- | Explication de la relation entre pgcd et ppcm via les facteurs premiers des nombres ! | + | Explication de la relation entre PGCD et PPCM via les facteurs premiers des nombres |
- | * [http:// | + | 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< | ||
- | ===== Problème | + | Le PGCD est 42, obtenu par le produit des facteurs communs (soulignés), |
- | * [[http:// | ||
===== 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:// | ||
Ligne 155: | Ligne 215: | ||
* formules CHON(S) | * 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:// | ||
+ | |||
+ | * [[http:// | ||
+ | * [[https:// | ||
+ | |||
+ | |||
===== Références diverses ===== | ===== Références diverses ===== |