extrait 1 à copier pour l'énoncé de décembre 2013
def deux_recherches(element, liste_impaire, liste_paire) :
# ....
return position_dans_liste_impaire, position_dans_liste_paire
vérifier que tous les éléments de la liste sont bien retrouvés
l = [ 0, 2, 4, 6, 8, 100, 1000 ]
for i in l :
print (i,recherche_dichotomique(i, l))
, énoncé 2014
#coding: latin-1
######### énoncé 1, exercice 1, recherche dichotomique
## question 1
def recherche_dichotomique( element, liste_triee ):
"""
premier code: http://www.xavierdupre.fr/blog/2013-12-01_nojs.html
"""
a = 0
b = len(liste_triee)-1
m = (a+b)//2
while a < b :
if liste_triee[m] == element :
return m
elif liste_triee[m] > element :
b = m-1
else :
a = m+1
m = (a+b)//2
return a
l = [ 0, 2, 4, 6, 8, 100, 1000 ]
print (recherche_dichotomique(100, l)) # affiche 5
## question 2
def deux_recherches(element,liste_impair,liste_pair) :
if element % 2 == 0 :
return recherche_dichotomique(element, liste_pair), -1
else :
return -1, recherche_dichotomique(element, liste_impair)
lp = [ 0, 2, 4, 6, 8, 100, 1000 ]
li = [ 1, 3, 5 ]
print (deux_recherches(100, li, lp)) # affiche (5, -1)
## question 3
"""
liste coupée liste non coupée (2n)
recherche simple 1 + n 2n
recherche dichotomique 1 + ln n ln(2n) = 1 + ln(n)
coût équivalent
"""
## question 4
def recherche_dichotomique( element, liste_triee ):
a = 0
b = len(liste_triee)-1
m = (a+b)//2
while a < b :
if liste_triee[m] == element :
return m
elif liste_triee[m] > element :
b = m-1
else :
a = m+1
m = (a+b)//2
if liste_triee[a] != element : return -1 # ligne ajoutée
else : return m # ligne ajoutée
l = [ 0, 2, 4, 6, 8, 100, 1000 ]
for i in l :
print (i,recherche_dichotomique(i, l))
# vérifier qu'on retrouve tous les éléments existant
print (recherche_dichotomique(1, l)) # affiche -1
## question 5
def deux_recherches(element,liste_impair,liste_pair) :
i = recherche_dichotomique(element, liste_impair)
if i == -1 : return recherche_dichotomique(element, liste_pair)
else : return i
##question 6
"""
Les logarithmes sont en base 2.
coût fonction question 2 : 1001 ( 1 + ln(n) ) = C1
coût fonction question 5 : 1000 ln(n) + 2 ln(n) = C2
C2 - C1 = ln(n) - 1001 > 0
La fonction 5 est plus rapide dans ce cas.
"""
cas où la recherche n'est plus dichotomique
def recherche_dichotomique( element, liste_triee ):
if element not in list_triee : return -1 # ligne A
a = 0
b = len(liste_triee)-1
m = (a+b)//2
while a < b :
if liste_triee[m] == element :
return m
elif liste_triee[m] > element :
b = m-1
else :
a = m+1
m = (a+b)//2
return a
File: td_note_2014.tex, line 110
def deux_recherches(element,liste_impair,liste_pair) :
if recherche_dichotomique(element, liste_impair) == -1 :
return recherche_dichotomique(element, liste_pair)
else : return recherche_dichotomique(element, liste_impair)
, énoncé 2014
#coding: latin-1
######### énoncé 1, exercice 2 distance de Levenstein
## question 1
def distance_edition(mot1, mot2):
"""
première fonction retrouvée à : http://www.xavierdupre.fr/blog/2013-12-02_nojs.html
"""
dist = { (-1,-1): 0 }
for i,c in enumerate(mot1) :
dist[i,-1] = dist[i-1,-1] + 1
dist[-1,i] = dist[-1,i-1] + 1
for j,d in enumerate(mot2) :
opt = [ ]
if (i-1,j) in dist :
x = dist[i-1,j] + 1
opt.append(x)
if (i,j-1) in dist :
x = dist[i,j-1] + 1
opt.append(x)
if (i-1,j-1) in dist :
x = dist[i-1,j-1] + (1 if c != d else 0)
opt.append(x)
dist[i,j] = min(opt)
return dist[len(mot1)-1,len(mot2)-1]
print ("****1*")
print (distance_edition("levenstein","levenshtein")) # 1
print (distance_edition("bonbon","bonbom")) # 1
print (distance_edition("example","exemples")) # 2
print (distance_edition("esche","eche")) # 1
## question 2
print ("****2*")
print (distance_edition("levenshtein","levenstein")) # 1
print (distance_edition("bonbom","bonbon")) # 1
print (distance_edition("exemples","example")) # 2
print (distance_edition("eche","esche")) # 1
## question 3
def distance_edition(mot1, mot2):
dist = { (-1,-1): 0 }
for i,c in enumerate(mot1) :
dist[i,-1] = dist[i-1,-1] + 1
dist[-1,i] = dist[-1,i-1] + 1
for j,d in enumerate(mot2) :
opt = [ ]
if (i-1,j) in dist :
x = dist[i-1,j] + 1
opt.append(x)
if (i,j-1) in dist :
x = dist[i,j-1] + 1
opt.append(x)
if (i-1,j-1) in dist :
if c == d : x = dist[i-1,j-1] ##
elif c in ['n','m'] and d in ['n','m'] : x = dist[i-1,j-1] + 0.5 ##
else : x = dist[i-1,j-1] + 1 ##
opt.append(x)
dist[i,j] = min(opt)
return dist[len(mot1)-1,len(mot2)-1]
print ("****3*")
print (distance_edition("levenstein","levenshtein")) # 1
print (distance_edition("bonbon","bonbom")) # 0.5
print (distance_edition("example","exemples")) # 2
print (distance_edition("esche","eche")) # 1
print (distance_edition("levenshtein","levenstein")) # 1
print (distance_edition("bonbom","bonbon")) # 0.5
print (distance_edition("exemples","example")) # 2
print (distance_edition("eche","esche")) # 1
## question 4
def distance_edition(mot1, mot2):
dist = { (-1,-1): 0 }
for i,c in enumerate(mot1) :
dist[i,-1] = dist[i-1,-1] + 1
dist[-1,i] = dist[-1,i-1] + 1
for j,d in enumerate(mot2) :
opt = [ ]
if (i-1,j) in dist :
if c == "s" : x = dist[i-1,j] + 0.5 ##
else : x = dist[i-1,j] + 1 ##
opt.append(x)
if (i,j-1) in dist :
if d == "s" : x = dist[i,j-1] + 0.5 ##
else : x = dist[i,j-1] + 1 ##
opt.append(x)
if (i-1,j-1) in dist :
if c == d : x = dist[i-1,j-1]
elif c in ['n','m'] and d in ['n','m'] : x = dist[i-1,j-1] + 0.5
else : x = dist[i-1,j-1] + 1
opt.append(x)
dist[i,j] = min(opt)
return dist[len(mot1)-1,len(mot2)-1]
print ("****4*")
print (distance_edition("levenstein","levenshtein")) # 1
print (distance_edition("bonbon","bonbom")) # 0.5
print (distance_edition("example","exemples")) # 1.5
print (distance_edition("esche","eche")) # 0.5
print (distance_edition("levenshtein","levenstein")) # 1
print (distance_edition("bonbom","bonbon")) # 0.5
print (distance_edition("exemples","example")) # 1.5
print (distance_edition("eche","esche")) # 0.5
## question 5
def distance_edition(mot1, mot2):
dist = { (-1,-1): 0 }
for i,c in enumerate(mot1) :
dist[i,-1] = dist[i-1,-1] + 1
dist[-1,i] = dist[-1,i-1] + 1
for j,d in enumerate(mot2) :
opt = [ ]
if (i-1,j) in dist :
if c == "s" :
if i == len(mot1)-1 : x = dist[i-1,j] + 0.2 ##
else : x = dist[i-1,j] + 0.5 ##
else : x = dist[i-1,j] + 1
opt.append(x)
if (i,j-1) in dist :
if d == "s" :
if j == len(mot2)-1 : x = dist[i,j-1] + 0.2 ##
else : x = dist[i,j-1] + 0.5 ##
else : x = dist[i,j-1] + 1
opt.append(x)
if (i-1,j-1) in dist :
if c == d : x = dist[i-1,j-1]
elif c in ['n','m'] and d in ['n','m'] : x = dist[i-1,j-1] + 0.5
else : x = dist[i-1,j-1] + 1
opt.append(x)
dist[i,j] = min(opt)
return dist[len(mot1)-1,len(mot2)-1]
print ("****5*")
print (distance_edition("levenstein","levenshtein")) # 1
print (distance_edition("bonbon","bonbom")) # 0.5
print (distance_edition("example","exemples")) # 1.2
print (distance_edition("esche","eche")) # 0.5
print (distance_edition("levenshtein","levenstein")) # 1
print (distance_edition("bonbom","bonbon")) # 0.5
print (distance_edition("exemples","example")) # 1.2
print (distance_edition("eche","esche")) # 0.5
File: td_note_2014.tex, line 176
if (i-1,j-1) in dist :
x = dist[i-1,j-1] + (0.5 if c != d else 0) # 1 --> 0.5
, énoncé 2014
#coding: latin-1
######### énoncé 2, exercice 3 distance de Levenstein
## question 1
def distance_edition(mot1, mot2):
"""
première fonction retrouvée à : http://www.xavierdupre.fr/blog/2013-12-02_nojs.html
"""
dist = { (-1,-1): 0 }
for i,c in enumerate(mot1) :
dist[i,-1] = dist[i-1,-1] + 1
dist[-1,i] = dist[-1,i-1] + 1
for j,d in enumerate(mot2) :
opt = [ ]
if (i-1,j) in dist :
x = dist[i-1,j] + 1
opt.append(x)
if (i,j-1) in dist :
x = dist[i,j-1] + 1
opt.append(x)
if (i-1,j-1) in dist :
x = dist[i-1,j-1] + (1 if c != d else 0)
opt.append(x)
dist[i,j] = min(opt)
return dist[len(mot1)-1,len(mot2)-1]
print ("****1*")
print (distance_edition("levenstein","levenstien")) # 2
print (distance_edition("bonbbon","bonbon")) # 1
print (distance_edition("example","exemples")) # 2
## question 2
print ("****2*")
print (distance_edition("levenstien","levenstein")) # 2
print (distance_edition("bonbon","bonbbon")) # 1
print (distance_edition("exemples","example")) # 2
## question 3
def distance_edition(mot1, mot2):
"""
première fonction retrouvée à : http://www.xavierdupre.fr/blog/2013-12-02_nojs.html
"""
dist = { (-1,-1): 0 }
for i,c in enumerate(mot1) :
dist[i,-1] = dist[i-1,-1] + 1
dist[-1,i] = dist[-1,i-1] + 1
for j,d in enumerate(mot2) :
opt = [ ]
if (i-1,j) in dist :
x = dist[i-1,j] + 1
opt.append(x)
if (i,j-1) in dist :
x = dist[i,j-1] + 1
opt.append(x)
if (i-1,j-1) in dist :
x = dist[i-1,j-1] + (1 if c != d else 0)
opt.append(x)
if (i-2,j-2) in dist : ##
if c == mot2[j-1] and d == mot1[i-1] : ##
x = dist[i-2,j-2] + 1 ##
opt.append(x) ##
dist[i,j] = min(opt)
return dist[len(mot1)-1,len(mot2)-1]
print ("****3*")
print (distance_edition("levenstein","levenstien")) # 1
print (distance_edition("bonbbon","bonbon")) # 1
print (distance_edition("example","exemples")) # 2
print (distance_edition("levenstien","levenstein")) # 1
print (distance_edition("bonbon","bonbbon")) # 1
print (distance_edition("exemples","example")) # 2
## question 4
def distance_edition(mot1, mot2):
"""
première fonction retrouvée à : http://www.xavierdupre.fr/blog/2013-12-02_nojs.html
"""
dist = { (-1,-1): 0 }
for i,c in enumerate(mot1) :
dist[i,-1] = dist[i-1,-1] + 1
dist[-1,i] = dist[-1,i-1] + 1
for j,d in enumerate(mot2) :
opt = [ ]
if (i-1,j) in dist :
x = dist[i-1,j] + 1
opt.append(x)
if (i,j-1) in dist :
x = dist[i,j-1] + 1
opt.append(x)
if (i-1,j-1) in dist :
x = dist[i-1,j-1] + (1 if c != d else 0)
opt.append(x)
if (i-2,j-2) in dist :
if c == mot2[j-1] and d == mot1[i-1] :
x = dist[i-2,j-2] + 1
opt.append(x)
if (i-2,j-1) in dist and c == d == mot1[i-1] : ##
x = dist[i-2,j-1] + 0.45 ##
opt.append(x) ##
if (i-1,j-2) in dist and c == d == mot2[j-1] : ##
x = dist[i-1,j-2] + 0.45 ##
opt.append(x) ##
dist[i,j] = min(opt)
return dist[len(mot1)-1,len(mot2)-1]
print ("****4*")
print (distance_edition("levenstein","levenstien")) # 1
print (distance_edition("bonbbon","bonbon")) # 0.45
print (distance_edition("example","exemples")) # 2
print (distance_edition("levenstien","levenstein")) # 1
print (distance_edition("bonbon","bonbbon")) # 0.45
print (distance_edition("exemples","example")) # 2
File: td_note_2014.tex, line 252
if abs(i-j)==1 and mot1[i]==mot2[j] and (mot1[i+1]==mot2[j-1] or mot1[i-1]==mot2[j+1]):
File: td_note_2014.tex, line 260
if abs(j-i)==1 and mot1[i]==mot2[j] and (mot1[i+1]==mot2[j-1] or mot1[i-1]==mot2[j+1]): dist[i,j] = min(opt)-1 else: dist[i,j]=min(opt)
vérifier que tous les éléments de la liste sont bien retrouvés
l = [ 0, 2, 4, 6, 8, 100, 1000 ]
for i in l :
print (i,recherche_dichotomique(i, l))
extrait 2 à copier pour l'énoncé de décembre 2013
def deux_recherches(element, liste1, liste2) :
# ....
return position_dans_liste1, position_dans_liste2
, énoncé 2014
#coding: latin-1
######### énoncé 1, exercice 1, recherche dichotomique
## question 1
def recherche_dichotomique( element, liste_triee ):
"""
premier code: http://www.xavierdupre.fr/blog/2013-12-01_nojs.html
"""
a = 0
b = len(liste_triee)-1
m = (a+b)//2
while a < b :
if liste_triee[m] == element :
return m
elif liste_triee[m] > element :
b = m-1
else :
a = m+1
m = (a+b)//2
return a
l = [ 0, 2, 3, 5, 10, 100, 340 ]
print (recherche_dichotomique(100, l)) # affiche 5
## question 2
def recherche_dichotomique( element, liste_triee ):
a = 0
b = len(liste_triee)-1
m = (a+b)//2
while a < b :
if liste_triee[m] == element :
return m
elif liste_triee[m] > element :
b = m-1
else :
a = m+1
m = (a+b)//2
if liste_triee[a] != element : return -1 # ligne ajoutée
else : return m
l = [ 0, 2, 4, 6, 8, 100, 1000 ]
for i in l :
print (i,recherche_dichotomique(i, l))
# vérifier qu'on retrouve tous les éléments existant
print (recherche_dichotomique(1, l)) # affiche -1
## question 3
def deux_recherches(element,liste1,liste2) :
return recherche_dichotomique(element, liste1) , \
recherche_dichotomique(element,liste2)
l1 = [ 0, 2, 4, 6, 8, 100, 1000 ]
l2 = [ 1200, 3000, 4000, 5555 ]
print (deux_recherches(100,l1,l2) ) # affiche (5,-1)
## question 4
"""
Les logarithmes sont en base 2.
cas 1 : 1000 ln(n) + 10 (ln(n) + ln(10n)) = 1020 ln(n) + 10 ln(10) = C1
cas 2 : 1010 ln(n + 10n) = 1010 ln(n) + 1010 ln(11) = C2
delta = C2 - C1 = -10 ln(n) + 1010 ln(11) - 10 ln(10)
Conclusion : pour n petit, le cas C1 est préférable, pour les n grands, c'est le cas 2.
"""
## question 5
def deux_recherches(element,liste1,liste2) :
if element > liste1[-1] :
return -1, recherche_dichotomique(element, liste2)
else :
return recherche_dichotomique(element,liste1), -1
l1 = [ 0, 2, 4, 6, 8, 100, 1000 ]
l2 = [ 1200, 3000, 4000, 5555 ]
print (deux_recherches(100,l1,l2) ) # affiche (5,-1)