Problème matrice – Bac théorique – Section informatique – 2010
Sujet (Algo et programmation - Bac 2010)
On se propose d'écrire un programme permettant de :
M [1, 0] = 2 + 5 +1 + 8 + 3 + 1 = 20 , M [2, 3] = 12 + 4 = 16
2) Chaque ligne du fichier diagonal.txt contiendra les éléments de M se trouvant sur une diagonale droite, en commençant par celle à gauche et de haut en bas, de telle sorte que :
- La ligne N°1 du fichier contient M [0, 0] c'est à dire 2
- La ligne N°2 du fichier contient M [0, 1] suivi de M [1, 0] c'est-à-dire 520
- La ligne N°3 du fichier contient M [0, 2] suivi de M [1, 1] suivi de M [2, 0] c'est-à-dire 11867
Pour l'exemple précédant, le contenu du fichier diagonal.txt sera comme suit :
7
520
11867
81347159
3122992296
141645137433
et les lignes qui seront affichées sont :
11867
81347159
3122992296
141645137433
En effet :
- La ligne numéro 0 n'est pas affichée car elle ne contient qu'un seul chiffre.
- La ligne numéro 1 n'est pas affichée car on ne trouve que 3 chiffres distincts.
- Les lignes numéro 2, 3, 4 et 5 seront affichées car elles contiennent chacune au moins 4 chiffres distincts.
Travail demandé
1. Analyser le problème en le décomposant en modules et déduire l'algorithme du programme principal qui permet de réaliser le traitement décrit précédemment.
2. Analyser chacun des modules envisagés précédemment et en déduire les algorithmes correspondants.
Solution Algorithmique
Dans cet algorithme, On va utiliser deux fonctions et quatre procédures :
- la fonction saisie()
- la procédure remplir_matrice()
- la procédure afficher_matrice()
- la fonction test_different()
- la procédure remplir_fichier_diagonal()
- la procédure afficher_fichier()
Algorithme du programme Principal
|
1 2 3 4 5 6 7 8 9 10 11 |
Algorithme matrice_diagonale Debut # Saisie de la dimension de la matrice n <- saisie() # Remplissage de la matrice remplir_matrice(m, n) # Affichage de la matrice afficher_matrice(m, n) # Traitement des diagonales et sauvegarde dans un fichier remplir_fichier_diagonal(m, n) Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| n | entier |
| m | matrice |
La fonction saisie
Ce programme permet de saisir un entier n compris entre 5 et 10 inclus, en contrôlant la validité de la saisie.
Il redemande la valeur tant que l’utilisateur entre un nombre en dehors de l’intervalle [5, 10], puis retourne la valeur correcte une fois la condition respectée.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
Fonction saisie(): entier # Saisie d’un entier n Ecrire('donner n telque 5<=n<=10: ') Lire(n) # Vérification de l’intervalle Tant que (n < 5) ou (n > 10) faire Ecrire('donner n telque 5<=n<=10: ') Lire(n) Fin tant que # Retourner la valeur valide return n Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| n | entier |
La procédure remplir_matrice
Cette procédure permet de remplir une matrice m de dimension n × n de la manière suivante :
- La première ligne de la matrice est remplie par des nombres aléatoires compris entre 1 et 9.
Chaque élément des lignes suivantes est calculé comme la somme des éléments de la ligne précédente, depuis une colonne donnée jusqu’à la dernière colonne.
La matrice obtenue a une forme triangulaire, car seules les premières colonnes de chaque ligne sont remplies.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
Procédure remplir_matrice(m, n) # Remplissage de la première ligne avec des valeurs aléatoires entre 1 et 9 Pour j de 0 à n-1 faire m[0][j] <- Alea(1, 9) Fin pour # Remplissage des autres lignes Pour i de 1 à n-1 faire Pour j de 0 à n-i-1 faire somme <- 0 # Calcul de la somme des éléments de la ligne précédente # à partir de la colonne j jusqu'à la fin Pour k de j à n-1 faire somme <- somme + m[i - 1][k] Finpour # Affectation de la somme à la case m[i][j] m[i][j] <- somme Fin pour Fin pour Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| i | entier |
| j | entier |
| k | entier |
| somme | entier |
La procédure afficher_matrice
Cette procédure est d’afficher le contenu d’une matrice carrée M de taille n × n à l’écran de manière lisible.
Elle reçoit : m : une matrice (tableau à deux dimensions) et n : la dimension de la matrice (nombre de lignes et de colonnes).
Elle affiche d’abord un titre : “Matrice M”.
Ensuite , la première boucle Pour parcourt les lignes de la matrice et la deuxième boucle Pour parcourt les colonnes de chaque ligne.
chaque élément m[i][j] est affiché sur la même ligne.
Enfin écrire() permet de passer à la ligne suivante après chaque ligne de la matrice.
|
1 2 3 4 5 6 7 8 9 10 |
Procédure afficher_matrice(m:matrice, n:entier) Ecrire('****** Matrice M ******') # Parcours de la matrice et affichage des valeurs Pour i de 0 à n-1 faire Pour j de 0 à n-1 faire Ecrire(m[i][j]) Finpour Ecrire() # retour a la ligne Finpour Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| i | entier |
| j | entier |
La fonction test_different
Le rôle de ce fonction est de vérifier si une chaîne de caractères contient au moins trois chiffres (ou caractères) différents, à condition que la chaîne ait une longueur minimale de 4.
1- La fonction test_different(ch) reçoit une chaîne de caractères ch.
2- Elle vérifie d’abord que la longueur de la chaîne est au moins 4.
3- Elle parcourt ensuite la chaîne caractère par caractère :
- à chaque position i, elle supprime le caractère ch[i] pour former une nouvelle chaîne ch1,
- elle teste si ce caractère n’existe plus dans ch1,
- si c’est le cas, cela signifie que ce caractère est différent des autres, et le compteur cp est incrémenté.
- La boucle s’arrête dès que 3 caractères différents sont trouvés ou que la chaîne est entièrement parcourue.
4- La fonction retourne :
Vrai si au moins 3 caractères différents sont détectés,
Faux sinon (ou si la chaîne contient moins de 4 caractères).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
Fonction test_different(ch:chaine):booleen # La chaîne doit contenir au moins 4 caractères Si long(ch) >= 4 alors cp <- 0 # Compteur de chiffres différents i <- 0 # Parcours de la chaîne Tant que cp < 3 and i < long(ch) faire # Supprimer le caractère ch[i] ch1 = Sous_chaine(ch,0,i) + Sous_chaine(ch,i+1,long(ch)] # Vérifier si le caractère supprimé n’existe plus Si Pos(ch1,ch[i]) < 0 alors cp <- cp + 1 Fin si i <- i + 1 Fin tant que # Retourne True si au moins 3 chiffres sont différents returner cp <- 3 Sinon retourner Faux Finsi Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| cp | entier |
| i | entier |
| ch1 | chaîne |
La procédure remplir_fichier_diagonal
Le rôle de cette procédure est de construire les diagonales d’une matrice carrée, de les sauvegarder dans un fichier texte et d’afficher celles qui contiennent au moins trois chiffres différents.
La procédure remplir_fichier_diagonal(m, n) reçoit : m : une matrice carrée de taille n × n et n : la dimension de la matrice.
1- Elle ouvre le fichier diagonal.txt en mode écriture.
2- Pour chaque indice i de 0 à n−1 :
- elle construit une chaîne ligne contenant les éléments de la diagonale secondaire partielle définie par
m[j][i − j] pour j allant de 0 à i,
- les éléments de la diagonale sont concaténés sous forme de chiffres.
- Elle utilise la fonction test_different(ligne) pour vérifier si la chaîne contient au moins 3 chiffres différents : si oui, la diagonale est affichée à l’écran.
- Chaque diagonale construite est ensuite écrite dans le fichier diagonal.txt, qu’elle respecte la condition ou non.
3- Enfin, le fichier est fermé.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
Procédure remplir_fichier_diagonal(m:matrice, n:entier) # Ouverture du fichier en écriture Ouvrir(f ,"diagonal.txt", "w") Ecrire('\nLes lignes contenant des chiffres qui ont au moins 3 chiffres différents') # Parcours des diagonales de la matrice Pour i de 0 à n-1 faire ligne <- '' # Construction de la chaîne à partir de la diagonale Pour j de 0 à i + 1 faire ligne <- ligne + Convch(m[j][i - j]) Fin pour # Test si la chaîne contient au moins 3 chiffres différents Si test_different(ligne) alors Ecrire(ligne) Finsi # Écriture de la chaîne dans le fichier Ecrire(f, ligne + '\n') Finpour # Fermeture du fichier Fermer(f_) Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| f | fichier |
| ligne | chaîne |
| i | entier |
| j | 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 |
from numpy import * import random # Dimensions maximales de la matrice lignes = 50 colonnes = 50 # Matrice M : contiendra les valeurs calculées (distances/sommes) m = array([[int()] * colonnes] * lignes) # =================================== # Fonction pour saisir un entier n # =================================== def saisie(): # Saisie d’un entier n n = int(input('donner n telque 5<=n<=10: ')) # Vérification de l’intervalle while (n < 5) or (n > 10): n = int(input('donner n telque 5<=n<=10: ')) # Retourner la valeur valide return n # ========================================= # Construction de la matrice M # ========================================= def remplir_matrice(m, n): # Remplissage de la première ligne avec des valeurs aléatoires entre 1 et 9 for j in range(n): m[0][j] = random.randint(1, 9) # Remplissage des autres lignes for i in range(1, n): for j in range(0, n - i): somme = 0 # Calcul de la somme des éléments de la ligne précédente # à partir de la colonne j jusqu'à la fin for k in range(j, n): somme = somme + m[i - 1][k] # Affectation de la somme à la case m[i][j] m[i][j] = somme # ========================================= # Affichage de la matrice M # ========================================= def afficher_matrice(m, n): print('****** Matrice M ******') # Parcours de la matrice et affichage des valeurs for i in range(n): for j in range(n): print(m[i][j], end=' ') print() # ===================================================== # Vérifie si une chaîne contient au moins 3 chiffres # différents # ===================================================== def test_different(ch): # La chaîne doit contenir au moins 4 caractères if len(ch) >= 4: cp = 0 # Compteur de chiffres différents i = 0 # Parcours de la chaîne while cp < 3 and i < len(ch): # Supprimer le caractère ch[i] ch1 = ch[0:i] + ch[i + 1:len(ch)] # Vérifier si le caractère supprimé n’existe plus if ch1.find(ch[i]) < 0: cp = cp + 1 i = i + 1 # Retourne True si au moins 3 chiffres sont différents return cp == 3 else: return False # ===================================================== # Construction et sauvegarde des diagonales # ===================================================== def remplir_fichier_diagonal(m, n): # Ouverture du fichier en écriture f = open("diagonal.txt", "w") print('\nLes lignes contenant des chiffres qui ont au moins 3 chiffres différents') # Parcours des diagonales de la matrice for i in range(n): ligne = '' # Construction de la chaîne à partir de la diagonale for j in range(i + 1): ligne = ligne + str(m[j][i - j]) # Test si la chaîne contient au moins 3 chiffres différents if test_different(ligne): print(ligne) # Écriture de la chaîne dans le fichier f.write(ligne + '\n') # Fermeture du fichier f.close() # ============================ # PROGRAMME PRINCIPAL # ============================ # Saisie de la dimension de la matrice n = saisie() # Remplissage de la matrice remplir_matrice(m, n) # Affichage de la matrice afficher_matrice(m, n) # Traitement des diagonales et sauvegarde dans un fichier remplir_fichier_diagonal(m, n) |
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
