MASTER DAPM   — D22 —  Examen de TP


Mercredi 8 février 2017     09:00 → 12:00 (durée 3H00)

Lisez attentivement le contenu de ce paragraphe avant de lire le sujet et de commencer ! Suivez scrupuleusement les instructions en respectant à la lettre les commandes, les noms des fichiers proposés, majuscules/minuscules comprises. Lisez attentivement le sujet. Les réponses aux questions éventuelles doivent être incorporées au fichier source C sous forme de commentaires en début de programme.

NB. Si vous n'avez pas réussi à suivre les instructions ci-dessus et que je dois intervenir pour faire ce travail à votre place, je retirerai 5 points à votre note.


OBJECTIF DE L'EXAMEN.

Écrire un programme de résolution du problème du compte est bon à l'aide du backtracking.

RÈGLES DU JEU.

On tire un nombre N au hasard entre 100 et 999 (inclus) et un jeu de 6 plaques (6 nombres) au hasard et sans remise parmi les 24 plaques suivantes:
1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 25, 50, 75, 100.
Le but du jeu est de trouver un nombre M le plus proche possible du nombre N (idéalement M = N) à l'aide d'une expression (un calcul) faisant intervenir les 4 opérations arithmétiques +, -, *, / et les plaques de son choix. Dans le cas où il y a plusieurs joueurs et au cas où les joueurs les plus proches du résultat ont la même valeur M, c'est le calcul qui utilise le moins de plaques qui est privilégié.

Les opérations arithmétiques sont restreintes aux entiers naturels, on ne peut donc diviser deux plaques A et B que si A divise B et on ne peut soustraire que si le résultat est positif.

Exemple: pour N = 126 avec le jeu de plaques [50, 2, 6, 25, 3, 6], une solution possible est 126 = 50 + (3 * 25) + (6/6) qui utilise 5 des 6 plaques. Une autre solution qui n'utilise que 4 plaques est 126 = (50 - (6 + 2)) * 3.

ADAPTATION DES RÈGLES DU JEU ET INDICATIONS.

Dans le programme CEB.c fourni plus loin et qu'il faudra compléter, le nombre N et les valeurs des plaques sont saisis sur la ligne de commande (N en tête de liste). Ainsi, l'appel sur la ligne de commande CEB 456 2 10 5 3 50 lance la résolution du problème pour l'entier N = 456 avec les 5 plaques 2, 10, 5, 3 et 50.

Par défaut N doit être compris entre NMIN = 100 et NMAX = 999 (inclus). Le nombre de plaques sera compris entre 2 et 10 (inclus) et leurs valeurs seront comprises entre 1 et PMAX = 100 inclus. Il suffit de modifier ces trois constantes dans le programme pour généraliser le jeu.

Chaque valeur nulle saisie sur la ligne de commande est remplacée par une valeur tirée au hasard, dans l'intervalle [[NMIN, NMAX]] pour N et [[1, PMAX]] pour une plaque. Ainsi l'appel CEB 0 0 0 0 0 0 0, lance le programme sur une valeur N aléatoire avec 6 plaques aléatoires. Ces adaptations sont déjà réalisées dans le programme fourni.

Les macros :

  1. abs(x). Pour calculer une valeur absolue.
  2. NMIN et NMAX. Constantes bornant la valeur de l'entier N à calculer.
  3. PMAX. La valeur maximale pour une plaque.

Les définitions de types :

  1. tplaque. Structure à deux champs pour représenter une plaque du jeu. Le champ val contient la valeur entière de la plaque, le champ exp la chaîne de caractère codant l'expression algébrique dont l'évaluation est val. Initialement exp est la chaîne constituée par les chiffres de l'entier val.
  2. tplaques. Un tableau de plaques pour ranger les plaques utilisées dans le jeu.

Les variables globales :

  1. N. L'entier à calculer, il est instancié par la fonction TraiterArgs().
  2. M. Structure à trois champs pour la solution optimale. Elle contient la valeur entière val la plus proche de N, la chaîne de caractères exp qui décrit l'expression algébrique dont l'évaluation est M et ndpu le nombre de plaques utilisées pour le calcul. Ce dernier champ est utile pour choisir parmi les différentes solutions, celle qui utilise le moins de plaques.
  3. NbPlaques. Le nombre de plaques saisies sur la ligne de commande.
  4. plaques. Le tableau contenant les plaques saisies. Il est instancié par la fonction TraiterArgs(). Le champ val de la première entrée plaques[0] contient le nombre de plaques du tableau (l'autre champ est inutilisé).
  5. NbSol. Initialisée à 0, elle contient le nombre d'expressions dont l'évaluation égale N.

Les fonctions prédéfinies :

  1. TraiterArgs. Elle récupère les valeurs sur la ligne de commande (celle de N suivie de celles des plaques) et renvoie le tableau contenant les différentes plaques ou NULL en cas d'erreur. Si une valeur saisie sur la ligne de commande est égale à 0, elle est remplacée par un entier tiré au hasard. (tirage non uniforme, mais suffisant pour ce jeu.)
  2. main. Elle récupère les arguments, les traite, initialise la meilleure approximation M, lance la fonction de recherche puis affiche la meilleure approximation.

SUJET.

Récupérez le fichier CEB.c qui contient la trame du programme à écrire et son fichier Makefile. Pour tous les exercices, il est impératif de commenter vos fonctions en expliquant précisément le rôle de vos instructions. Une solution sera fournie à l'issue de l'examen.

Complétez la fonction AfficherPlaques() qui affiche la valeur et l'expression associée de chacune des plaques du tableau passé en paramètre. Cette fonction vous sera utile pour vérifier vos calculs.
Complétez la fonction Calculer() qui, à partir d'un tableau de plaques, de deux entiers i et j et d'un caractère +,-,*,/ codant l'opération, renvoie une plaque dont le champ val contient le résultat de l'opération P[i] op P[j] et le champ exp l'expression correspondante. Par exemple si la plaque d'indice i contient la valeur 10 et la plaque d'indice j la valeur 3 et que l'opération est codée par le caractère *, alors le champ val contiendra la valeur 30 et le champ exp la chaîne de caractères (10 * 3).

Si l'opération est illicite (soustraction négative ou nulle, division impossible) ou inutile (multiplication par 1 ou division par 1), la fonction renverra une plaque dont le champ val vaudra 0 et le champ exp la chaîne vide.
Complétez la fonction Reduction() qui à partir d'un tableau de plaques, de deux entiers i et j et d'un entier codant une opération algébrique (0 ↔ +, 1 ↔ -, 2 ↔ *, 3 ↔ /), renvoie un nouveau tableau contenant en position d'indice 1, la plaque résultat de l'opération P[i] op P[j] effectuée par la fonction Calculer(), et les plaques inutilisées du tableau en entrée (donc autres que celles d'indice i et j).

La fonction devra renvoyer le pointeur NULL si la réduction n'était pas possible.
Complétez la fonction PlusProche() qui à partir d'un tableau de plaques, renvoie la valeur de la plaque la plus proche de N, renvoie l'indice de cette plaque via la variable IdxPP et met à jour la variable globale M si la valeur la plus proche est meilleure que celle qui était contenue dans M ou que la valeur est identique mais que le calcul utilise moins de plaques.
Complétez la fonction ChercherSolutions() pour qu'elle affiche toutes les expressions algébriques dont l'évaluation vaut N (rien sinon). La meilleure solution est affichée dans la fonction main() quoi qu'il arrive.

Indication : écrivez une fonction récursive qui utilise le backtracking. Rappelez la fonction ChercherSolutions() avec un jeu de plaques réduit grâce à la fonction Reduire() et ceci pour chaque couple d'indices de plaques (i, j) et chaque opérateur +, -, *, /.

En quoi consiste la base récurrente de l'algorithme ?
Quelle est la meilleure approximation pour l'entier N = 793 avec les plaques suivantes : [3, 2, 5, 10, 2, 7] ?
Quelle est la complexité de votre algorithme ?