Recherche dans un tableau – Bac Pratique 2015 [ Algorithme + Python ]
Travail demandé
Une chaine est dite existante dans un tableau de chaine si elle peut être formée à partit de la concaténation des ièmes carcatères des différents éléments de ce tableau.
Exemple : pour n=5 et le tableau suivant : t
| SALAH | AMIRA | BILEL | ANWAR | KARIM |
Pour ch=’’AMINA’’ le programme affiche chaine existante dans T car elle est le résultat de la concaténation des 2èmes carcatères des différents éléments de T
Pour ch=’’SALWA’’ le programme affiche chaine inexistante dans T car aucune cocaténation des ième caractères de T ne forme ch.
Ecrire un programme Python qui permet de saisir un entier n (5≤n≤10) et une chaine ch composée de lettres majuscules, puis de remplir un tableau T par n chaine de lettres et de même longueur que ch et de vérifier l’existence de ch dans T comme décrit ci-dessus.
Solution Algorithmique
Pour résoudre ce problème, il faut concevoir un algorithme qui vérifie si une chaîne ch peut être formée par la concaténation des ièmes caractères des différentes chaînes d'un tableau T. Voici un principe pour construire cet algorithme :
1- Initialisation et saisie des données :
Lire la chaîne ch composée de lettres majuscules.
Lire un entier n (avec 5≤n≤105 \leq n \leq 10).
Initialiser un tableau T de n chaînes, chacune de longueur ch.
2- Saisie des chaînes dans le tableau T :
Pour chaque indice i de 1 à n, lire une chaîne T[i] de longueur ch et la stocker dans le tableau.
3- Vérification de l'existence de ch :
a) Initialiser une chaîne ch1
b) Initialiser une variable booléenne existence à Vrai.
c) Parcourir chaque caractère de la chaîne ch :
d) Pour chaque i allant de 0 à n-1, ajouter le ième caractère de T[i]à ch1.
Si ch1 ne correspond pas à ch1, mettre existence à Faux et arrêter la boucle et retourner à l'étape c.
Si la variable existence est toujours à Vrai, alors ch existe dans T selon les critères donnés, sinon elle n'existe pas.
4- Affichage du résultat :
Si existence est Vrai, afficher "chaine existante dans T".
Sinon, afficher "chaine inexistante dans T".
Dans cet algorithme, On va utiliser 4 fonctions et 2 procédures :
Algorithme du programme principal
|
1 2 3 4 5 6 7 8 9 10 11 12 |
Algorithme recherche Debut ch<-saisie_ch() n<-saisie_taille() Ecrire('remplissage du tableau t') remplir(t,n,ch) Si recherche_existence(t,n,ch) alors Ecrire(ch+' est une chaine existante dans T ') Sinon Ecrire(ch+' est une chaine inexistante dans T ') Fin si Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| n | entier |
| ch | chaîne des caractères |
| t | tableau des 20 chaînes des caractères |
La fonction saisie_taille
Cette fonction retourne un entier n entre 5 et 10 saisi par l'utilisateur.
|
1 2 3 4 5 6 7 8 9 10 |
foncttion saisie_taille():entier Début Ecrire('donner un entier entre 5 et 10') lire (n) Tant que n<5 ou n>10 faire Ecrire('donner un entier entre 5 et 10') lire (n) Fin tant que retourner n Fin |
Déclaration des objets
Objet | Type / Nature |
n | entier |
La fonction saisie_ch
Cette fonction retourne une chaîne de caractères formée des lettres majuscules.
|
1 2 3 4 5 6 7 8 9 10 |
foncttion saisie_ch():chaine Début Ecrire('donner une chaine composee des lettres majuscules:') lire (ch) Tant que (verif_majus(ch)==Faux) faire Ecrire('donner une chaine composee des lettres majuscules:') lire (ch) Fin tant que retourner ch Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| ch | chaine des caracteres |
La fonction verif_majus
Cette fonction vérifie si une chaine est composé uniquement des lettres majuscules ou non.
|
1 2 3 4 5 6 7 8 9 10 11 |
foncttion verif_majus(ch:chaine):booleen Début i<-0 Tant que ('A'<=ch[i]<='Z') et (i<len(ch)-1) faire i<-i+1 Fin tant que Si ('A'<=ch[i]<='Z') alors retourner Vrai Sinon retuurner Faux Fin |
Déclaration des objets
Objet | Type / Nature |
i | entier |
La procédure remplir
Cette procédure remplit le tableau t des mots composé uniquement des lettres majuscules et dont ses longueurs sont égaux à long de ch
|
1 2 3 4 5 6 7 8 9 10 11 |
Procédure remplir(@t:Tab,n:entier,ch:chaine) Début Pour i de 0 à n-1 faire Ecrire(""donner elt en majuscule N° "+str(i)+" dont sa long="+long(ch)) lire(t[i]) Tant que (long(t[i])!=long(ch)) ou (verif_majus(t[i])=Faux) faire Ecrire(""donner elt en majuscule N° "+str(i)+" dont sa long="+long(ch)) lire(t[i]) Fin tant que Fin pour Fin |
Déclaration des objets
Objet | Type / Nature |
i | entier |
La fonction recherche_existence
Cette fonction recherche l'existence d'un mot donné dans un tableau T des chaînes de caractères.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
Fonction recherche_existence(t:Tab;n:entier;ch:chaine):booleen Début existence<-Faux i<- -1 Tant que (existence==Faux) et i<long(ch)-1 faire i<-i+1 ch1<-'' Pour j de 0 à n-1 faire ch2<-t[j] ch1<-ch1+ch2[i] Fin pour Si ch=ch1 alors existence<-Vrai Fin si Fin tant que retourner existence Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| i | entier |
| j | entier |
| ch1 | chaîne des caractères |
| ch2 | chaîne des caractères |
| existence | booléen |
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 |
from numpy import array t=array([str]*30) #declaration du tableau des chaines def verif_majus(ch): i=0 while ('A'<=ch[i]<='Z') and (i<len(ch)-1): i=i+1 if ('A'<=ch[i]<='Z'): return True else: return False def saisie_ch() : ch=input("donner une chaine composee des lettres majuscules: ") while(verif_majus(ch)==False) : ch=input("donner une chaine composee des lettres majuscules: ") return ch def saisie_taille() : n=int(input("donner un entier entre 5 et 10: ")) while(n<5) or (n>10) : n=int(input("donner un entier entre 5 et 10: ")) return n def remplir(t,n,ch): for i in range (n) : t[i]=input("donner elt en majuscule N° "+str(i)+" dont sa longueur="+str(len(ch))+': ') while (len(t[i])!=len(ch)) or (verif_majus(t[i])==False) : t[i]=input("donner elt en majuscule N° "+str(i)+" dont sa longueur="+str(len(ch))+': ') def recherche_existence(t,n,ch): existence=False i=-1 while(existence==False) and i<len(ch)-1: i=i+1 ch1='' for j in range(n): ch2=t[j] ch1=ch1+ch2[i] #print(ch1) if ch==ch1 : existence=True return existence ''' while ((existence==True) and (i<n-1)): existence=False ch1=t[0] j=0 while ((ch[j]==ch1[i]) and (j<n-1)): j=j+1 ch1=t[j] if (ch[j]==ch1[i]): existence=True i=i+1 ''' #programme principal ch=saisie_ch() n=saisie_taille() print('remplissage du tableau t') remplir(t,n,ch) if recherche_existence(t,n,ch) : print(ch+' est une chaine existante dans T ') else: print(ch+' est une chaine inexistante dans T ') |
Exécution du programme
Solution en Python et Designer QT
Pour remplir un tableau des chaînes à partir d'une chaîne de caractères en Python, vous pouvez suivre les étapes suivantes :
1- Découper la chaîne de caractères en sous-chaînes contenant les mots.
3- Ajouter chaque sous-chaîne au tableau.
Pour créer une application en Python pour rechercher l'existence d'un mot donné dans le tableau T.
1- Créer l'interface graphique avec Qt Designer
a- Ouvrez Qt Designer et créez un nouveau fichier de type Main Window.
b- Ajoutez ces widgets:
QLineEdit nommé 'ch' pour entrer le mot.
QLineEdit nommé 'tab_ch' pour entrer les chaines à mettre dans le tableau.
QPushButton nommé 'remplir_bt' pour exécuter le module createTab afin de remplir le tableau à partir de la chaine 'ch'.
QPushButton nommé 'bt_recherche' pour exécuter le module recherche_existence.
QLabel nommé 'msg' pour afficher les messages d'erreur
QLabel nommé 'tab_label' pour afficher les éléments du tableau T.
QLabel nommé 'resultat' pour afficher les mots zigzag.
Enregistrez le fichier avec l'extension .ui, par exemple tabtab-2.ui.
2- Créer le script Python pour l'application
|
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 |
from PyQt5.uic import loadUi from PyQt5 import QtCore, QtGui from PyQt5.QtWidgets import * from PyQt5 import QtCore, QtGui, QtWidgets from numpy import array t=array([str]*100) app = QApplication([]) windows = loadUi ("tabtab-2.ui") # Fonction qui supprime des espaces de la chaine des carcatères def supprimer_espaces (ch) : while(ch[0]==' '): # elimnier tous les espaces au début de la chaine ch=ch[1:len(ch)] while(ch[len(ch)-1]==' '): # elimnier tous les espaces a la fin de la chaine ch=ch[0:len(ch)-1] while (ch.find(' ')>0): ch=ch.replace(" ", " ") # remplacer les doubles espaces apar un seul espace return ch def verif_majus(ch): i=0 while ('A'<=ch[i]<='Z') and (i<len(ch)-1): i=i+1 if ('A'<=ch[i]<='Z'): return True else: return False # Procedure qui remplit un tableau par des entiers a partir d'une chaine des caractère def createTab(): windows.msg.clear() ch = windows.ch.text() tab_ch = windows.tab_ch.text() global n # pour la taille di tableau if (ch=="") or (tab_ch=="") or (verif_majus(ch)==False): windows.msg.setText("Veuillez remplir les deux chaînes en majuscules") else: windows.msg.clear() # effacer le message d erreur tab_ch= supprimer_espaces(tab_ch) i=0 j=0 ch1='' test_long=True # parcourir les caracteres de la chaine while((i<len(tab_ch)) and (test_long) and (('A'<=tab_ch[i]<='Z') or (tab_ch[i]==' '))): if ('A'<=tab_ch[i]<='Z'): ch1=ch1+tab_ch[i] if ((tab_ch[i]==' ') or (i==len(tab_ch)-1)) : t[j]=ch1 ch1='' test_long=(len(t[j])==len(ch)) j=j+1 i=i+1 if (i<len(tab_ch)) : windows.msg.setText("La chaine doit contenir des mots en majuscules et de longueur="+str(len(ch))) else : if 5<=j<=10: # test du taille du tableau n=j tab='' for k in range (j) : tab=tab+ 't['+str(k)+']= '+ t[k]+ '\n' #afficher les elements du tableau windows.tab_label.setText(tab) else: windows.msg.setText("Le nbr des elements doit etre entre 5 et 10") def recherche_existence(): ch = windows.ch.text() existence=False i=-1 while(existence==False) and i<len(ch)-1: i=i+1 ch1='' for j in range(n): ch2=t[j] ch1=ch1+ch2[i] print(ch1) if ch==ch1 : existence=True if existence : windows.msg.setText(ch+' est une chaine existante dans T') else: windows.msg.setText(ch+' est une chaine inexistante dans T') windows.remplir_bt.clicked.connect ( createTab ) windows.bt_recherche.clicked.connect ( recherche_existence ) windows.show() app.exec_() |
Exécution du programme
Vous pouvez voir aussi :
1) des exercices sur les chaînes des caractères
2) des exercices sur les tableaux
3) des sujets Bac pratique
4) des sujets Bac théorique
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
