Exercices corrigés sur la récursivité (TD 01)
Exercice 1
Étant donné un tableau trié de n entiers distincts où chaque entier est compris entre 0 et m-1 et m>n. Recherchez le plus petit nombre manquant dans le tableau. Proposez un algorithme avec une complexité logarithmique (\(O(log_n)\))
Exemples
3
(4,5,10,11),n=4,m=12
0
def elementManquant(tab, debut, fin):
if debut > fin:
return fin+1
if debut != tab[debut]:
return debut
milieu = (debut+fin)//2
if tab[milieu] == milieu:
return elementManquant(tab, milieu+1, fin)
return elementManquant(tab, debut, milieu)
tab=[0,1,2,6,9]
n=len(tab)
print("Premier élément manquant est :", elementManquant(tab, 0, n-1))
Exercice 2
Étant donné un tableau non trié d’entiers non négatifs, trouvez un sous-tableau continu qui a la somme donnée.
Exemples
La somme est trouvée entre les indices 2 et 4
(1, 4), somme = 0
Aucun sous-tableau trouvé
def soustableau(tab, somme):
n = len(tab)
for i in range(n):
s = tab[i]
j = i+1
while j <= n:
if s == somme:
print("le sous-tableau est entre {} et {}".format(i, j-1))
return
if s > somme or j == n:
break
s += tab[j]
j += 1
print("le sous-tableau n’existe pas")
tab = [15, 2, 4, 8, 9, 5, 10, 23]
n = len(tab)
somme = 23
soustableau(tab, n, somme)
Exercice 3
Étant donné un tableau d’entiers triés. Nous devons trouver la valeur la plus proche du nombre donné. Le tableau peut contenir des valeurs en double et des nombres négatifs.
Exemples
9
(2,5,6,7,8,8,9), objectif=4
5
# Méthode pour comparer laquelle est la plus proche.
# Nous trouvons le plus proche en prenant la différence entre la cible (obj) et les deux valeurs.
# nous supposons que val2 est supérieur à val1 et que la cible se situe entre les deux.
def proche(val1, val2, obj):
if obj-val1 >= val2-obj:
return val2
else:
return val1
def plusProche(tab, obj):
n = len(tab)
if obj <= tab [0]:
return tab [0]
if obj >= tab[n-1]:
return
# faire la recherche dichtomique
debut, fin=0,n
milieu = 0
while debut < fin:
milieu = (debut+fin)//2
if tab[milieu] == obj:
return obj
if obj < tab[milieu]:
# Si la cible est est supérieure à la précédente du milieu
# renvoie la plus proche des deux.
if milieu>0 and obj> tab[milieu-1]:
return proche(tab[milieu-1],tab[milieu],obj)
fin=milieu
else:
# Si la cible est inférieure à la suivante du milieu, renvoie la
# plus proche des deux
if milieu < n-1 and obj < tab[milieu+1]:
return proche(tab[milieu], tab[milieu+1], obj)
debut=milieu
# Il ne reste qu’un seul élément après la recherche => c’est le plus proche
return tab[milieu]
tab = [1, 2, 4, 5, 6, 6, 8, 9]
n = len(tab)
cible = 11
print(plusProche(tab, cible))
Exercice 4
Étant donné une valeur N, si nous voulons effectuer un changement pour N Dirhams, et que nous avons une quantité infinie de chacune des pièces évaluées \(S=S1, S2, .., Sm\), de combien de façons pouvons-nous effectuer le changement ? L’ordre des pièces n’a pas d’importance.
Exemples
4 solutions ((1,1,1,1), (1,1,2), (2,2), (1, 3))
N = 10 et S = (2, 5, 3, 6)
5 solutions((2,2,2,2,2), (2,2,3,3), (2,2,6), (2,3,5) et (5,5))
def nombreFacons(S, N, n):
# Si N est 0, il y'a 1 solution (n'incluez aucune pièce)
if N==0:
return 1
# si N est inférieure à 0, aucune solution
if N<0:
return 0
# S'il y'a pas de pièce (n=0) et que N est supérieur à 0
# alors aucune solution
if N>=1 and n<=0:
return 0
# le nombre et la somme des solutions :
# (i) incluant S[n-1]
# (ii) Excluant S[n-1]
return nombreFacons(S,N-S[n-1],n)+nombreFacons(S,N,n-1)
pieces=[2,5,3,6]
N=10
print(nombreFacons(pieces,N,len(pieces)))
Exercice 5
Étant donné deux séquences, trouvez la longueur de la sous-séquence la plus longue présente dans les deux. Une sous-séquence est une séquence qui apparaît dans le même ordre relatif, mais pas nécessairement contiguë. Par exemple, "abc", "abg", "bdf", "aeg", "acefg", .. etc. sont des sous-séquences de "abcdefg". Ecrire une fonction pour compter la plus longue sous-séquence.
Exemples
3 (ADH)
s1="AGGTAB", s2="GXTXAYB"
4 (GTAB)
def plusLongueSequence(X, Y, m, n):
if m == 0 or n == 0:
return 0
elif X[m-1] == Y[n-1]:
return 1 + plusLongueSequence(X, Y, m-1, n-1)
else:
return max(plusLongueSequence(X, Y, m, n-1), plusLongueSequence(X, Y, m-1, n))
X = "AGGTAB"
Y = "GXTXAYB"
print("plus longue sous-séquence", plusLongueSequence(X , Y, len(X), len(Y)))
