minetmaxregner.py

Created on December 15, 2024
1.15 KB
def min_max_dvr(t : list, a : 
int, b : int) -> tuple :
Cette fonction détermine le 
minimum et le maximum de 
t[a..b[ , c’est-à-dire des 
éléments de a inclus à b exclus.
Elle utilise un algorithme du 
type
"diviser pour régner".

if a < 0 or b > len(t) or a == b :
return None
elif b == a+1 : return t[a], t[a]
elif b == a+2 :
if t[a] < t[a+1] : 
return t[a], t[a+1]
else : 
return t[a+1], t[a]
else :
c = (a+b)//2
min_gauche, max_gauche = 
min_max_dvr(t, a, c)
min_droit, max_droit = 
min_max_dvr(t, c, b)
return min(min_gauche, min_droit), 
max(max_gauche, max_droit)



ASSERT : 
  
assert min_max_dvr([], 0, 4) is None  # recherche dans un tableau vide
assert min_max_dvr([2,5,-1,3,9], 0, 10) is None    # recherche hors borne
assert min_max_dvr([2,5,0,3,9], 0, 5) == (0,9)
assert min_max_dvr([-2,5,-1,3,9], 0, 5) == (-2,9)   # recherche dans un tableau 
avec des nombres négatifs
assert min_max_dvr([3], 0, 1) == (3,3) 

QUESTION :
  
# C2(10) = 2 C2(5) + 2   avec C2(5)= C2(3) + C2(2) + 2 = C2(3) + 1 + 2 
= C2(3) + 3
#C2(3)= C2(2) + C2(1) + 2 = 1 + 0 + 2 = 3
# d'où C2(10) = 14
# C2(20) = 2 C2(10) + 2 = 30
# C2(40) = 2 C2(20) + 2 = 62