Python : Recherche dans un tableau. Corrigé Exercice A

Python : Recherche dans un tableau. Corrigé
Exercice A. Recherche d’un élément dans un tableau non trié
1) Le principe de la recherche d’un élément dans un tableau non trié est simple : un parcours séquentiel jusqu’à
trouver cet élément ou aboutir à la …n de la liste.
def mem(a,L):
for x in L :
if x == a :
return True
return False
Remarque : Cette fonction est en fait déjà implémentée : si x est un objet python et s un objet iterable (une séquence,
c’est à dire un objet de type list, tuple, range, str, l’expression (x in s) vaut True ssi x appartient à s:
2) def indice(a,L) :
r = 0
for x in liste :
if x == a :
return r
r += 1
return r
3) from numpy.random import randint
def moyenne(N):
s = 0 ;
for k in range(1000):
a = randint(N) ; L = [randint(N) for i in range(10000)]
s = s + indice(a, )
print("moyenne des comparaisons effectuées :", s/1000)
1
b) Pour tout 0
k < n, la probabilité que r = k est égal à
N
1 n
n’appartienne pas à la liste vaut 1
:
N
En fait, il vaut mieux utiliser les P (r > k) : En e¤et, on a 8k
n
1
1
N
k
1, P (r > k) =
, et la probabilité que l’élément
1
1
N
k+1
P
Pn 1
La valeur moyenne de r est E(r) = nk=0 k P (r = k) = k=0
P (r > k), car P (r = k) = P (r > k
P
P
P
En e¤et, on a E(r) = nk=0 k P (r = k) = nk=0 k (P (r > k 1) P (r > k))) = nk=01 P (r > k)
!
Pn
1 Pn 1
1 k
1
1 k+1
= 1
1
= (N 1) 1
1
Donc E(r) = k=0 1
k=0 1
N
N
N
N
Ainsi, E(r) tend vers (N
1) lorsque n tend vers l’in…ni.
Remarque : Lorsque n = N , E(i)
(1
e
1 )N
lorsque N tend vers l’in…ni.
Exercice B. Recherche dans un tableau trié
et P (r > n) = 0:
1)
P (r > k):
nP (r > n):
n
:
1) Pour chercher x dans la liste triée par ordre croissant [a0 ; :::; an
x et ap , où p =
n
2
1 ],
on utilise le principe dichotomique : on compare
.
–si x < ap alors x, s’il se trouve dans la liste [a0 ; :::; an
1]
appartient nécessairement à la liste [a0 ; :::; ap
1]
–si x = ap , la recherche est terminée ;
–si x > ap alors x, s’il se trouve dans la liste, appartient nécessairement à la liste [ap+1 ; :::; an
1 ]:
Pour mettre ce principe en pratique, on le généralise à la recherche de x dans la liste extraite [ai ; :::; aj
1]
: si i
j
la liste en question est vide et x ne s’y trouve donc pas ; si i < j, la liste n’est pas vide et l’élément médian a
j k
et la comparaison entre x et ak ramène la recherche à l’un des deux tableaux [ai ; :::; ak 1 ] ou
pour indice k = i+j
2
[ak+1 ; :::; aj
1 ]:
def mem(a,L):
i , j = 0 , len(L)
while i < j :
k = (i + j) // 2
if L[k] == a :
return True
elif L[k] > a :
else :
j = k
i = k + 1
return False
Remarque : Le nombre de comparaisons est en moyenne de l’ordre de log(n):
2) Si on cherche la première occurrence de a dans le tableau, il faut poursuivre la recherche dans la partie gauche
même si on a trouvé a.
def indice(a,L):
i, j = 0, len(L) ; r = len(L)
while i < j :
k = (i + j) // 2
if L[k] >= a :
j = k
if L[k] == a :
else :
r = k
i = k + 1
return p
À l’issue de la recherche dichotomique, deux situations peuvent se rencontrer :
–si a est présent dans le tableau, la variable r contient l’indice de la première occurrence et c’est ce résultat qui
est retourné par la fonction ;
–si a n’est pas présent dans le tableau, la variable r vaut sa valeur initiale len(L).
Exercice C. Recherche d’un mot dans un texte par la méthode naïve
1) def recherche(mot,texte) :
if len(mot) > len(texte) :
return False
for k in range(len(texte)-len(mot)+1):
if texte[k:k+len(mot)] == mot :
return True
return False
Si on ne s’autorise que des comparaisons entre caractères, il est préférable de commencer par écrire une fonction
déterminant si un mot est pré…xe d’un facteur d’un autre :
def suffixe(mot, texte, d):
for k in range(len(mot)):
if mot[k] != texte[d+k]:
return False
return True
Et on remplace texte[k:k+len(mot)] == mot par if suffixe(mot, texte, d).
2) from numpy.random import randint
def alea(n) :
alphabet = "abcdefghijklmnopqrstuvwxyz" ; s = ""
for i in range(n) :
s = s + alphabet[randint(26)]
return s
Remarque : Variante pour l’avant-dernière ligne : s = [ alphabet[randint(26)] for i in range(n)].
3) def moyenne(n) :
compteur = 0
for k in range(n):
if recherche("llg", alea(1000)):
return (compteur/1000)
compteur = compteur + 1

Download Report