Problème matrice – Bac théorique – Section informatique – 2022
Sujet (Algo et programmation - Bac 2022)
Une séquence contigüe dans une matrice carrée M de NxN entiers, est une séquence formée d'au moins deux éléments successifs se trouvant sur la même ligne et dont leur somme est égale à zéro.
A partir d’une matrice M remplie aléatoirement, on se propose de remplir un fichier texte F par les positions des séquences contigües, se trouvant dans les lignes de cette matrice, comme suit :
- Dans la première ligne du fichier F, écrire le titre "Les séquences contigües des lignes".
- Pour chaque séquence contigüe trouvée, écrire ses positions dans une ligne du fichier F en les
séparant par des espaces sachant que les positions d’une séquence sont :
- Le numéro de la ligne de la matrice où se trouve la séquence.
- Le numéro de la colonne de début de la séquence.
- Le numéro de la colonne de fin de la séquence.
Travail demandé
1. Analyser le problème en le décomposant en modules.
2. Ecrire les algorithmes des modules envisagés.
Solution Algorithmique
Dans cet algorithme, On va utiliser une fonction et trois procédures :
- la fonction saisie()
- la procédure remplir_matrice()
- la procédure afficher_matrice()
- la procédure remplir_fichier_contigu()
Algorithme du programme Principal
|
1 2 3 4 5 6 7 |
Algorithme sequences_contigues Debut n <- saisie() # Saisie de la taille de la matrice remplir_matrice(m, n) # Remplissage de la matrice afficher_matrice(m, n) # Affichage de la matrice remplir_fichier_contigu(m, n)# Enregistrement des séquences contiguës Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| n | entier |
| m | matrice |
La fonction saisie()
La fonction saisie() sert à demander à l’utilisateur de saisir un entier valide n supérieur ou égal à 2, puis à vérifier cette saisie avant de la retourner.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
Fonction saisie(longueur:entier):entier # Demande à l'utilisateur de saisir un entier n Ecrire('donner n >= 2 : ') Lire(n) # Vérification de la validité de la saisie # Tant que n est inférieur à 2, on redemande la saisie Tant que Non (n >= 2) faire Ecrire('donner n >= 2 : ') Lire(n) Fin tant que # Retourne la valeur valide de n retourner n Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| n | entier |
La procédure remplir_matrice
La procédure remplir_matrice(m, n) sert à remplir une matrice carrée m de taille n × n avec des nombres entiers aléatoires non nuls compris entre –100 et 100.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
Procédure remplir_matrice(m:matrice ; n:entier) Pour i de 0 à n-1 faire Pour j de 0 à n-1 faire # Générer un entier aléatoire entre -100 et 100 m[i][j] <- Alea(-100, 100) # Recommencer tant que la valeur générée est égale à 0 Tant que m[i][j] = 0 faire m[i][j] <- Alea(-100, 100) Fin tant que Fin pour Fin pour Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| i | entier |
| j | entier |
La procédure afficher_matrice
La procédure afficher_matrice(m, n) sert à afficher à l’écran le contenu d’une matrice carrée m de taille n × n, de façon claire et organisée.
|
1 2 3 4 5 6 7 8 |
Procédure afficher_matrice(m:matrice ; n:entier) Pour i de 0 à n-1 faire Pour j de 0 à n-1 faire Ecrire(m[i][j],' ') Fin pour Ecrire() Fin pour Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| i | entier |
| j | entier |
La procédure remplir_fichier_contigu
La procédure remplir_fichier_contigu(m, n) sert à rechercher, dans chaque ligne de la matrice m, les séquences contiguës dont la somme des éléments est égale à 0, puis à enregistrer ces séquences dans un fichier texte.
|
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 |
Procédure remplir_fichier_contigu(m:matrice, n:entier) Ecrire('*** Contenu du fichier contigu ***') # Ouverture du fichier en écriture Ouvrir(f , "sequence_contigue.txt", "w") Pour i de 0 à n-1 faire Pour j de 0 à n - 2 faire somme <- m[i][j] # Initialisation de la somme sequence <- Convch(i) + ' ' + Convch(j) k <- j # Recherche d'une séquence contiguë Tant que (k < n - 1) et (somme != 0) faire k <- k + 1 somme <- somme + m[i][k] Fin tant que # Si la somme est nulle, écrire la séquence dans le fichier Si somme = 0 alors sequence <- sequence + ' ' + Convch(k) Ecrire(f, sequence + '\n') Ecrire(sequence) Fin si Fin tant que # Fermeture du fichier Fermer(f) Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| i | entier |
| j | entier |
| k | entier |
| somme | entier |
| sequence | chaîne |
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 |
from numpy import * import random # Module nécessaire pour la génération de nombres aléatoires # -------------------------------------------------- # Définition des dimensions maximales de la matrice # -------------------------------------------------- lignes = 50 # Nombre maximal de lignes colonnes = 50 # Nombre maximal de colonnes # -------------------------------------------------- # Création d'une matrice m de taille 50x50 # Initialisée avec des entiers (0 par défaut) # -------------------------------------------------- m = array([[int()] * colonnes] * lignes) # -------------------------------------------------- # Fonction de saisie d’un entier n (n >= 2) # -------------------------------------------------- def saisie(): # Demande à l'utilisateur de saisir un entier n n = int(input('donner n >= 2 : ')) # Vérification de la validité de la saisie # Tant que n est inférieur à 2, on redemande la saisie while not (n >= 2): n = int(input('donner n >= 2 : ')) # Retourne la valeur valide de n return n # -------------------------------------------------- # Procédure qui remplit la matrice m de taille n×n # avec des nombres aléatoires non nuls # -------------------------------------------------- def remplir_matrice(m, n): for i in range(n): for j in range(n): # Générer un entier aléatoire entre -100 et 100 m[i][j] = random.randint(-100, 100) # Recommencer tant que la valeur générée est égale à 0 while m[i][j] == 0: m[i][j] = random.randint(-100, 100) # -------------------------------------------------- # Procédure qui affiche la matrice m de taille n×n # -------------------------------------------------- def afficher_matrice(m, n): print('*** Contenu de la matrice M ***') for i in range(n): for j in range(n): # Affichage des éléments sur la même ligne print(m[i][j], end=' ') # Passage à la ligne suivante print() # -------------------------------------------------- # Procédure qui enregistre les séquences contiguës # dont la somme est égale à 0 dans un fichier texte # -------------------------------------------------- def remplir_fichier_contigu(m, n): print('*** Contenu du fichier contigu ***') # Ouverture du fichier en écriture f = open("sequence_contigue.txt", "w") for i in range(n): for j in range(n - 1): somme = m[i][j] # Initialisation de la somme sequence = str(i) + ' ' + str(j) k = j # Recherche d'une séquence contiguë while (k < n - 1) and (somme != 0): k = k + 1 somme = somme + m[i][k] # Si la somme est nulle, écrire la séquence dans le fichier if somme == 0: sequence = sequence + ' ' + str(k) f.write(sequence + '\n') print(sequence) # Fermeture du fichier f.close() # -------------------------------------------------- # Programme principal # -------------------------------------------------- n = saisie() # Saisie de la taille de la matrice remplir_matrice(m, n) # Remplissage de la matrice afficher_matrice(m, n) # Affichage de la matrice remplir_fichier_contigu(m, n)# Enregistrement des séquences contiguës |
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
