TD-9, exploration

TD-9, exploration

Ce document est disponible à l'URL http://www.enseignement.polytechnique.fr/profs/informatique/Luc.Maranget/TC/TD-9

Envoyez vos programmes à Luc.Maranget@inria.fr. Les solutions sont ici.

1	Rendre la monnaie

Nous avons vu ce problème en cours. Étant donné un certain système de pièces, trouver le nombre minimal de pièces pour fabriquer une somme donnée. Nous avons également vu que l'algorithme glouton ne donne pas toujours l'optimal.

On cherchera plutôt à écrire un programme qui donne la solution optimale à tout prix. On utilisera la programmation dynamique. Le principe est ici de remarquer que le nombre minimal M(s) de pièces pour une somme s donnée, se calcule en fonction de ce minimum pour des sommes plus petites :

Où p₀, p₁, ... , p_n-1 sont les valeurs des pièces.

Cette remarque autorise le calcul de M à l'aide d'un tableau rempli de gauche à droite. On pourra retrouver les pièces qui forment l'optimum à l'aide d'une autre tableau qui enregistrera la pièce ajoutée à chaque étape.

Et on obtiendra par exemple (pour rendre 38 francs, à l'aide du système français, plus une pièce de 4 francs) :

maranget@manche ~/TD/TD-9 > java Monnaie 38 1 2 4 5 10 20 50 100
Voici votre monaie en 4 pieces : 20 10 4 4

On insistera un peu sur la sûreté de la programmation. On traitera en particulier le cas où il n'est pas possible de rendre la monnaie :

maranget@manche ~/TD/TD-9 > java Monnaie 23 5 7
Désolé, je ne peux pas rendre la monaie.

Solution.

Une extension possible de cet exercice est de considérer que le tiroir caisse de la boulangerie ne contient pas infiniment de pièces et de demander au client s'il ne peut pas donner une pièce en plus dans le cas où il est impossible de rendre la monnaie par manque de pièces...

2	Le compte est bon

Rappelons le principe du jeu. On choisit au hasard N (six dans le jeu) plaques parmi un tas de plaques portant des nombres (de 1 à 10, 25, 50, 75 et 100 dans le jeu). On tire ensuite au hasard complet un nombre M non nul (compris entre 100 et 999 dans le jeu).

Le but du jeu est d'arriver à retrouver M à l'aide des N plaques et des quatre opérations (la division est autorisée si elle tombe juste).

Dans le cas de six plaques la quantité de calculs possibles est à la porté d'un ordinateur. En suivant la technique d'exploration suivante. Soit S multi-ensemble d'entiers, le but est donc de calculer M à l'aide de ces entiers :

Si S est vide, il n'y a pas de solution.
Si M est présent dans S, c'est fini, il existe une solution.
Sinon, on considérera touts les paires{s_i, s_j} de deux entiers pris dans S (s_i >= s_j) et on cherchera à résoudre les trois à quatre sous-problèmes de taille n-1 sur les multi-ensembles obtenus en retirant s_i et s_j de S et en y ajoutant s_i + s_j, s_i * s_j, s_i - s_j ou s_i / s_j (la soustraction ne donne lieu à rien si s_i = s_j, la division également si s_i n'est pas multiple de s_j).

Le nombre total d'ensembles examinés est inférieur à C(N) avec C(1) = 1 et C(n+1) = 1 + 4C_n²C(n-1). Soit C(6) vaut dans les trois millions et demi, ce qui est peu. En pratique, il n'y a même pas lieu de chercher à optimiser beaucoup.

Dans un premier temps, on écrira une méthode qui renvoie un booléen indiquant si le compte est bon ou pas. Dans un deuxième temps, on cherchera a afficher la suite des opérations réalisées lorsque le compte est bon.

Afin de vous aider à écrire un code assez générique voici une classe Op des opérateurs. La classe Op est abstraite et déclare deux méthodes :

La méthode eval :
```
abstract int eval (int x, int y) ;
```
Réalise effectivement un calcul à partir de x et y.
La méthode symbol :
```
abstract String symbol() ;
```
L'appel op.symbol() renvoie un symbole représentant l'opération op.

Il y a une sous-classe de Op par opération, soit Add, Sub, Mul et Div. À titre d'exemple voici la classe des additions.

class Add extends Op {
  int eval (int x, int y) {
    int r = x + y ;
    if (r <= x || r <= y) // Il y a eu débordement de capacité
      return 0 ;
    else
      return r;
  }

  String symbol () {return "+";}
}

On notera que lorsque l'opération est illégale (par exemple, si la division ne tombe pas juste ou en cas de débordement de capacité) les méthodes eval renvoient conventionellement zéro, qui ne se trouve jamais dans les ensembles S.

Toute l'astuce de la programmation repose sur la gestion des ensembles de plaques (multi-ensembles de nombres). Vous devriez obtenir par exemple :

maranget@manche ~/TD/TD-9 > java Ceb 2 7 10 25 75 100 383
Le compte est bon
400 - 17 = 383
200 * 2 = 400
125 + 75 = 200
100 + 25 = 125
10 + 7 = 17
maranget@manche ~/TD/TD-9 > java Ceb 2 7 10 25 75 100 391
Le compte est bon
500 - 109 = 391
50 * 10 = 500
75 - 25 = 50
100 + 9 = 109
7 + 2 = 9
maranget@manche ~/TD/TD-9 > java Ceb 2 7 10 25 75 100 921
Le compte est pas bon

(On notera que l'affichage des calculs demande un peu d'interprétation.)

Solution..

Dernière modification : 2002-11-27

Ce document a été traduit de L^AT_EX par H^EV^EA.