XD blog

implémentation

2013-11-09 Compter les pièces de monnaie pour obtenir un montant

On est amené presque tous les jours à compter les pièces dans son porte-monnaie pour payer la baguette, le fromage ou la bouteille de vin. Comment écrire un algorithme qui donne la liste des pièces qu'il faut piocher dans son porte-monnaie pour payer ? On s'intéressera seulement au cas où on cherche à composer le montant juste. Cela revient à chercher un sous-ensemble S de pièces dans l'ensemble P des pièces du portefeuille pour composer le montant M :

$M = \sum_{ p \in S } p$

Une façon naïve de construire l'ensemble S est de procéder comme on le fait souvent, c'est-à-dire à prendre la pièce la plus grosse, de voir si elle dépasse le montant N puis de passer à la seconde plus grande et ainsi de suite. Soit :

On trie les pièces par ordre décroissant.
Au début, l'ensembe S est vide.
On prend les pièces dans l'ordre décroissant et on les ajoute à l'ensemble S si la somme de l'ensemble n'est pas plus grand que M.

Cela donne le programme suivant :

more...

2013-11-08 De l'idée au programme informatique

Lorsqu'on apprend à programmer, on a souvent une idée précise de l'objectif à atteindre et pourtant, on reste perplexe devant l'écran ne sachant pas par où commencer. Par exemple, si on dispose d'une matrice de trois colonnes :

x y poids

A C 3

A D 1

A E 4

B D 6

Et on souhaite calculer combien de fois on a le couple (x,y) divisé par combien de fois on a x :

$\frac{ \# (x,y) } { \# x }$

Par exemple, si x=A et y=D, on aura 1 / (3 + 1 + 4) = 0.125. Maintenant, comment s'y prend-on ?

Tout d'abord, on cherche à calculer un ratio de trucs qui ne sont pas des nombres entiers. Un dictionnaire est tout indiqué pour stocker ces trucs car il permet d'associer n'importe quoi (valeur) à presque n'importe quoi (clé). La valeur est une somme d'entiers, la clé est un couple de lettres ou une lettre. Sans me soucier des petits détails, voilà ce que j'ai envie d'écrire comme premier jet :

l = [ ['A','B', 3], ['A','C', 1], 
      ['A','E', 4], ['B','D', 6], ]

def transition(l):
    d = {}
    for x,y,n in l :
        d [x,y] += n  # erreur ici : KeyError: ('A', 'B')
        d [x] += n
    
    for x,y in d :
        d[x,y] /= d [x]
    return d
    
print (transition(l))

Bien sûr ça ne marche pas (voir l'erreur ci-dessus). Mais j'ai foi en moi. La logique est bonne. Lorsque j'écris d [a,b] += n, je suppose que le couple (x,y) existe dans le dictionnaire même la toute première fois. Et c'est pas possible ! Il est vide au début.

more...

Xavier Dupré