Matrice – Bac pratique – Section informatique – 2013
Sujet (Algo et programmation - Bac 2013)
On se propose de chercher dans une matrice M, les plus longues séquences d'éléments juxtaposés dont la somme est égale à zéro, en procédant comme suit :
Exemple:
Pour la matrice M de dimension 5x6 suivante :
Dans la lère ligne, il y a 2 séquences d'éléments juxtaposés dont la somme est égale à 0 :
- La séquence ayant comme ICD la valeur 1 et comme ICF la valeur 5.
- La séquence ayant comme ICD la valeur 3 et comme ICF la valeur 6.
Dans la 2ème ligne, il y a une seule séquence d'éléments juxtaposés dont la somme est égale à 0, la séquence ayant comme ICD la valeur 1 et comme ICF la valeur 4.
Dans la 3eme ligne, il y a une seule séquence d'éléments juxtaposés dont la somme est égale à 0, la séquence ayant comme ICD la valeur 2 et comme ICF la valeur 6.
Dans la 4eme ligne, il n'y a aucune séquence d'éléments juxtaposés dont la somme est égale à O.
Dans la Sème ligne, il y a une seule séquence d'éléments juxtaposés dont la somme est égale à 0, la séquence ayant comme ICD la valeur 1 et comme ICF la valeur.
Travail demandé
Ecrire un programme en Python intitulé Sequence qui permet, à partir d'une matrice M de dimension LxC, de remplir un tableau T et de créer un fichier "Long_Seq.txt", comme décrit précédemment.
Solution Algorithmique
Dans cet algorithme, On va utiliser trois fonctions et cinq procédures:
- la fonction saisie()
- la fonction saisie_element()
- la procédure remplir_matrice()
- la procédure afficher_matrice()
- la fonction verif_juxtapose()
- la procédure remplir_tableau()
- la procédure afficher_tableau()
- la procédure remplir_fichier_long_seq()
Algorithme du programme Principal
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
Algorithme Sequence Debut Ecrire('*** Saisie du nombre des lignes et de colonnes ***') # Saisie du nombre de lignes et de colonnes l <- saisie(0, 23) c <- saisie(2, 23) # Initialisation des variables globales longueur_tableau <- 0 max_sequence <- 0 # Appels des différentes fonctions remplir_matrice(m, l, c) afficher_matrice(m, l, c) remplir_tableau(t, m, l, c) afficher_tableau(t, longueur_tableau) remplir_fichier_long_seq(t, longueur_tableau, max_sequence) Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| l | entier |
| c | entier |
| m | matrice |
| t | tableau |
La fonction saisie
La fonction saisie(inf, sup) permet de demander à l’utilisateur de saisir un entier strictement compris entre deux bornes inf et sup.
Plus précisément :
- La fonction affiche un message demandant un entier n tel que inf < n < sup. - Si la valeur saisie n’est pas dans l’intervalle ouvert ]inf, sup[, la saisie est redemandée. - La saisie est répétée tant que la condition n’est pas respectée. - Lorsque l’utilisateur entre enfin une valeur correcte, la fonction retourne cet entier.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
Fonction saisie():entier # Demande à l'utilisateur de saisir un entier n Ecrire('donner n tel que ' + inf + '< n < ' + sup + ': ') Lire(n) # Tant que n n'appartient pas à l'intervalle ]inf , sup[ # on redemande la saisie Tant que (n <= inf) ou (n >= sup) faire Ecrire('donner n tel que ' + inf + '< n < ' + sup + ': ') Lire(n) Fin tant que # Retourne la valeur correcte saisie retourner n Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| n | entier |
La fonction saisie_element
La fonction saisie_element() a pour rôle est de demander à l’utilisateur de saisir un entier non nul.
Plus précisément :
La fonction demande une première fois à l’utilisateur de saisir un entier.
Si l’utilisateur saisit 0, la saisie est refusée.
Tant que la valeur saisie est égale à 0, la fonction redemande une nouvelle saisie.
Dès que l’utilisateur saisit un entier différent de 0, la fonction retourne cette valeur.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
Fonction saisie_element():chaine # Première saisie Ecrire('donner n tel que n != 0: ') Lire(n) # Tant que la valeur saisie est nulle, on recommence Tant que (n == 0) faire Ecrire('donner n tel que n != 0: ') Lire(n) Fin tant que # Retourne la valeur correcte retourner n Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| n | entier |
La procédure remplir_matrice
Cette procédure remplir_matrice(m, l, c) a pour rôle de remplir une matrice m de dimensions l × c avec des entiers non nuls saisis par l’utilisateur.
Détail du fonctionnement :
Elle affiche un message indiquant le début du remplissage de la matrice.
Elle parcourt la matrice ligne par ligne (i de 0 à l-1).
Pour chaque ligne, elle parcourt les colonnes (j de 0 à c-1).
À chaque position m[i][j], elle appelle la fonction saisie_element() afin de saisir un entier différent de zéro.
La valeur saisie est stockée dans la matrice à la position correspondante.
|
1 2 3 4 5 6 7 8 |
Procedure remplir_matrice(m:matrice, l:entier, c:entier) Ecrire('*** Remplir la matrice M ***') Pour i de 0 à l-1 faire Pour j de 0 à c-1 faire m[i][j] <- saisie_element() Fin pour Fin pour Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| i | entier |
| j | entier |
La procédure afficher_matrice
Cette procédure afficher_matrice(m, l, c) a pour rôle d’afficher le contenu de la matrice M de dimensions l × c.
Détail du fonctionnement :
Elle affiche un message indiquant l’affichage de la matrice.
Elle parcourt la matrice ligne par ligne à l’aide de la boucle sur i.
Pour chaque ligne, elle parcourt les colonnes avec la boucle sur j.
Chaque élément m[i][j] est affiché sur la même ligne, séparé par un espace.
Après l’affichage de chaque ligne, un retour à la ligne est effectué avec Ecrire().
|
1 2 3 4 5 6 7 8 9 |
Procedure afficher_matrice(m:matrice, l:entier, c:entier) Ecrire(''*** Contenu de la matrice M ***'') Pour i de 0 à l-1 faire Pour j de 0 à c-1 faire Ecrire(m[i][j],' ') Fin pour Ecrire() Fin pour Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| i | entier |
| j | entier |
La fonction verif_juxtapose()
Cette fonction verif_juxtapose(m, numero_ligne, numero_colonne, c) a pour rôle de vérifier s’il existe, sur une ligne donnée de la matrice m, une séquence de valeurs consécutives (juxtaposées) dont la somme est égale à 0.
Détail du fonctionnement :
La fonction commence par initialiser la somme s avec la valeur située à la position (numero_ligne, numero_colonne).
Elle utilise l’indice i pour parcourir les colonnes à partir de numero_colonne.
Tant que la somme s n’est pas nulle et que l’on ne dépasse pas la dernière colonne (i < c - 1), elle ajoute successivement les éléments voisins situés à droite. À chaque itération, l’élément suivant de la ligne est ajouté à la somme. Si, au cours de ce parcours, la somme devient égale à 0, la fonction retourne l’indice de la colonne où la séquence se termine. Si aucune séquence de valeurs juxtaposées de somme nulle n’est trouvée, la fonction retourne -1.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
Fonction verif_juxtapose(m:matrice, numero_ligne:entier, numero_colonne:entier, c): booleen # Initialisation de la somme avec la première valeur s <- m[numero_ligne][numero_colonne] i <- numero_colonne # Addition des éléments juxtaposés tant que la somme ≠ 0 # et que l’on reste dans la ligne Tant que (s != 0) et (i < c - 1) faire i <- i + 1 s <- s + m[numero_ligne][i] Fin pour # Si la somme est nulle, retourner l’indice de fin Si s = 0 alors retourner i Sinon retourner -1 Fin si Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| s | entier |
| i | entier |
La procédure remplir_tableau
Cette procédure remplir_tableau(t, m, l, c) a pour rôle de détecter toutes les séquences de valeurs juxtaposées de somme nulle dans la matrice m et de stocker leurs caractéristiques dans le tableau T.
Détail du fonctionnement :
La procédure parcourt toutes les lignes de la matrice (i de 0 à l-1).
Pour chaque ligne, elle parcourt les colonnes possibles de départ (j de 0 à c-2).
À chaque position (i, j), elle appelle la fonction verif_juxtapose pour vérifier s’il existe une séquence contiguë sur la ligne i dont la somme est égale à 0.
Si une séquence est trouvée un dictionnaire sequence_juxtapose est créé pour mémoriser :
- nl : le numéro de la ligne,
- icd : l’indice de la colonne de début,
- icf : l’indice de la colonne de fin.
Ces informations sont ensuite renseignées à partir des valeurs calculées.
La procédure met à jour la longueur maximale de séquence trouvée (max_sequence).
Chaque séquence détectée est ajoutée au tableau T à la position longueur_tableau.
Le compteur longueur_tableau est ensuite incrémenté.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
Procédure remplir_tableau(t:tableau, m:matrice, l:entier, c:entier) Pour i de 0 l-1 faire Pour j de 0 à c - 1) faire # Vérification de l’existence d’une séquence Si verif_juxtapose(m, i, j, c) != -1 alors sequence_juxtapose = Enregistrement( nl= entier, # numéro de ligne icd= entier, # indice de colonne début icf= entier # indice de colonne fin ) # Remplissage du dictionnaire sequence_juxtapose["nl"] <- i sequence_juxtapose["icd"] <- j sequence_juxtapose["icf"] <- verif_juxtapose(m, i, j, c) # Mise à jour de la longueur maximale trouvée Si max_sequence < c - j - 1 alors max_sequence <- c - j - 1 Fin si # Ajout de la séquence dans le tableau T t[longueur_tableau] <- sequence_juxtapose longueur_tableau <- longueur_tableau + 1 Fin si Fin pour Fin pour Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| i | entier |
| j | entier |
| sequence_juxtapose | Enregistrement |
| longueur_tableau | entier (variable globale) |
| sequence_juxtapose | entier (variable globale) |
La procédure afficher_tableau
Cette procédure afficher_tableau(t, index) a pour rôle d’afficher le contenu du tableau T, qui stocke les informations sur les séquences juxtaposées trouvées dans la matrice.
Détail du fonctionnement :
Elle affiche un message indiquant l’affichage du tableau T.
Elle parcourt le tableau T de l’indice 0 jusqu’à index - 1.
Pour chaque élément du tableau des enregistrements, elle affiche : le numéro de la ligne, l’indice de la colonne de début de la séquence, et l’indice de la colonne de fin de la séquence.
Les valeurs sont affichées sur une même ligne pour chaque séquence.
|
1 2 3 4 5 6 |
Procedure afficher_tableau(t:tableau, index:entier) Ecrire('*** Contenu du tableau T ***') Pour i de 0 à index-1 faire Ecrire(t[i]["nl"], ' ', t[i]["icd"], ' ', t[i]["icf"]) Fin pour Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| i | entier |
La procédure remplir_fichier_long_seq
Cette procédure remplir_fichier_long_seq(t, longueur_tableau, max_sequence) a pour rôle de créer et remplir le fichier texte Long_Seq.txt avec les informations relatives aux plus longues séquences d’éléments juxtaposés dont la somme est égale à zéro.
Détail du fonctionnement :
Elle ouvre (ou crée) le fichier Long_Seq.txt en mode écriture.
Elle écrit dans la première ligne du fichier le nombre d’éléments de la plus longue séquence trouvée.
Elle parcourt ensuite le tableau T, qui contient toutes les séquences détectées.
Pour chaque séquence, elle calcule sa longueur à partir des indices de début (icd) et de fin (icf).
Si la longueur de la séquence correspond à la longueur maximale (max_sequence), ses informations sont :
affichées à l’écran,
enregistrées dans le fichier sous la forme : NL#ICD#ICF.
Enfin, le fichier est fermé correctement.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
Procédure remplir_fichier_long_seq(t:tableau, longueur_tableau:entier, max_sequence:entier) Ecrire('*** Contenu du fichier Long_Seq.txt ***') Ouvrir (f , "Long_Seq.txt", "w") # Écriture de la longueur maximale Ecrire(f , "Le nombre d'elt de la plus longue séquence= " , max_sequence , '\n') Ecrire('Le nombre d\'elt de la plus longue séquence= ', max_sequence) # Écriture des séquences correspondantes Pour i de 0 à longueur_tableau-1 faire Si (t[i]["icf"] - t[i]["icd"] + 1) = max_sequence alors Ecrire(t[i]["nl"], '#', t[i]["icd"], '#', t[i]["icf"]) Ecrire(f , t[i]["nl"] , '#' , , t[i]["icd"] , '#' , t[i]["icf"] , '\n') Fin si Fin pour Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| f | fichier |
| i | entier |
Solution en Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 |
from numpy import * # -------------------------------------------------- # Définition des dimensions maximales de la matrice # -------------------------------------------------- lignes = 50 colonnes = 50 # Création d'une matrice M de taille 50x50 initialisée à 0 m = array([[int()] * colonnes] * lignes) # Création d'un tableau T de 50 dictionnaires # Chaque dictionnaire contiendra les informations d’une séquence t = array([{}] * 50) # -------------------------------------------------- # Fonction qui permet de saisir un entier n # compris strictement entre inf et sup # -------------------------------------------------- def saisie(inf, sup): # Première saisie de n n = int(input('donner n tel que ' + str(inf) + '< n < ' + str(sup) + ': ')) # Tant que n n’appartient pas à l’intervalle ]inf , sup[ # on redemande la saisie while (n <= inf) or (n >= sup): n = int(input('donner n tel que ' + str(inf) + '< n < ' + str(sup) + ': ')) # Retourne la valeur correcte return n # -------------------------------------------------- # Fonction qui permet de saisir un entier différent de 0 # -------------------------------------------------- def saisie_element(): # Première saisie n = int(input('donner n tel que n != 0: ')) # Tant que la valeur saisie est nulle, on recommence while (n == 0): n = int(input('donner n tel que n != 0: ')) # Retourne la valeur correcte return n # -------------------------------------------------- # Procedure qui remplit la matrice M # -------------------------------------------------- def remplir_matrice(m, l, c): print('*** Remplir la matrice M ***') for i in range(l): for j in range(c): m[i][j] = saisie_element() # -------------------------------------------------- # Procedure qui affiche la matrice M # -------------------------------------------------- def afficher_matrice(m, l, c): print('*** Contenu de la matrice M ***') for i in range(l): for j in range(c): print(m[i][j], end=' ') print() # -------------------------------------------------- # Fonction qui vérifie l’existence d’une séquence # de valeurs juxtaposées sur une ligne dont la somme est 0 # -------------------------------------------------- def verif_juxtapose(m, numero_ligne, numero_colonne, c): # Initialisation de la somme avec la première valeur s = m[numero_ligne][numero_colonne] i = numero_colonne # Addition des éléments juxtaposés tant que la somme ≠ 0 # et que l’on reste dans la ligne while s != 0 and i < c - 1: i = i + 1 s = s + m[numero_ligne][i] # Si la somme est nulle, retourner l’indice de fin if s == 0: return i else: return -1 # -------------------------------------------------- # Procedure qui remplit le tableau T par les séquences trouvées # -------------------------------------------------- def remplir_tableau(t, m, l, c): global longueur_tableau, max_sequence for i in range(l): for j in range(c - 1): # Vérification de l’existence d’une séquence if verif_juxtapose(m, i, j, c) != -1: sequence_juxtapose = dict( nl=int(), # numéro de ligne icd=int(), # indice de colonne début icf=int() # indice de colonne fin ) # Remplissage du dictionnaire sequence_juxtapose["nl"] = i sequence_juxtapose["icd"] = j sequence_juxtapose["icf"] = verif_juxtapose(m, i, j, c) # Mise à jour de la longueur maximale trouvée if max_sequence < c - j - 1: max_sequence = c - j - 1 # Ajout de la séquence dans le tableau T t[longueur_tableau] = sequence_juxtapose longueur_tableau = longueur_tableau + 1 # -------------------------------------------------- # Procedure qui affiche le contenu du tableau T # -------------------------------------------------- def afficher_tableau(t, index): print('*** Contenu du tableau T ***') for i in range(index): print(t[i]["nl"], ' ', t[i]["icd"], ' ', t[i]["icf"]) # -------------------------------------------------- # Procedure qui crée et remplit le fichier Long_Seq.txt # -------------------------------------------------- def remplir_fichier_long_seq(t, longueur_tableau, max_sequence): print('*** Contenu du fichier Long_Seq.txt ***') f = open("Long_Seq.txt", "w") # Écriture de la longueur maximale f.write("Le nombre d'elt de la plus longue séquence= " + str(max_sequence) + '\n') print('Le nombre d\'elt de la plus longue séquence= ', max_sequence) # Écriture des séquences correspondantes for i in range(longueur_tableau): if (t[i]["icf"] - t[i]["icd"] + 1) == max_sequence: print(t[i]["nl"], '#', t[i]["icd"], '#', t[i]["icf"]) f.write(str(t[i]["nl"]) + '#' + str(t[i]["icd"]) + '#' + str(t[i]["icf"]) + '\n') f.close() # -------------------------------------------------- # Programme principal # -------------------------------------------------- print('*** Saisie de nombre des lignes et de colonnes ***') # Saisie du nombre de lignes et de colonnes l = saisie(0, 23) c = saisie(2, 23) # Initialisation des variables globales longueur_tableau = 0 max_sequence = 0 # Appels des différentes fonctions remplir_matrice(m, l, c) afficher_matrice(m, l, c) remplir_tableau(t, m, l, c) afficher_tableau(t, longueur_tableau) remplir_fichier_long_seq(t, longueur_tableau, max_sequence) |
Exécution du programme
0 commentaire
laisser un commentaire
Passion de robotique
Tutoriels récents
Atelier robotique
Tutoriels populaires
Construction des robots
Tutoriels plus commentés
Bras robotique
Categories
Maison intelligente
