Tri des fichiers – Bac pratique – Section informatique – 2018
Sujet (Algo et programmation - Bac 2018)
Soit "Source.txt" un fichier texte rempli par des entiers de l’intervalle [0,255], suivi chacun par un seul espace, représentant des codes de couleurs en décimal. Ce fichier contient au maximum 20 lignes composée chacune de 10 entiers.
Afin d’obtenir un fichier texte "Resultat.txt" représentant une palette de couleurs triées de la plus claire àla plus foncée, du haut en bas, on procède comme suit : - transférer le contenu de chaque ligne du fichier "Source.txt" vers une ligne d’une matrice M àraison d’un entier par case, - trier dans l’ordre croissant le contenu de chaque colonne de la matrice M,
- transférer le contenu de chaque ligne de la matrice M, après le tri, vers une ligne du fichier "Resultat.txt" tout en ajoutant un espace de séparation après chaque entier.
Exemple : Pour le contenu du fichier "Source.txt" suivant :
En utilisant l'éditeur de texte disponible (Bloc-notes, Notepad, Notepad++, ...), créer dans le dossier de travail le fichier texte "txt" et y saisir le contenu présenté dans l'exemple en respectant le contenu de chaque ligne.
Soit la procédure Tri_Rapide ci-dessous, écrite en langage Pascal, qui permet de trier dans l’ordre croissant un tableau T dont les indices des cases sont dans l’intervalle [d,f].
Ecrire un programme en Python intitulé "Palette" permettant :
- de transférer le contenu du fichier "source.txt" vers une matrice M comme décrit précédemment,
- d’utiliser le module Tri_Rapide pour trier dans l’ordre croissant chaque colonne de la matrice M,
- de transférer le contenu de la matrice M, après le tri, vers un fichier "source.txt" comme décrit précédemment,
- d'afficher le contenu du fichier "source.txt".
Solution Algorithmique
Dans cet algorithme, On va utiliser cinq procédures:
- la procédure remplir_matric()
- la procédure afficher_matrice()
- la procédure tri_rapide()
- la procédure tri_matrice()
- la procédure remplir_fichier_resultat()
Algorithme du programme Principal
|
1 2 3 4 5 6 7 8 9 10 11 |
Algorithme Palette Debut ligne <- 0 # Initialisation du compteur de lignes remplir_matrice(m) # Remplissage de la matrice depuis le fichier Ecrire('*** Matrice M ***') afficher_matrice(m, ligne, 10) tri_matrice(m, ligne, t) # Tri des colonnes de la matrice Ecrire('*** Matrice M triee ***') afficher_matrice(m, ligne, 10) remplir_fichier_resultat(m, ligne) # Sauvegarde du résultat dans un fichier Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| ligne | entier |
| m | matrice |
| t | tableau |
La procédure remplir_matrice
Cette procédure sert à lire le contenu du fichier texte Source.txt et à stocker les nombres qu’il contient dans une matrice m, ligne par ligne.
1- Elle ouvre le fichier Source.txt en mode lecture.
2- Elle lit toutes les lignes du fichier.
Pour chaque ligne :
- Elle supprime le caractère de fin de ligne (\n).
- Elle extrait les nombres entiers séparés par des espaces.
- Elle place ces nombres successivement dans les colonnes de la matrice m sur la ligne courante.
- Après avoir rempli une ligne de la matrice, elle passe à la ligne suivante.
- Elle utilise la variable globale ligne pour compter le nombre de lignes déjà remplies.
3- Enfin, elle ferme le fichier.
|
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 |
Procedure remplir_matrice(m:matrice) colonne <- 0 # Indice de colonne # Ouverture du fichier source en lecture Ouvrir(f_source , "Source.txt", "r") # Lecture de toutes les lignes du fichier listes <- Lire_lignes(f_source) # Parcours de chaque ligne du fichier Pour liste dans listes: liste <- liste.strip('\n') # Suppression du saut de ligne nbr <- '' # Variable pour stocker un nombre # Extraction des nombres séparés par des espaces Tant que Pos(liste,' ') != -1 faire nbr <- Sous_chaine(liste , 0 , Pos(liste' ')) liste <- Sous_chaine(liste, Pos(liste,' ')+1 , long(liste)) m[ligne][colonne] = Valeur(nbr) # Stockage dans la matrice colonne <- colonne + 1 Fin tant que # Stockage du dernier nombre de la ligne m[ligne][colonne] <- int(liste) # Passage à la ligne suivante ligne <- ligne + 1 colonne <- 0 Fin tant que # Fermeture du fichier Fermer(f_source) Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| colonne | entier |
| f_source | fichier |
| listes | chaîne |
| liste | chaîne |
| nbr | chaîne |
| ligne | entier(variable globale) |
La procédure afficher_matrice
Cette procédure affiche à l’écran les éléments de la matrice de caractères ligne par ligne.
1- Elle parcourt la matrice selon le nombre de lignes l et de colonnes c.
2- Elle affiche chaque caractère de la matrice avec un espace entre les éléments.
3- Elle passe à la ligne après l’affichage de chaque ligne de la matrice.
|
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 procédure tri_rapide
Cette procédure permet de trier un tableau t par ordre croissant en utilisant l’algorithme du tri rapide (Quick Sort).
1- Elle choisit un pivot (l’élément du milieu du sous-tableau).
2- Elle place ce pivot au début du sous-tableau.
3- Elle partitionne le tableau :
- Tous les éléments inférieurs au pivot sont déplacés à gauche.
- Les éléments supérieurs ou égaux restent à droite.
- Elle remet ensuite le pivot à sa position définitive dans le tableau.
4- Elle applique récursivement le même traitement au sous-tableau situé à gauche du pivot, puis au sous-tableau situé à droite du pivot
|
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 tri_rapide(d:entier, f:entier, t:tableau) Si f > d alors m <- (d + f) div 2 # Choix du pivot x <- t[m] t[m] <- t[d] t[d] <- x p <- d Pour i de d + 1 à f faire Si t[i] < t[d] alors p <- p + 1 x <- t[i] t[i] <- t[p] t[p] <- x Fin si Fin pour # Placement du pivot à sa position finale x <- t[p] t[p] <- t[d] t[d] <- x # Appels récursifs tri_rapide(d, p - 1, t) tri_rapide(p + 1, f, t) Fin si Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| m | entier |
| x | entier |
| p | entier |
La procédure tri_matrice
Cette procédure sert à trier séparément chaque colonne de la matrice m par ordre croissant.
Elle parcourt les 10 premières colonnes de la matrice.
Pour chaque colonne :
1- Elle copie les éléments de cette colonne dans le tableau temporaire t.
2- Elle applique la procédure tri_rapide pour trier le tableau t.
3- Elle recopie ensuite les valeurs triées de t dans la colonne correspondante de la matrice m.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
Procédure tri_matrice(m:matrice, ligne:entier, t:tableau) # Parcours des 10 premières colonnes Pour j de 0 à 9 faire # Copier la colonne j dans le tableau t Pour i de 0 à ligne-1 faire t[i] <- m[i][j] Fin pour # Tri de la colonne tri_rapide(0, ligne - 1, t) # Recopie de la colonne triée dans la matrice Pour i de 0 à ligne-1 faire m[i][j] <- t[i] Fin pour Fin pour Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| i | entier |
| j | entier |
La procédure remplir_fichier_resultat
Cette procédure permet d’écrire le contenu de la matrice m (déjà triée) dans le fichier texte Resultat.txt.
1- Elle ouvre le fichier Resultat.txt en mode écriture.
2- Elle parcourt la matrice ligne par ligne.
Pour chaque ligne, elle construit une chaîne contenant les 10 valeurs de la ligne, séparées par des espaces et écrit cette chaîne dans le fichier, suivie d’un saut de ligne.
3- Enfin, elle ferme le fichier.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
Procedure remplir_fichier_resultat(m:matrice , ligne:entier) # Ouverture du fichier en écriture Ouvrir(f ,"Resultat.txt", "w") # Écriture ligne par ligne Pour i de 0 à ligne-1 faire liste <- '' Pour j de 0 à 9 faire liste <- liste + Convch(m[i][j]) + ' ' Fin pour Ecrire(f , liste + '\n') Fin pour # Fermeture du fichier Fermer(f) Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| f | fichier |
| i | entier |
| j | entier |
| liste | 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 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 |
from numpy import * # -------------------------------------------------- # Définition des dimensions maximales de la matrice # -------------------------------------------------- lignes = 100 # Nombre maximal de lignes colonnes = 100 # Nombre maximal de colonnes # -------------------------------------------------- # Création d'une matrice m de taille 100x100 # Initialisée avec des entiers (0 par défaut) # -------------------------------------------------- m = array([[int()] * colonnes] * lignes) # -------------------------------------------------- # Tableau temporaire t utilisé pour le tri # -------------------------------------------------- t = array([int()] * 100) # -------------------------------------------------- # Procédure qui lit le fichier "Source.txt" # et remplit la matrice m ligne par ligne # -------------------------------------------------- def remplir_matrice(m): global ligne # Compteur du nombre de lignes remplies colonne = 0 # Indice de colonne # Ouverture du fichier source en lecture f_source = open("Source.txt", "r") # Lecture de toutes les lignes du fichier listes = f_source.readlines() # Parcours de chaque ligne du fichier for liste in listes: liste = liste.strip('\n') # Suppression du saut de ligne nbr = '' # Variable pour stocker un nombre # Extraction des nombres séparés par des espaces while liste.find(' ') != -1: nbr = liste[0:liste.find(' ')] liste = liste[liste.find(' ') + 1:len(liste)] m[ligne][colonne] = int(nbr) # Stockage dans la matrice colonne = colonne + 1 # Stockage du dernier nombre de la ligne m[ligne][colonne] = int(liste) # Passage à la ligne suivante ligne = ligne + 1 colonne = 0 # Fermeture du fichier f_source.close() # -------------------------------------------------- # Procédure qui affiche une matrice # l : nombre de lignes # c : nombre de colonnes # -------------------------------------------------- def afficher_matrice(m, l, c): for i in range(l): for j in range(c): print(m[i][j], end=' ') print() # -------------------------------------------------- # Procédure de tri rapide (Quick Sort) # d : indice de début # f : indice de fin # t : tableau à trier # -------------------------------------------------- def tri_rapide(d, f, t): if f > d: m = (d + f) // 2 # Choix du pivot x = t[m] t[m] = t[d] t[d] = x p = d for i in range(d + 1, f + 1): if t[i] < t[d]: p = p + 1 x = t[i] t[i] = t[p] t[p] = x # Placement du pivot à sa position finale x = t[p] t[p] = t[d] t[d] = x # Appels récursifs tri_rapide(d, p - 1, t) tri_rapide(p + 1, f, t) # -------------------------------------------------- # Procédure qui trie chaque colonne de la matrice # -------------------------------------------------- def tri_matrice(m, ligne, t): # Parcours des 10 premières colonnes for j in range(10): # Copier la colonne j dans le tableau t for i in range(ligne): t[i] = m[i][j] # Tri de la colonne tri_rapide(0, ligne - 1, t) # Recopie de la colonne triée dans la matrice for i in range(ligne): m[i][j] = t[i] # -------------------------------------------------- # Procédure qui écrit la matrice triée # dans le fichier "Resultat.txt" # -------------------------------------------------- def remplir_fichier_resultat(m, ligne): # Ouverture du fichier en écriture f = open("Resultat.txt", "w") # Écriture ligne par ligne for i in range(ligne): liste = '' for j in range(10): liste = liste + str(m[i][j]) + ' ' f.write(liste + '\n') # Fermeture du fichier f.close() # -------------------------------------------------- # Programme principal # -------------------------------------------------- ligne = 0 # Initialisation du compteur de lignes remplir_matrice(m) # Remplissage de la matrice depuis le fichier print('*** Matrice M ***') afficher_matrice(m, ligne, 10) tri_matrice(m, ligne, t) # Tri des colonnes de la matrice print('*** Matrice M triee ***') afficher_matrice(m, ligne, 10) remplir_fichier_resultat(m, ligne) # Sauvegarde du résultat dans un fichier |
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
