, correction 2012
# coding: latin-1
# question 1
def frequence_lettre (mot) :
res = { }
for c in mot :
if c in res : res[c] += 1
else : res [c] = 1
return res
print frequence_lettre ("aviateur")
# affiche {'a': 2, 'e': 1, 'i': 1, 'r': 1, 'u': 1, 't': 1, 'v': 1}
# Deux autres écritures de la fonction
def frequence_lettre (mot) :
res = { c:0 for c in mot }
for c in mot : res[c] += 1
return res
def frequence_lettre (mot) :
res = { }
for c in mot :
# la méthode get retourne res[c] si cette valeur existe, 0 sinon
res[c] = res.get( c, 0 ) + 1
return res
# question 2
def anagramme (mot1, mot2) :
h1 = frequence_lettre(mot1)
h2 = frequence_lettre(mot2)
# il fallait éviter d'écrire la ligne suivante bien qu'elle retourne le résultat cherché :
# return h1 == h2
for c in h1 :
if c not in h2 or h1[c] != h2[c] : return False
# il ne faut pas oublier cette seconde partie
for c in h2 :
if c not in h1 : return False
return True
a,b = "anagramme", "agrammane"
print anagramme (a,b), anagramme (b,a) # affiche True, True
# on vérifie que la fonctionne marche aussi dans l'autre cas
a,b = "anagramme", "agrummane"
print anagramme (a,b), anagramme (b,a) # affiche False, False
# on pouvait faire plus rapide en éliminant les cas évidents
def anagramme (mot1, mot2) :
if len(mot1) != len(mot2) : return False
h1 = frequence_lettre(mot1)
h2 = frequence_lettre(mot2)
if len(h1) != len(h2) : return False
for c in h1 :
if h1[c] != h2.get(c, 0) : return False
return True
, correction 2012
# coding: latin-1
# question 1
def factorielle (n) :
res = 1
while n > 1 :
res *= n
n -= 1
return res
print factorielle (3)
# voici la version récursive qui n'était pas demandée :
def factorielle_recursive (n) :
return n*factorielle_recursive (n-1) if n > 1 else 1
# question 2
def f(a,b) :
# f(a,b) = f(a-1,b) + f(a,b-1)
# la formule implique de calculer toutes les valeurs f(i,j)
# avec (i,j) dans [[0,a]] x [[0,b]]
# un moyen afin d'éviter de trop nombreux calculs est de
# stocker les valeurs intermédiaires de f dans une matrice
# il faut ensuite s'assurer que f(a-1,b) et f(a,b-1)
# ont déjà été calculées avant de calculer f(a,b)
# pour cela, on parcourt la matrice dans le sens des i et j croissants
# il ne faut pas oublier les a+1,b+1 car range (a) est égal à [ 0,1, ..., a-1 ]
mat = [ [ 0 for i in range (b+1) ] for j in range (a+1) ]
for i in range (a+1) :
for j in range (b+1) :
if i == 0 or j == 0 :
mat [i][j] = max (i,j)
else :
mat [i][j] = mat [i-1][j] + mat[i][j-1]
return mat [a][b]
# on teste pour des valeurs simples
print f(0,5) # affiche 5
print f(1,1) # affiche 2
# on vérifie en suite que cela marche pour a < b et b > a
print f (4,5) # affiche 210
print f (5,4) # affiche 210
# autres variantes
# la version récursive ci-dessous est juste beaucoup plus longue, elle appelle
# la fonction f_recursive autant de fois que la valeur retournée
# par la fonction cout_recursive alors que la fonction précédente
# effectue de l'ordre de O(a*b) calculs
def f_recursive(a,b) :
return f_recursive(a-1,b) + f_recursive(a,b-1) if a > 0 and b > 0 else max(a,b)
def cout_recursive(a,b) :
return cout_recursive(a-1,b) + cout_recursive(a,b-1) if a > 0 and b > 0 else 1
# une autre version non récursive
def f(a,b) :
mat = { }
for i in range (a+1) :
for j in range (b+1) :
mat [i,j] = mat [i-1,j] + mat[i,j-1] if i > 0 and j > 0 else max (i,j)
return mat [a,b]
, correction 2012
def f_recursive(a,b, memoire) :
if (a,b) in memoire : return memoire [a,b]
else :
res = f_recursive(a-1,b, memoire) + f_recursive(a,b-1, memoire) \
if a > 0 and b > 0 else max(a,b)
memoire [a,b] = res
return res
, correction 2012
# coding: latin-1
# question 1
def somme_partielle (li, i, j) :
r = 0
for a in range (i,j) :
r += li [a]
return r
# question 2
def plus_grande_sous_liste (li) :
meilleur = min(li) # ligne A
im,jm = -1,-1
for i in range (0,len(li)) :
for j in range (i+1, len(li)+1) : # ne pas oublier +1 car sinon
# le dernier élément n'est jamais pris en compte
s = somme_partielle(li, i,j)
if s > meilleur :
meilleur = s
im,jm = i,j
return li [im:jm]
# si li ne contient que des valeurs positives, la solution est évidemment la liste entière
# c'est pourquoi il faut tester cette fonction avec des valeurs négatives
li = [ 4,-6,7,-1,8,-50,3]
m = plus_grande_sous_liste(li)
print(m) # affiche [7, -1, 8]
li = [1,2,3,4,5,-98,78,9,7,7]
m = plus_grande_sous_liste(li)
print(m) # affiche [79, 9, 7, 7]
# autre version plus courte
def plus_grande_sous_liste (li) :
solution = [ (somme_partielle(li,i,j), i, j) \
for i in range (0,len(li)) \
for j in range (i+1, len(li)+1) ]
m = max(solution)
return li [m[1]:m[2]]
, correction 2012
def plus_grande_sous_liste_n2 (li) :
meilleur = 0
im,jm = -1,-1
for i in range (0,len(li)) :
s = 0
for j in range (i, len(li)) :
s += li[j]
if s > meilleur :
meilleur = s
im,jm = i,j+1
return li [im:jm]
li = [ 4,-6,7,-1,8,-50,3]
m = plus_grande_sous_liste_n2(li)
print(m) # affiche [7, -1, 8]
li = [1,2,3,4,5,-98,78,9,7,7]
m = plus_grande_sous_liste_n2(li)
print(m) # affiche [79, 9, 7, 7]
, correction 2012
#coding:latin-1
def plus_grande_sous_liste_rapide_r (li, i,j) :
if i == j : return 0
elif i+1 == j : return li[i],i,i+1
milieu = (i+j)//2
# on coupe le problème deux
ma,ia,ja = plus_grande_sous_liste_rapide_r (li, i, milieu)
mb,ib,jb = plus_grande_sous_liste_rapide_r (li, milieu, j)
# pour aller encore plus vite dans un cas précis
if ja == ib :
total = ma+mb
im,jm = ia,jb
else :
# on étudie la jonction
im,jm = milieu,milieu+1
meilleur = li[milieu]
s = meilleur
for k in range (milieu+1, j) :
s += li[k]
if s > meilleur :
meilleur = s
jm = k+1
total = meilleur
meilleur = li[milieu]
s = meilleur
for k in range (milieu-1, i-1, -1) :
s += li[k]
if s > meilleur :
meilleur = s
im = k
total += meilleur - li[milieu]
if ma >= max(mb,total) : return ma,ia,ja
elif mb >= max(ma,total) : return mb,ib,jb
else : return total,im,jm
def plus_grande_sous_liste_rapide (li) :
m,i,j = plus_grande_sous_liste_rapide_r (li,0,len(li))
return li[i:j]
li = [ 4,-6,7,-1,8,-50,3]
m = plus_grande_sous_liste_rapide(li)
print(m) # affiche [7, -1, 8]
li = [1,2,3,4,5,-98,78,9,7,7]
m = plus_grande_sous_liste_rapide(li)
print(m) # affiche [79, 9, 7, 7]
, correction 2012
#-*- coding: latin-1 -*-
def plus_grande_sous_liste_n (li) :
meilleur = [ None for i in li ]
somme = [ None for i in li ]
best = None
for i,el in enumerate(li):
if i == 0 or meilleur[i-1] is None:
meilleur[i] = i
somme[i] = el
if best is None or somme[i] > somme[best]:
best = i
else:
if el >= 0 or somme[i-1] > -el :
meilleur[i] = meilleur[i-1]
somme[i] = somme[i-1] + el
if best is None or somme[i] > somme[best]:
best = i
i,j = meilleur[best], best+1
return li [i:j]
li = [ 4,-6,7,-1,8,-50,3]
m = plus_grande_sous_liste_n(li)
print(m) # affiche [7, -1, 8]
li = [1,2,3,4,5,-98,78,9,7,7]
m = plus_grande_sous_liste_n(li)
print(m) # affiche [79, 9, 7, 7]