Moteur de recherche – Bac théorique – Section informatique – 2017
Sujet (Algo et programmation - Bac 2017)
On se propose de réaliser un moteur de recherche local permettant de trouver, sur un ordinateur, tous les fichiers textes contenant un ensemble de mots saisis par l'utilisateur.
Pour cela, on dispose d'un fichier texte nommé "Chemin.txt" situé sur la racine du disque C et contenant les chemins d'accès des fichiers textes du disque local de l'ordinateur à raison d'un chemin par ligne, sachant que :
- un chemin d'accès est composé d'au maximum 80 caractères
- le nombre maximum de fichiers texte est égal à 100
Le procédé de recherche consiste à :
- saisir dans un tableau TM les N mots (0 < N < 11) à rechercher. Un mot est formé uniquement par des lettres,
- remplir une matrice M par le nombre de lignes, contenant le mot à rechercher, dans chaque fichier tels que
M[i][j] = nombre de lignes du fichier G contenant le mot à rechercher TM[i]
Où G représente le fichier dont son chemin est indiqué dans la ligne numéro i du fichier "Chemin.txt"
- afficher tous les mots à rechercher suivis par les chemins des fichiers qui les contiennent s'ils existent séparés par un espace.
Travail demandé :
1- Analyser le problème en le décomposant en modules.
2- Ecrire un algorithme solution pour chaque module envisagé. Chaque algorithme proposé doit être accompagné d'un tableau de déclaration des objets
Solution Algorithmique
Dans cet algorithme, On va utiliser quatre fonctions et cinq procédures:
- la fonction saisie()
- la fonction saisie_chemin()
- la procédure remplir_fichier_source()
- la fonction verif_ch()
- la fonction saisie_mot()
- la procédure remplir()
- la procédure remplir_matrice()
- la procédure afficher_matrice()
- la procédure afficher_resultats()
Algorithme du programme Principal
|
1 2 3 4 5 6 7 8 9 10 |
Algorithme moteur_recherche Debut nbr_lignes = saisie(1, 100) # Nombre de fichiers remplir_fichier_source(nbr_lignes) # Saisie des chemins n = saisie(1, 10) # Nombre de mots à rechercher remplir(tm, n) # Saisie des mots remplir_matrice(m, tm, n) # Remplissage de la matrice afficher_matrice(m, nbr_lignes, n) # Affichage de la matrice afficher_resultats(m, tm, tchemins, nbr_lignes, n) Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| nbr_lignes | entier |
| n | entier |
| tm | tableau des chaînes |
| m | matrice des entiers |
| tchemins | tableau des chaînes |
La fonction saisie
Cette fonction permet de demander à l’utilisateur de saisir un nombre entier représentant le nombre de lignes, en s’assurant que cette valeur appartient à l'intervalle [inf,sup].
1- Elle lit une valeur entière saisie au clavier.
2- Elle vérifie la validité de cette valeur.
3- Tant que le nombre saisi n’est pas dans l'intervalle [inf, sup], la saisie est redemandée.
4- Elle retourne finalement un entier valide, utilisable comme nombre de lignes du fichier source.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
Fonction saisie(inf:entier, sup:entier):entier # Saisie initiale Ecrire('donner un nombre entre ' , inf , ' et ' , sup , ' : ') Lire(n) # Vérification de la validité de la saisie Tant que Non (inf <= n <= sup) faire Ecrire('donner un nombre entre ' , inf , ' et ' , sup , ' : ') Lire(n) Fin pour # Retourner le nombre valide retourner n Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| n | entier |
La fonction saisie_chemin
Cette fonction permet de saisir une chaîne de caractères valide, dont la longueur est comprise entre 1 et 120 caractères.
1- Elle demande à l’utilisateur de saisir une chaîne.
2- Elle vérifie que la longueur de la chaîne respecte l’intervalle autorisé [1,80].
3- Tant que la chaîne est vide ou dépasse 120 caractères, la saisie est redemandée.
4- Elle retourne la chaîne correcte, prête à être utilisée par le programme.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
Fonction saisie_chemin():chaine # Saisie du chemin Ecrire('donner un chemin valide : ') Lire(ch) # Vérification de la longueur Tant que Non (1 <= len(ch) <= 80) faire Ecrire('donner un chemin valide : ') Lire(ch) Fin pour # Retourner le chemin valide retourner ch Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| ch | chaîne |
La procédure remplir_fichier_source
Cette procédure permet de créer et remplir le fichier texte Source.txt avec n lignes de texte saisies par l’utilisateur.
1- Elle ouvre (ou crée) le fichier Chemin.txt en mode écriture.
2- Elle demande à l’utilisateur de saisir n chaînes de caractères, chacune représentant un chemin d'accès d'un fichier.
3- Chaque chaîne saisie est écrite dans le fichier suivie d’un retour à la ligne.
4- Elle ferme le fichier après la fin de l’écriture.
|
1 2 3 4 5 6 7 8 9 |
Procedure remplir_fichier_source(n:entier) Ecrire('*** Remplir fichier Chemin.txt ***') Ouvrir(f , "Chemin.txt", "w") # Saisie de n lignes et écriture dans le fichier Pour i de 0 à n-1 faire ch <- saisie_chemin() f.write(ch + '\n') f.close() Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| f | fichier |
| i | entier |
| ch | chaîne |
La fonction verif_ch
Cette fonction permet de tester si une chaîne non vide est constituée uniquement de lettres alphabétiques (majuscule ou minuscule).
1- Si la chaîne est vide, la fonction retourne False.
2- Sinon :
Elle parcourt la chaîne caractère par caractère.
Chaque caractère est converti en majuscule avec la fonction Majus() afin d’accepter les lettres minuscules et majuscules.
Elle vérifie que chaque caractère est compris entre 'A' et 'Z'.
3- La fonction retourne :
Vrai si tous les caractères sont des lettres,
Faux dès qu’un caractère non alphabétique est rencontré.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
Fonction verif_ch(ch:chaine):booleen Si long(ch) != 0 alors i <- 0 # Parcours de la chaîne caractère par caractère Tant que (i < long(ch) - 1) et ('A' <= Majus(ch[i].upper()) <= 'Z') alors i <- i + 1 Fin tant que retourner ('A' <= Majus(ch[i]) <= 'Z') Sinon retourner Faux Fin si Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| i | entier |
La fonction saisie_mot
Cette fonction assure la saisie d’un mot valide, composé uniquement de lettres alphabétiques.
1- La fonction demande à l’utilisateur de saisir un mot.
2- Elle vérifie la validité du mot à l’aide de la fonction verif_ch.
Tant que le mot saisi est vide, ou contient des caractères non alphabétiques
l’utilisateur est invité à ressaisir le mot.
3- Une fois un mot valide saisi, la fonction le retourne.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
fonction saisie_mot():chaine # Saisie du mot Ecrire('donner un mot à rechercher : ') Lire(ch) # Vérification du mot Tant que Non(verif_ch(ch)) faire Ecrire('donner un mot à rechercher : ') Lire(ch) Fin tant que # Retourner le mot valide retourner ch Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| ch | chaîne |
La procédure remplir
Cette procédure permet de remplir un tableau avec n mots valides saisis par l’utilisateur, destinés à être recherchés dans des fichiers.
1- La procédure affiche un message indiquant le début du remplissage du tableau.
2- Elle parcourt les n premières cases du tableau tm.
À chaque itération : elle appelle la fonction saisie_mot pour obtenir un mot valide (composé uniquement de lettres), puis stocke ce mot dans le tableau tm.
|
1 2 3 4 5 6 |
Procedure remplir(tm:tableau, n:entier) Ecrire('*** Remplir le tableau TM ***') Pour i de 0 à n-1 faire tm[i] <- saisie_mot() Fin Pou Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| i | entier |
La procédure remplir_matrice
Cette procédure permet de remplir une matrice dont chaque élément représente le nombre d’occurrences d’un mot donné dans un fichier donné, à partir d’une liste de fichiers fournie dans Chemin.txt.
La procédure ouvre le fichier Chemin.txt, qui contient la liste des chemins des fichiers à analyser.
Chaque ligne de Chemin.txt correspond à un fichier et l’indice i représente le numéro du fichier.
Pour chaque fichier :
1- elle lit toutes ses lignes,
2- puis, pour chaque mot recherché t[j] (avec j variant de 0 à n-1),
3- elle vérifie si le mot apparaît dans une ligne à l’aide de find.
4- À chaque occurrence trouvée, la case m[i][j] est incrémentée.
5- À la fin m[i][j] contient le nombre d’occurrences du mot t[j] dans le fichier numéro i.
|
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 |
Procedure remplir_matrice(m:matrice, t:tableau, n:entier) # Ouverture du fichier contenant les chemins Ouvrir(f_chemins , "Chemin.txt", "r") # Lecture de tous les chemins chemins <- Lire_lignes(f_chemins) i <- -1 # Parcours des fichiers Pour chemin dans chemins faire i <- i + 1 nom_fichier <- chemin.strip('\n') # Ouverture du fichier correspondant Ouvrir(f_fichier , nom_fichier, "r") lignes <- Lire_lignes(f_fichier) # Recherche des mots dans le fichier Pour mots dans lignes faire Pour j de 0 à n-1 faire Si Pos(mots,t[j]) != -1 alors m[i][j] <- m[i][j] + 1 Fin si Fin pour Fin pour # Fermeture du fichier analysé Fermer(f_fichier) # Fermeture du fichier Chemin.txt Fermer(f_chemins) Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| f_chemins | chaîne |
| chemins | chaîne |
| i | entier |
| chemin | chaîne |
| nom_fichier | chaîne |
| lignes | chaîne |
| mots | chaîne |
| j | chaîne |
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 élément 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 afficher_resultats
Cette procédure permet de remplir une matrice dont chaque élément représente le nombre d’occurrences d’un mot donné dans un fichier donné, à partir d’une liste de fichiers fournie dans Chemin.txt.
La procédure ouvre le fichier Chemin.txt, qui contient la liste des chemins des fichiers à analyser.
Chaque ligne de Chemin.txt correspond à un fichier et l’indice i représente le numéro du fichier.
Pour chaque fichier :
1- elle lit toutes ses lignes,
2- puis, pour chaque mot recherché t[j] (avec j variant de 0 à n-1),
3- elle vérifie si le mot apparaît dans une ligne à l’aide de find.
4- À chaque occurrence trouvée, la case m[i][j] est incrémentée.
5- À la fin m[i][j] contient le nombre d’occurrences du mot t[j] dans le fichier numéro i.
|
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 |
Procedure afficher_resultats(m:matrice, tm:tableau, tchemins:tanleau, l:entier, c:entier) Ecrire('*** Les resultats de recherche ***') # Lecture des chemins Ouvrir(f_chemins , "Chemin.txt", "r") chemins <- Lire_lignes(f_chemins) i <- -1 # Remplissage du tableau des chemins Pour chemin dans chemins faire i <- i + 1 tchemins[i] <- chemin.strip('\n') Fin pour # Fermeture du fichier source Fermer(f_chemins) # Affichage des résultats Pour j de 0 à c-1 Ecrire(tm[j], ' ') Pour i de 0 à l-1 faire Si m[i][j] != 0 alors Ecrire(tchemins[i], ' ') Fin si Fin pour Ecrire() Fin pour Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| f_chemins | chaîne |
| chemins | chaîne |
| i | entier |
| chemin | chaîne |
| j | 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 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 |
from numpy import * # -------------------------------------------------- # Définition des dimensions maximales de la matrice # -------------------------------------------------- lignes = 50 # Nombre maximal de lignes de la matrice colonnes = 50 # Nombre maximal de colonnes de la matrice # -------------------------------------------------- # Création des structures de données # -------------------------------------------------- # Matrice M : stocke le nombre d’occurrences de chaque mot # dans chaque fichier m = array([[int()] * colonnes] * lignes) # Tableau tm : contient les mots à rechercher tm = array([{int()}] * 50) # Tableau tchemins : contient les chemins des fichiers tchemins = array([{str}] * 50) # -------------------------------------------------- # Fonction de saisie d’un entier compris entre inf et sup # -------------------------------------------------- def saisie(inf, sup): # Saisie initiale n = int(input('donner un nombre entre ' + str(inf) + ' et ' + str(sup) + ' : ')) # Vérification de la validité de la saisie while not (inf <= n <= sup): n = int(input('donner un nombre entre ' + str(inf) + ' et ' + str(sup) + ' : ')) # Retourner la valeur valide return n # -------------------------------------------------- # Fonction de saisie d’un chemin de fichier valide # (longueur comprise entre 1 et 100 caractères) # -------------------------------------------------- def saisie_chemin(): # Saisie du chemin ch = input('donner un chemin valide : ') # Vérification de la longueur while not (1 <= len(ch) <= 80): ch = input('donner chemin valide : ') # Retourner le chemin valide return ch # -------------------------------------------------- # Procédure qui crée et remplit le fichier Chemin.txt # avec n chemins de fichiers # -------------------------------------------------- def remplir_fichier_source(n): print('*** Remplir fichier Chemin.txt ***') # Ouverture du fichier en écriture f = open("Chemin.txt", "w") # Saisie et écriture des chemins for i in range(n): ch = saisie_chemin() f.write(ch + '\n') # Fermeture du fichier f.close() # -------------------------------------------------- # Fonction qui vérifie si une chaîne est composée # uniquement de lettres alphabétiques # -------------------------------------------------- def verif_ch(ch): if len(ch) != 0: i = 0 # Parcours de la chaîne caractère par caractère while (i < len(ch) - 1) and ('A' <= ch[i].upper() <= 'Z'): i = i + 1 return ('A' <= ch[i].upper() <= 'Z') else: return False # -------------------------------------------------- # Fonction qui permet de saisir un mot valide # à rechercher dans les fichiers # -------------------------------------------------- def saisie_mot(): # Saisie du mot ch = input('donner un mot à rechercher : ') # Vérification du mot while not (verif_ch(ch)): ch = input('donner un mot à rechercher : ') # Retourner le mot valide return ch # -------------------------------------------------- # Procédure qui remplit le tableau tm # avec n mots à rechercher # -------------------------------------------------- def remplir(tm, n): print('*** Remplir le tableau TM ***') for i in range(n): tm[i] = saisie_mot() # -------------------------------------------------- # Procédure qui remplit la matrice M # M[i][j] contient le nombre d’occurrences # du mot tm[j] dans le fichier i # -------------------------------------------------- def remplir_matrice(m, t, n): # Ouverture du fichier contenant les chemins f_chemins = open("Chemin.txt", "r") # Lecture de tous les chemins chemins = f_chemins.readlines() i = -1 # Parcours des fichiers for chemin in chemins: i = i + 1 nom_fichier = chemin.strip('\n') # Ouverture du fichier correspondant f_fichier = open(nom_fichier, "r") lignes = f_fichier.readlines() # Recherche des mots dans le fichier for mots in lignes: for j in range(n): if mots.find(t[j]) != -1: m[i][j] = m[i][j] + 1 # Fermeture du fichier analysé f_fichier.close() # Fermeture du fichier Chemin.txt f_chemins.close() # -------------------------------------------------- # Procédure d’affichage de la matrice M # -------------------------------------------------- def afficher_matrice(m, l, c): print('*** Matrice M ***') for i in range(l): for j in range(c): print(m[i][j], end=' ') print() # -------------------------------------------------- # Procédure d’affichage des résultats de recherche # -------------------------------------------------- def afficher_resultats(m, tm, tchemins, l, c): print('*** Les resultats de recherche ***') # Lecture des chemins f_chemins = open("Chemin.txt", "r") chemins = f_chemins.readlines() i = -1 # Remplissage du tableau des chemins for chemin in chemins: i = i + 1 tchemins[i] = chemin.strip('\n') # Fermeture du fichier source f_chemins.close() # Affichage des résultats for j in range(c): print(tm[j], end=' ') for i in range(l): if m[i][j] != 0: print(tchemins[i], end=' ') print() # -------------------------------------------------- # Programme principal # -------------------------------------------------- nbr_lignes = saisie(1, 100) # Nombre de fichiers remplir_fichier_source(nbr_lignes) # Saisie des chemins n = saisie(1, 10) # Nombre de mots à rechercher remplir(tm, n) # Saisie des mots remplir_matrice(m, tm, n) # Remplissage de la matrice afficher_matrice(m, nbr_lignes, n) # Affichage de la matrice afficher_resultats(m, tm, tchemins, nbr_lignes, 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
