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)))