Exercice 3 - Binaire et masques solutions · Bac Numérique et Sciences Informatiques Nouvelle-Calédonie 2025 (jour 1)

Exercice 3 (8 points)

Cet exercice porte sur l'algorithmique, la représentation binaire des entiers positifs et la programmation en langage Python.

Partie A: Modélisation du problème

On s'intéresse à un jeu de calcul mental appelé Objectif somme. Le jeu se joue sur un plateau de 5x5 cases. Chaque case contient un chiffre non nul de 1 à 9. On dispose également de nombres cibles en ligne et en colonne. Le but est de trouver les cases du tableau à vider afin d'atteindre les cibles en ligne et en colonne:

sur chaque ligne, la somme des cases restantes doit valoir la cible de cette ligne;

sur chaque colonne, la somme des cases restantes doit valoir la cible de cette colonne.

De plus, il faut conserver au moins un chiffre par ligne.

Par exemple, la figure suivante représente un plateau de jeu et une solution:

Les lignes du plateau seront nommées de L0 à L4 et les colonnes de C0 à C4.

Ainsi l'exemple de la figure 1, la ligne L1 fait référence aux valeurs 8,6,3,5,1 du plateau et la colonne C3 fait référence aux valeurs 3,5,2,8,8 du plateau.

Dans la suite, on suppose que les cibles sont nécessairement des entiers entre 1 et 45.

Dans la suite on appelle plateau une liste de 5 listes de 5 entiers. Chacune des listes de 5 entiers représente une ligne. Les entiers de ces listes sont compris entre 0 et 9, 0 représente une case vide. Pour représenter un jeu, un plateau doit être accompagné de deux listes de 5 entiers: la liste des cibles de lignes, la liste des cibles des colonnes.

Voici une représentation en langage Python de la figure 1:

plateau_ex = [[7, 9, 2, 3, 2],

[8, 6, 3, 5, 1],

[7, 7, 3, 2, 7],

[6, 4, 5, 8, 2],

[8, 6, 8, 8, 4]]

ciblesLignes_ex = [13, 9, 12, 6, 4]

ciblesColonnes_ex = [15, 13, 5, 2, 9]

Partie C: Problème sur une ligne et représentation binaire

Pour aider à la résolution du jeu Objectif somme, on cherche dans cette partie à résoudre le problème sur une ligne seulement. Il s’agit de trouver les nombres d’une liste de 5 entiers dont la somme est égale à un nombre cible.

Par exemple, une solution pour la liste [6, 4, 5, 8, 2] avec la cible 6 est de conserver le chiffre 6 uniquement. Une autre solution est de conserver le 4 et le 2.

On représente la première solution (conserver le 6) par la liste [1, 0, 0, 0, 0]. Cela signifie que la solution choisie est uniquement le premier élément de la liste. La liste [1, 0, 0, 0, 0] est appelée un masque solution du problème. Le masque solution correspondant à la solution avec le 4 et le 2, est alors [0, 1, 0, 0, 1].

10.

Expliquer pourquoi [1, 1, 0, 0, 1] est un masque solution pour la liste [1, 2, 3, 5, 2] et la cible 5. Donner tous les autres masques solutions.

11.

Écrire une fonction somme qui prend comme paramètres une liste de 5 entiers et un masque (une liste de taille 5 de 0 et de 1) et qui renvoie la somme des chiffres du tableau correspondant au masque. Par exemple, somme([1, 5, 3, 4, 8], [0, 1, 1, 0, 1]) doit renvoyer $5 + 3 + 8 = 16$.

On peut remarquer que les masques solutions correspondent à des nombres en écriture binaire. Par exemple, le masque [0, 1, 0, 0, 1] correspond à l’entier 9 car $0 \times 16 + 1 \times 8 + 0 \times 4 + 0 \times 2 + 1 \times 1 = 9$. Ainsi, on représente les masques possibles par des nombres en écriture binaire sur 5 bits.

12.

Donner la représentation binaire sur 5 bits de l’entier 26 sous la forme d’une liste de taille 5.

13.

Expliquer pourquoi on ne représente que les entiers compris entre 0 et 31 sur 5 bits.

14.

Écrire une fonction dec2bin qui prend comme paramètre un entier compris entre 0 et 31 et qui renvoie sa représentation binaire sous la forme d’une liste de 5 bits. Par exemple la valeur de retour de l’appel dec2bin(9) est [0, 1, 0, 0, 1].

Pour résoudre le problème, on se propose de générer tous les masques possibles avec la fonction dec2bin et de tester si ce sont des masques solutions. On stockera alors tous ces masques solutions dans une liste. On pourra utiliser la méthode append appliquée à une liste.

15.

Écrire une fonction masques_solutions qui prend comme paramètres une liste de taille 5 entiers et une cible, et qui renvoie la liste de tous les masques solutions correspondant.