Exercice : Matrice binaire (comparaison de bits) et chemins rectilignes
Soit p et q deux entiers naturels tels que 5≤p≤q≤32. On se propose de remplir une matrice M à p lignes et q colonnes par des zéros (0) et des uns (1) de la façon suivante :
On mettra 1 dans toute cellule M[i, j] si les représentations de i et de j dans la base 2 ont au moins une fois le chiffre 1 à la même position, sinon on y mettra 0. On commencera à lire les positions à partir de la droite.
Exemples :
- M[5,3] aura la valeur 1 car les deux représentations binaires ont le chiffre 1 à la première position. En effet : 5=(101)_2 et 3=(11)_2 .
- M[9,4] aura la valeur 0 car les deux représentations binaires n’ont pas de 1 à la même place. En effet : 9=(1001)_2 et 4=(100)_2 .
On se propose ensuite de chercher tous les chemins rectilignes menant de la première ligne à la dernière ligne en n’empruntant que des cellules contenant des 1 et en sautant au maximum une seule cellule contenant 0. Par conséquent, un chemin rectiligne est une colonne ne comportant pas deux cellules consécutives contenant 0.
Pour tout chemin trouvé, on affichera son numéro (l’indice j). En plus, les données relatives à ce problème seront enregistrées dans un fichier texte intitulé chemins.txt et placé sur la racine du disque D. Ce fichier comportera dans sa première ligne le naturel p suivi d’une espace, suivie du naturel q et comportera dans chacune des lignes qui suivent le numéro du chemin trouvé. La dernière ligne contiendra le nombre de chemins trouvés.
On se propose d’écrire un programme qui réalise ces différents traitements.
Exemple d’exécution :
Supposons que l’on ait p = 5 et q = 5.
La matrice M de 5 lignes (indices 0 à 4) et 5 colonnes (indices 0 à 4) remplie selon la règle décrite (comparaison de bits de i et de j en partant de la droite) donne :
| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 |
| 2 | 0 | 0 | 1 | 1 | 0 |
| 3 | 0 | 1 | 1 | 1 | 0 |
| 4 | 0 | 0 | 0 | 0 | 1 |
- Analyse des colonnes (chemins rectilignes du haut vers le bas, avec au maximum un saut consécutif de 0) :
- Colonne 0 : Contient des 0 consécutifs (ex: M[0,0] et M[1,0] sont des 0). Rejetée.
- Colonne 1 : Contient les valeurs [0, 1, 0, 1, 0]. Il y a des zéros, mais aucun 0 n’est consécutif (le premier 0 est à l’indice 0, le suivant à l’indice 2, puis à l’indice 4). Validée (Chemin trouvé).
- Colonne 2 : Contient les valeurs [0, 0, 1, 1, 0]. M[0,2] et M[1,2] sont deux zéros consécutifs. Rejetée.
- Colonne 3 : Contient les valeurs [0, 1, 1, 1, 0]. Les zéros sont aux indices 0 et 4, ils ne sont pas consécutifs. Validée (Chemin trouvé).
- Colonne 4 : Contient M[0,4], M[1,4], M[2,4], M[3,4] qui valent tous 0 (plus d’un zéro consécutif au début). Rejetée.
- Résultat de l’affichage et du contenu du fichier chemins.txt :
5 5
1
3
2(Où 5 5 représente p et q, 1 et 3 sont les indices des colonnes valides, et 2 est le nombre total de chemins trouvés).
Questions :
- Ecrire un algorithme du programme principal en respectant le procédé décrit précédemment et en le décomposant en modules.
- Ecrire un algorithme pour chaque module envisagé.