| Les deux révisions précédentes Révision précédente | Prochaine révisionLes deux révisions suivantes |
| teaching:progappchim:algos_entiers [2015/04/20 08:29] – villersd | teaching:progappchim:algos_entiers [2015/04/20 10:04] – villersd |
|---|
| Le PGCD est 42, obtenu par le produit des facteurs communs (soulignés), tandis que le PPCM est obtenu par le produit de tous les facteurs, en utilisant la puissance la plus grande (en gras). Tous les facteurs du tableau de décomposition, soit de la première colonne, soit de la seconde, sont tous utilisés. Par conséquent on a bien pour deux nombres a et b que PPCM(a,b) = a * b / PGCD(a,b) ! | Le PGCD est 42, obtenu par le produit des facteurs communs (soulignés), tandis que le PPCM est obtenu par le produit de tous les facteurs, en utilisant la puissance la plus grande (en gras). Tous les facteurs du tableau de décomposition, soit de la première colonne, soit de la seconde, sont tous utilisés. Par conséquent on a bien pour deux nombres a et b que PPCM(a,b) = a * b / PGCD(a,b) ! |
| |
| ===== Problème du sac à dos ===== | |
| |
| * [[http://fr.wikipedia.org/wiki/Probl%C3%A8me_du_sac_%C3%A0_dos]] | |
| |
| |
| ===== Problème des apéritifs ===== | ===== Problème des apéritifs ===== |
| | |
| | Énoncé en version "appliquée" : |
| | |
| | <blockquote>La carte des apéritifs propose un certain nombre d’éléments, à des prix différents. Quel assortiment puis-je acheter, coûtant exactement une certaine somme d’argent N ?</blockquote> |
| | |
| | Illustration : |
| | {{ http://imgs.xkcd.com/comics/np_complete.png }} |
| | |
| | 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'éléments différents qui donnera une masse entière |
| | donnée. En voici une solution : |
| | |
| | <sxh python; title : aperitif_initial-02.py> |
| | #!/usr/bin/env python |
| | # -*- coding: utf-8 -*- |
| | """ |
| | http://paternault.fr/informatique/jouets/aperitif.html |
| | https://git.framasoft.org/spalax/jouets/blob/master/README.rst |
| | https://wiki.python.org/moin/Generators |
| | """ |
| | |
| | def aperitif(total, prix): |
| | """Solutions du problème des apéritifs. |
| | |
| | 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 |
| | listes correspondant à ``prix``. |
| | """ |
| | |
| | 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, prix[1:]): |
| | liste.append([nombre] + solution) |
| | return liste |
| | |
| | atomes=[1,12,14,16,32] |
| | # atomes=atomes[::-1] |
| | masse=59 |
| | print atomes,type(atomes) |
| | print masse, type(masse) |
| | print aperitif(masse, atomes) |
| | </sxh> |
| | |
| | |
| | ==== Références ==== |
| * [[http://xkcd.com/287/]] | * [[http://xkcd.com/287/]] |
| * [[http://paternault.fr/informatique/jouets/aperitif.html]] et [[https://git.framasoft.org/spalax/jouets/blob/master/README.rst|ici]] | * [[http://paternault.fr/informatique/jouets/aperitif.html]] et [[https://git.framasoft.org/spalax/jouets/blob/master/README.rst|ici]] |
| * formules CHON(S) | * formules CHON(S) |
| * protéines | * protéines |
| * spectro de masse ? | * spectrométrie de masse (en masses entières) |
| | |
| | ===== Problème du sac à dos ===== |
| | L’énoncé de ce problème extrêmement difficile ([[http://fr.wikipedia.org/wiki/21_probl%C3%A8mes_NP-complets_de_Karp|un des problèmes de Karp]]) est par contre simple, faisant référence à un problème courant : |
| | |
| | <blockquote>Étant donné plusieurs objets possédant chacun un poids et une valeur et étant donné un poids maximum pour le sac, quels objets faut-il mettre dans le sac de manière à maximiser la valeur totale sans dépasser le poids maximal autorisé pour le sac ?</blockquote> |
| | |
| | En voici une illustration (source wikimedia) : |
| | {{ http://upload.wikimedia.org/wikipedia/commons/thumb/c/c6/Knapsack_greedy.svg/500px-Knapsack_greedy.svg.png }} |
| | |
| | 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,...). Un examen systématique des possibilités conduit à une explosion combinatoire du nombre de configurations à examiner ! |
| | |
| | Solutions en Python : |
| | * [[http://rosettacode.org/wiki/Knapsack_problem/0-1|Rosetta code]], en force brute et 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://fr.wikipedia.org/wiki/Probl%C3%A8me_du_sac_%C3%A0_dos]] |
| | * [[https://interstices.info/jcms/c_19213/le-probleme-du-sac-a-dos]] |
| | |
| | |
| |
| ===== Références diverses ===== | ===== Références diverses ===== |