adplus-dvertising

Exercices corrigés sur la récursivité (TD 01)

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
  (0,1,2,6,9),n=5,m=10
3
  (4,5,10,11),n=4,m=12
0

Voir solution

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
  (1,4,20,3,10,5),somme=33
La somme est trouvée entre les indices 2 et 4
  (1, 4), somme = 0
Aucun sous-tableau trouvé

Voir solution

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
  (1,2,4,5,6,6,8,9),objectif=11
9
  (2,5,6,7,8,8,9), objectif=4
5

Voir solution

# 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
  N = 4 et S = (1,2,3)
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))
 le programme renvoie uniquement le nombre de solutions et non les solutions.

Voir solution

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
  s1="ABCDGH" , s2="AEDFHR"
3 (ADH)
  s1="AGGTAB", s2="GXTXAYB"
4 (GTAB)
 le programme renvoie uniquement la longueur de la sous-séquence et non la sous-séquence.

Voir solution

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)))
                                
Partager ce cours avec tes amis :
 
Rédigé par ESSADDOUKI Mostafa
ESSADDOUKI
The education of the 21st century opens up opportunities to not merely teach, but to coach, mentor, nurture and inspire.