Bac scientifique théorique 2010 [ Algorithme + Python ]
Travail demandé
On se propose d’écrire un programme Python « Tri » qui permet de remplir un tableau T par n entiers distincts puis de former et d’afficher un autre Res qui va contenir les n entiers du tableau T classés en ordre croissant selon le principe suivant :
Pour chaque élément du tableau T :
1) Déterminer le nombre Nbr d’éléments de T qui lui sont inférieurs ou égaux.
2) Placer cet élément dans la position Nbr du tableau Res.
Exemple : T
| 3 | 14 | 0 | 9 | 17 | 5 | 8 | 4 |
L’entier T[1]=3 a 2 éléments qui lui sont inférieurs ou égaux (3 et 0), il sera placé dans la position 2 du tableau Res:
| 3 |
L’entier T[2]=14 a 7 éléments qui lui sont inférieurs ou égaux (3,14,0,9,5,8 et 4), il sera placé dans la position 7 du tableau Res:
| 3 | 14 |
Ainsi de suite pour les autres éléments.
Le tableau Res aura les éléments placés dans un ordre croissant comme suit :
| 0 | 3 | 4 | 5 | 8 | 9 | 14 | 17 |
Solution Algorithmique
Cet algorithme vise à trier un tableau T contenant n entiers distincts en ordre croissant et à placer les éléments triés dans un autre tableau Res. Voici le principe de l'algorithme :
1- Initialisation :
On a un tableau T de taille n.
On crée un tableau Res de la même taille n pour stocker les résultats triés.
2- Remplissage du tableau T par n entiers distincts :
a- Saisir le premier élément du tableau (lire t[0])
a- Initialiser un index i à 1, qui suivra le nombre d'éléments actuellement dans T.
b- Saisir un entier (lire t[i]).
c- Vérifier si cet entier n'est pas déjà présent dans T. Pour ce faire, parcourir le tableau T jusqu'à l'index i-1 et comparer chaque élément à t[i].
d- Si t[i] est trouvé dans T, on retourne à la phase (b)
Sinon on incrémente l'indice i et on retourne à la phase (b) .
3- Remplissage du tableau Res:
Pour chaque élément T[i] du tableau T :
a- On initialise un compteur position à 0.
b- On parcourt le tableau T et pour chaque élément T[j], si T[j]≤T[i], on incrémente le compteur position.
c- On place l'élément T[i] à l'index position dans le tableau Res.
4- Affichage du tableau Res:
Après avoir parcouru tous les éléments de T, le tableau Res contiendra les éléments de T triés en ordre croissant.
Dans cet algorithme, On va utiliser deux fonctions et deux procédures:
|
1 2 3 4 5 6 7 8 9 |
Algorithme trie Debut n<-saisie() Ecrire('remplissage du tableau t') remplir(t,n) tri(t,res,n) Ecrire('le tableau trie:') afficher_tableau(res,n) Fin |
Déclaration des objets
Objet | Type / Nature |
i | entier |
t | tableau de 30 entiers |
res | tableau de 30 entiers |
La fonction saisie
Cette fonction retourne un entier n entre 1 et 30 saisi par l'utilisateur.
|
1 2 3 4 5 6 7 8 9 10 |
foncttion saisie() Début Ecrire('donner un entier entre 1 et 30') lire (n) Tant que n<1 ou n>30 faire Ecrire('donner un entier entre 1 et 30') lire (n) Fin tant que retourner n Fin |
Déclaration des objets
Objet | Type / Nature |
n | entier |
La fonction verif_distinct
Cette fonction vérifie si un entier saisi par l'utilisateur se trouve dans le tableau.
|
1 2 3 4 5 6 7 8 |
foncttion verif_distinct(t,i) Début j<-0 Tant que t[j]!=t[i] et j<i-1 faire j<-j+1 Fin Tant que retourner t[j]!=t[i] Fin |
Déclaration des objets
Objet | Type / Nature |
i | entier |
j | entier |
La procédure remplir
Cette procédure remplit le tableau t de n entiers distincts.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
Procédure remplir(@t:Tab,n:entier) Début Ecrire('donner elt N°',i,':') lire(t[i]) Pour i de 1 à n-1 faire Ecrire('donner elt N°',i,':') lire(t[i]) Tant que verif_distinct(t,i)=faux alors Ecrire('donner elt N°',i,':') lire(t[i]) Fin tant que Fin pour Fin |
Déclaration des objets
Objet | Type / Nature |
i | entier |
La procédure Tri
Cette procédure va parcourir le tableau T en remplissant le tableau Res par des entiers d'une façon croissante.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
Procédure tri(t,@res,n) Début Pour i de 0 à n-1 faire position<-0 Pour j de 0 à n-1 faire Si (t[i]>t[j]) alors position<-position+1 res[position]<-t[i] Fin si Fin pour Fin Pour Fin |
Déclaration des objets
Objet | Type / Nature |
i | entier |
j | entier |
position | entier |
La procédure afficher_tableau
Cette procédure va parcourir un tableau en affichant ses éléments.
|
1 2 3 4 5 6 |
Procédure afficher_tableau(t,n) Début Pour i de 0 à n-1 faire Ecrire ('t[',i,']= ', t[i]) Fin Pour Fin |
Déclaration des objets
Objet | Type / Nature |
i | 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 |
from numpy import array t=array([int()]*30) # remplir ce tableau par des entiers distincts res=array([int()]*30) # on va stocker les valeurs triees dans ce tableau def saisie_taille() : n=int(input("donner un entier entre 1 et 30 ")) while(1>n) and(n>30) : n=int(input("donner un entier entre 1 et 30 ")) return n def verif_distinct(t,i): j=0 while t[j]!=t[i] and j<i-1 : j=j+1 return t[j]!=t[i] def remplir(t,n): # remplir ce tableau par des entiers distincts t[0]=int(input("donner elt N°0: ")) for i in range (1,n) : t[i]=int(input("donner elt N°"+str(i)+" distinct: ")) while verif_distinct(t,i)==False: t[i]=int(input("donner elt N°"+str(i)+" distinct: ")) def tri(t,res,n): for i in range(n): position=0; for j in range(n): if (t[i]>t[j]): position=position+1 res[position]=t[i] def afficher_tableau(t,n): for i in range (n) : print('t['+str(i)+']= '+ str(t[i])) #programme principal n=saisie_taille() print('remplissage du tableau t') remplir(t,n) tri(t,res,n) print('tableau trie') afficher_tableau(res,n) |
Exécution du programme
Solution en Python et Designer QT
Pour remplir un tableau d'entiers à partir d'une chaîne de caractères en Python il faut:
1- Découper la chaîne de caractères en sous-chaînes contenant les entiers.
2- Convertir chaque sous-chaîne en entier.
3- Ajouter chaque entier au tableau.
Pour créer une application en Python pour trier un tableau T contenant n entiers distincts en ordre croissant et à placer les éléments triés dans un autre tableau Res , vous pouvez suivre les étapes suivantes :
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 des entiers .
QPushButton nommé 'remplir_bt' pour exécuter le module createTab afin de remplir le tableau t à partir de la chaine 'ch'.
QPushButton nommé 'trier_bt' pour exécuter le module TrierTab afin de remplir le tableau Res par des entiers du tableau T d'une façon croissante.
QLabel nommé 'msg' pour afficher un message d'erreur si ch est vide ou contient des valeurs non numériques .
QLabel nommé 'tab_label' pour afficher les éléments du tableau T.
QLabel nommé 'res_abel' pour afficher les éléments du tableau Res.
Enregistrez le fichier avec l'extension .ui, par exemple tabtab-2.ui.
2- Créer le script Python pour l'application
Voici un exemple de script Python qui utilise l'interface graphique générée par Qt Designer.
|
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 |
from PyQt5.uic import loadUi from PyQt5 import QtCore, QtGui from PyQt5.QtWidgets import * from PyQt5 import QtCore, QtGui, QtWidgets from numpy import array import math t=array([int()]*30) # le tableau t sera remplit par des entiers distincts res=array([int()]*30) # le tableau res va contenir des entiers triés 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_distinct(t,n): i=1 j=0 while t[j]!=t[i] and i <n-1 : j=0 while t[j]!=t[i] and j<i-1 : j=j+1 if t[j]!=t[i] : i=i+1 return t[j]!=t[i] def createTab(): windows.tab_label.clear() windows.res_label.clear() global n # pour la taille de deux tableaux ch = windows.ch.text() if ch=="": windows.msg.setText("Veuillez remplir la chaîne") else: windows.msg.clear() # effacer le message d erreur ch= supprimer_espaces(ch) i=0 j=0 ch1='' # parcourir les caracteres de la chaine while((i<len(ch)) and (('0'<=ch[i]<='9') or (ch[i]==' '))): if ('0'<=ch[i]<='9') : ch1=ch1+ch[i] if ((ch[i]==' ') or (i==len(ch)-1)) : t[j]=int(ch1) ch1='' j=j+1 i=i+1 if (i<len(ch)) : # si la chaine contient des valeurs non numeriques windows.msg.setText("la chaîne contient des valeurs non numériques") else : n=j print(verif_distinct(t,n)) if verif_distinct(t,n) : tab='' for k in range (j) : tab=tab+ 't['+str(k)+']= '+ str(t[k])+ '\n' #afficher les elements du tableau windows.tab_label.setText(tab) else : windows.msg.setText("la chaîne contient des valeurs numériques non distinctes") def TrierTab(): for i in range(n): position=0; for j in range(n): if (t[i]>t[j]): position=position+1 res[position]=t[i]; tab='' for k in range (n) : tab=tab+ 'res['+str(k)+']= '+ str(res[k])+ '\n' #afficher les elements du tableau windows.res_label.setText(tab) windows.remplir_bt.clicked.connect ( createTab ) windows.trier_bt.clicked.connect ( TrierTab ) windows.show() app.exec_() |
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
