Trier un tableau des entiers – Bac Pratique 2014 [ Algorithme + Python ]
Sujet bac informatique pratique 2014 (Bac scientifique)
Soit T un tableau contenant des n entiers distincts avec n appartient à l’intervalle [1,99].
Pour trier dans l’ordre croissant les éléments du tableau T, on propose la méthode suivante :
1- Placer chaque élément T[i] dans la case d’indice T[i] d’un tableau intermédiaire T1, sachant que les éléments du tableau T1 sont initialisés à zéro.
2- Placer dans l’ordre tous les entiers différents de zéro du tableau TI, dans le tableau T.
Exemple :
Pour T=
| 6 | 2 | 11 | 8 | 4 | 5 |
Après application du principe de tri décrit précédemment, on pbtient le tableau intermédiare TI ci-dessous :
T1
| 0 | 2 | 0 | 4 | 5 | 6 | 0 | 8 | 0 | 0 | 11 |
On aura le tableau T trié suivant :
Pour T=
| 2 | 4 | 5 | 6 | 8 | 11 |
Travail demandé :
Ecrire un programme Python qui permet de :
1- remplir un tableau T par n entiers distincts strictement positifs et ne dépasse pas 99 avec 5≤n≤30.
2- trier le tableau T en utilisant la méthode décrite ci-dessus. -
3- afficher le tableau T après tri.
Solution Algorithmique
Voici le principe de l'algorithme qui permet de réaliser les trois étapes demandées :
1. Remplir un tableau T par n entiers saisis dans un ordre croissant :
Initialisation : Créer un tableau T de taille n.
Saisie des éléments :
a) Saisir le premier élément du tableau t[0].
b) Pour chaque élément i de 1 à n-1 : comparer t[i] à T[i-1] :
- Si t[i] est supérieur ou égal à T[i-1], l'affecter à T[i].
- Sinon, redemander la saisie de l'entier jusqu'à ce que l'ordre croissant soit respecté.
2. Tri du tableau T avec la méthode décrite
Principe
- Utiliser un tableau intermédiaire T1 de taille 100 (indices de 0 à 99) initialisé à zéro.
- Placer chaque élément de T dans la case d’indice correspondant dans T1.
- Parcourir T1 et copier tous les éléments non nuls dans T dans l'ordre croissant.
Étapes
a- Pour chaque élément T[i] de T, placer T[i] dans T1 à l'indice T[i].
b- Parcourir T1 de l'indice 1 à 99. Chaque fois que T1[j] est non nul, placer T1[j] dans T.
c-T est maintenant trié dans l'ordre croissant.
3. Affichage du tableau T après tri
Une fois que le tableau T est trié, il suffit de l'afficher.
Dans cet algorithme, On va utiliser 3 fonctions et 3 procédures :
Algorithme du programme principal
|
1 2 3 4 5 6 7 8 9 10 11 |
Algorithme trier_tableau Debut n<-saisie() Ecrire('remplissage du tableau t') remplir(t,n) trier(t,n) Ecrire('tableau t1') afficher_tableau(t1,m+1) Ecrire('tableau t trie') afficher_tableau(t,n) Fin |
Déclaration des objets
Objet | Type / Nature |
t | tableau de 100 entiers |
t1 | tableau de 100 entiers |
n | entier |
m | entier |
La fonction saisie
Cette fonction retourne un entier n entre 1 et 99 saisi par l'utilisateur.
|
1 2 3 4 5 6 7 8 9 10 |
foncttion saisie():entier Début Ecrire('donner un entier entre 1 et 99') lire (n) Tant que n<1 ou n>99 faire Ecrire('donner un entier entre 1 et 99') lire (n) Fin tant que retourner n Fin |
Déclaration des objets
Objet | Type / Nature |
n | 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°0: ") lire(t[0]) Pour i de 1 à n-1 faire Ecrire("donner elt N°",i,":") lire(t[i]) Tant que test_distinct(t,i)=Faux faire Ecrire("donner elt N°",i,":") lire(t[i]) Fin tant que Fin pour Fin |
Déclaration des objets
Objet | Type / Nature |
i | entier |
La fonction max
Cette fonction recherche le plus grand élément dans le tableau.
|
1 2 3 4 5 6 7 8 9 10 |
Fonction max(t:Tab,n:entier):entier Début x<-t[0] Pour i de 1 à n-1 faire Si x<t[i] alors x<-t[i] Fin si Fin pour retourner x Fin |
Déclaration des objets
Objet | Type / Nature |
i | entier |
x | entier |
La procédure trier
Cette procédure trie les éléments du tableau t d'une façon croissante.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
Procédure trier(@t:Tab,n:entier) Début Pour i de 0 à n-1 faire t1[t[i]]<-t[i] Fin pour m<-max(t,n); j<-0 Pour i de 0 à m faire Si (t1[i]!=0) alors t[j]<-t1[i] j<-j+1 Fin si Fin pour Fin |
Déclaration des objets
Objet | Type / Nature |
i | entier |
j | entier |
m | entier |
La procédure afficher_tableau
Cette procédure affiche les éléments du tableau.
|
1 2 3 4 5 6 7 |
Procédure afficher_tableau(t:Tab,n:entier) Début Pour i de 0 à n-1 faire Ecrire('t[',i,']=') Ecrire(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 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
from numpy import array t=array([int()]*99) t1=array([int()]*99) def saisie_taille() : n=int(input("donner un entier entre 1 et 99 ")) while(1>n) or (n>99) : n=int(input("donner un entier entre 1 et 99 ")) return n def test_distinct(t,i): j=i-1 while (t[j]!=t[i]) and (j>0): j=j-1 return t[j]!=t[i] def remplir(t,n): t[0]=int(input("donner elt N°"+str(0)+":")) for i in range (1,n) : t[i]=int(input("donner elt N°"+str(i)+":")) while (test_distinct(t,i))==False: t[i]=int(input("donner elt N°"+str(i)+":")) def afficher_tableau(t,n): for i in range (n) : print('t['+str(i)+']= '+ str(t[i])) def max(t,n): x=t[0]; for i in range(1,n): if x<t[i] : x=t[i] return x def trier(t,n): global m for i in range(n) : t1[t[i]]=t[i]; m=max(t,n); j=0 for i in range(m+1) : if (t1[i]!=0) : t[j]=t1[i] j=j+1 # programme principal n=saisie_taille() print('remplissage du tableau t') remplir(t,n) trier(t,n) print('tableau t1') afficher_tableau(t1,m+1) print('tableau t trie') afficher_tableau(t,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, vous pouvez suivre les étapes suivantes :
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 les éléments du tableau dans l'ordre croissant .
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 à partir de la chaine 'ch'.
QPushButton nommé 'bt_trier' pour exécuter le module tri_Tab afin de trier le tableau T.
QLabel nommé 'msg' pour afficher un message d'erreur si ch est vide ou contient des valeurs non numériques ou les éléments du tableau ne sont pas dans l'ordre croissant.
QLabel nommé 'tab_label' pour afficher les éléments du tableau T.
QLabel nommé 'tab_label1' pour afficher les éléments du tableau T1.
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 101 102 103 104 105 |
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([int()]*99) t1=array([int()]*99) 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 test_distinct(t,i): j=i-1 while (t[j]!=t[i]) and (j>0): j=j-1 return t[j]!=t[i] # Procedure qui remplit un tableau par des entiers a partir d'une chaine des caractère def createTab(): ch = windows.ch.text() global n # pour la taille di tableau 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]==' ')or (ch[i]=='-'))): if ('0'<=ch[i]<='9') or (ch[i]=='-'): 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 : if test_distinct(t,j-1): n=j 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 non distinctes") def max(t,n): x=t[0]; for i in range(1,n): if x<t[i] : x=t[i] return x def tri_Tab(): for i in range(n) : t1[i]=0 for i in range(n) : t1[t[i]]=t[i]; m=max(t,n); tab='' for k in range (m+1) : tab=tab+ 't1['+str(k)+']= '+ str(t1[k])+ '\n' windows.tab1_label.setText(tab) j=0 for i in range(m+1) : if (t1[i]!=0) : t[j]=t1[i] j=j+1 tab='' for k in range (n) : tab=tab+ 't['+str(k)+']= '+ str(t[k])+ '\n' windows.tab_label.setText(tab) windows.remplir_bt.clicked.connect ( createTab ) windows.bt_trier.clicked.connect ( tri_Tab ) windows.show() app.exec_() |
Exécution du programme
1) Remplissage du tableau:
2) Affichage du tableau trié :
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
