INFO PYTHON.2 FEUILLE D'EX n° 8 BTS SIO MARS 2012
COURS:
THEME:
• Tri à bulle sur une liste. On compare deux à deux les termes de la liste en changeant
seulement l'ordre de deux termes si l'ordre de leurs indices ne correspond pas à l'ordre de
leurs valeurs. On fait ainsi remonter les termes de valeurs plus grandes comme des bulles de
champagne dans un verre.
• Comparaison xrange( un entier....) et range( un entier....)
( Cela revient au même pratiquement . Quand l'entier est très grand on prend xrange.
Par exemple: for i in xrange(500) veut dire de:
<< pour i entier de 0 à 499 >>
On peut ausi dire : for i in range(0,500) )
• Soit a et b deux entiers naturels avec a ≤ b .
• for i in xrange ( entier a, entier b ) ( donne les entiers de a à l'entier b-1 )
• for i in reversed(xrange (entier b)) ( donne le compte à rebours à partir de l'entier b-1 jusqu'à 0)
• for i in reversed(xrange (entier a,entier b)) ( donne le compte à rebours à partir de l'entier b-1 jusqu'à a)
len( liste) ( donne le nombre de termes de la liste )
• Utilisation diecte de sort()
•• Soit L une liste de valeurs numériques.
L.sort()
print L
Cela va afficher la liste L avec ses termes numériques dans l'ordre croissant.
•• Remarque: Quand L est une liste de chaînes de caractères comme L=["bonjour","beau","alors","hier","fleur"]
L.sort() permet d'ordonner les chaînes dans l'ordre alphabétique.
Cela donnerait ici : ['alors', 'beau', 'bonjour', 'fleur', 'hier']
Cela permet si l'on a une liste de noms de les mettre dans l'ordre alphabétique.
Par exemple pour une feuille d'appel:
def feuilleappel():
L=["Maurice","André","Jamine","Barnabé","Aimé"]
L.sort()
for line in L:
print line
On obtiendra:
>>> feuilleappel()
Aimé
André
Barnabé
Jamine
Maurice
>>>
------------------------------------------------------------------------------------------------------------------
EXERCICE 1
Que donne le petit script suivant ?
def rez():
for i in xrange(5):
print i
------------------------------------------------------------------------------------------------------------------
Réponse :
0
1
2
3
4
La fonction xrange() est utilisée exclusivement pour les boucles for.
range() on renvoie une liste d'entiers.
xrange() renvoie un objet xrange qui génère les entiers.
En pratique pour un petit nombre d'entiers les deux font la même chose.
xrange() est plus rapide et plus léger en mémoire que range().
--------------------------------------------------------------------------------------------------------------
EXERCICE 2
Que donne le petit script suivant ?
def reau():
for i in xrange(5):
print " julien"
------------------------------------------------------------------------------------------------------------------
Réponse : On obtient:
julien
julien
julien
julien
julien
Pour chaque entier i de 0 à 4 cela écrit julien.
-----------------------------------------------------------------------------------------------------------
EXERCICE 3
Que donne le script suivant ?
def rat():
for i in xrange(2,5):
print i
------------------------------------------------------------------------------------------------------
Réponse : Cela donne les entiers de 2 et 4
2
3
4
-----------------------------------------------------------------------------------------------------------
EXERCICE 4
Que donne le script suivant ?
def reuter():
for j in reversed(xrange(2,5)):
print j
---------------------------------------------------------------------------------------------------------
Réponse:
Cela donne le compte à rebours de 4 à 2:
4
3
2
reversed fait que c'est décroissant de 5-1 à 2.
-----------------------------------------------------------------------------------------------
EXERCICE 5
Que donne le script suivant ?
def reuter():
for j in reversed(xrange(5)):
print j
----------------------------------------------------------
Réponse:
On obtient le compte à rebours de 5-1 à 0:
4
3
2
1
0
-----------------------------------------------------------------------------------------------
EXERCICE 6 Tri à bulle
Soit la liste lis = [ 7, 5, 8, 3, 6] de 5 termes.
Ecrire un script qui permet de ranger ses termes dans l'ordre croissant.
--------------------------------------------------------------------------------------------------------------
Réponse:
Voici un script qui convient:
def Tri_Bulle():
lis=[7,5,8,6,3]
print lis
L=len(lis)
print "le nombre de valeurs de la liste lis est: " ,L
for i in xrange(len(lis)):
# i varie entre 0 et L-1=4
for j in reversed(xrange(i,len(lis))):
# j varie de L-1=4 à i en décroissant
if lis[j]<lis[j-1]:
t=lis[j]
lis[j]=lis[j-1]
lis[j-1]=t
print lis
Ce script donne:
>>> Tri_Bulle()
[7, 5, 8, 6, 3]
le nombre de valeurs de la liste lis est: 5
[7, 5, 8, 3, 6]
[7, 5, 3, 8, 6]
[7, 3, 5, 8, 6]
[3, 7, 5, 8, 6]
[6, 7, 5, 8, 3]
[6, 7, 5, 3, 8]
[6, 7, 3, 5, 8]
[6, 3, 7, 5, 8]
[3, 6, 7, 5, 8]
[3, 6, 5, 7, 8]
[3, 5, 6, 7, 8]
>>>
En déplaçant le print vers la gauche au dessous du premier for
on peut directement avoir la dernière ligne.
-------------------------------------------------------------------------------------------------------
EXERCICE 7
1. Reprendre l'exercice précédent en demandant la liste de valeurs
à classer dans l'ordre croissant.
2. Reprendre le même objectif final mais avec liste.sort().
--------------------------------------------------------------------------------------------------------
Réponse: Voici une réponse possible:
def tiul():
lis=input("donner une liste de valeurs notée lis " )
print lis
for i in xrange(len(lis)):
for j in reversed(xrange(i,len(lis))):
if lis[j]<lis[j-1]:
t=lis[j]
lis[j]=lis[j-1]
lis[j-1]=t
print lis
Par exemple en le faisant tourner on a avec la liste [ 1,7,5]:
>>> tiul()
donner une liste de valeurs notée lis [1,7,5]
[1, 7, 5]
[1, 5, 7]
[7, 5, 1]
[7, 1, 5]
[1, 7, 5]
[1, 5, 7]
>>>
AUTRE SCRIPT POSSIBLE SANS COMPTE A REBOURS POUR j
from random import*
def tribulle():
L=input("Donner une liste de valeurs: L = ")
print " Nous voulons ordonner la liste dans l'ordre croissant "
for i in range(len(L)):
for j in range(len(L)):
while i<j and L[i]>L[j]:
L[i],L[j]=L[j],L[i]
print L
# Tant que les termes d'indices i et j ne sont pas
# rangés dans le même ordre que i et j on les permute
Cela donne par exemple:
-----------------------------------------------------------------
>>> tribulle()
Donner une liste de valeurs: L = [6,4,9,2]
Nous voulons ordonner la liste dans l'ordre croissant
[4, 6, 9, 2]
[2, 6, 9, 4]
[2, 4, 9, 6]
[2, 4, 6, 9]
>>>
Remarque:
On peut déplacer print L à la verticale de for i in range(len(L):
pour n'avoir que la dernière ligne affichée.
Remarque:
Dans le script précédent on a fait varier i et j entre 0 et len(L)-1 .
C'est plus que nécessaire pour j.
On peut se contenter de faire seulement varier j entre i et len(L)-1
c-à-d " mathématiquement" on considère en fait i ≤ j < len( L)
Alors quand j = i on ne demande pas de permutation car on n'a pas L[i]>L[j].
Donc dans le while on supprime la condition i < j .
On voit juste à l'affichage les permutations nécessaires pour le tri.
On peut écrire:
from random import*
def tribull():
L=input("Donner une liste de valeurs: L = ")
print " Nous voulons ordonner la liste dans l'ordre croissant "
for i in range(len(L)):
for j in range(i,len(L)):
while L[i]>L[j]:
L[i],L[j]=L[j],L[i]
print L
On obtient par exemple:
>>> tribull()
Donner une liste de valeurs: L = [9,5,6,2]
Nous voulons ordonner la liste dans l'ordre croissant
[5, 9, 6, 2] 5 ↔ 9
[2, 9, 6, 5] 2 ↔ 5
[2, 6, 9, 5] 6 ↔ 9
[2, 5, 9, 6] 5 ↔ 6
[2, 5, 6, 9] 6 ↔ 9
>>>
Il a fallu 5 permutations pour ordonner la liste L.
Question 2
Voici un script qui convient:
def essai():
L=input("Donner une liste ")
print " L = " ,L
L.sort()
print " Cela donne: L = ",L
On obtient par exemple:
>>> essai()
Donner une liste [1,9,4,7,2]
L = [1, 9, 4, 7, 2]
Cela donne L = [1, 2, 4, 7, 9]
>>>
-----------------------------------------------------------------------------------------------------