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

Exercice

Trouver le plus petit nombre manquant dans un tableau trié

Niveau : Intermédiaire

Étant donné un tableau trié de n entiers distincts, où chaque entier est compris entre 0 et m-1, avec m > n, écrire un algorithme qui recherche le plus petit nombre manquant dans ce tableau.

On demande une solution de complexité logarithmique.

Objectif Proposer un algorithme de type recherche dichotomique, de complexité O(log n).

Exemples

Entrée

(0, 1, 2, 6, 9), n = 5, m = 10

Sortie

Exemple 2

Entrée

(4, 5, 10, 11), n = 4, m = 12

Sortie

Solution détaillée

Principe : dans un tableau trié sans trou, on devrait avoir tab[i] = i. Dès qu’une différence apparaît, cela signifie qu’un entier manque.
Idée : utiliser une recherche dichotomique pour trouver la première position où tab[i] ≠ i.

Implémentation :

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

Complexité : la recherche se fait par divisions successives de l’intervalle, donc la complexité est O(log n).

Exercice

Trouver un sous-tableau continu de somme donnée

Niveau : Débutant

Étant donné un tableau non trié d’entiers non négatifs, écrire une fonction qui trouve un sous-tableau continu dont la somme des éléments est égale à une valeur donnée.

Exemple

Entrée

(1, 4, 20, 3, 10, 5), somme = 33

Sortie

La somme est trouvée entre les indices 2 et 4

Exemple 2

Entrée

(1, 4), somme = 0

Sortie

Aucun sous-tableau trouvé

Solution détaillée

Principe : pour chaque position de départ i, on accumule les éléments suivants jusqu’à atteindre ou dépasser la somme demandée.
Arrêt : dès que la somme partielle est égale à la somme recherchée, on affiche les indices du sous-tableau.

Implémentation :

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]
somme = 23
soustableau(tab, somme)

Résultat attendu : si un sous-tableau existe, on affiche ses bornes, sinon on indique qu’aucune solution n’a été trouvée.

Exercice

Trouver la valeur la plus proche d’un nombre donné

Niveau : Intermédiaire

Étant donné un tableau trié d’entiers, pouvant contenir des doublons et des valeurs négatives, écrire une fonction qui retourne la valeur la plus proche d’un nombre cible.

Exemple

Entrée

(1, 2, 4, 5, 6, 6, 8, 9), objectif = 11

Sortie

Exemple 2

Entrée

(2, 5, 6, 7, 8, 8, 9), objectif = 4

Sortie

Solution détaillée

Principe : utiliser une recherche dichotomique pour localiser la zone où se trouve la cible, puis comparer les deux valeurs voisines.
Fonction auxiliaire : la fonction proche compare deux valeurs candidates et retourne celle qui est la plus proche de l’objectif.

Implémentation :

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 tab[n - 1]

    debut, fin = 0, n
    milieu = 0

    while debut < fin:
        milieu = (debut + fin) // 2

        if tab[milieu] == obj:
            return obj

        if obj < tab[milieu]:
            if milieu > 0 and obj > tab[milieu - 1]:
                return proche(tab[milieu - 1], tab[milieu], obj)

            fin = milieu
        else:
            if milieu < n - 1 and obj < tab[milieu + 1]:
                return proche(tab[milieu], tab[milieu + 1], obj)

            debut = milieu + 1

    return tab[milieu]


tab = [1, 2, 4, 5, 6, 6, 8, 9]
cible = 11
print(plusProche(tab, cible))

Résultat attendu : la fonction retourne l’élément du tableau ayant la plus petite distance à la cible.

Exercice

Compter le nombre de façons de rendre la monnaie

Niveau : Intermédiaire

Étant donné un montant N et un ensemble de pièces S = (S1, S2, ..., Sm) disponibles en quantité infinie, écrire une fonction qui compte le nombre de façons d’obtenir exactement N.

L’ordre des pièces n’a pas d’importance.

Remarque Le programme renvoie uniquement le nombre de solutions et non la liste détaillée des décompositions possibles.

Exemple

Entrée

N = 4 et S = (1, 2, 3)

Sortie

Explication : les solutions sont : (1,1,1,1), (1,1,2), (2,2) et (1,3).

Exemple 2

Entrée

N = 10 et S = (2, 5, 3, 6)

Sortie

Solution détaillée

Principe : pour chaque pièce, deux choix sont possibles : l’inclure dans la somme ou l’exclure.
Cas de base : si N == 0, il y a une solution ; si N < 0, aucune solution ; si aucune pièce ne reste alors que N > 0, aucune solution.

Implémentation :

def nombreFacons(S, N, n):
    if N == 0:
        return 1

    if N < 0:
        return 0

    if N >= 1 and n <= 0:
        return 0

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

Résultat attendu : le programme retourne le nombre total de façons de rendre exactement la somme demandée.

Exercice

Longueur de la plus longue sous-séquence commune

Niveau : Intermédiaire

Étant données deux séquences, écrire une fonction qui détermine la longueur de la plus longue sous-séquence commune.

Une sous-séquence apparaît dans le même ordre relatif, mais pas nécessairement de façon contiguë.

Remarque Le programme renvoie uniquement la longueur de la plus longue sous-séquence commune, et non la sous-séquence elle-même.

Exemple

Entrée

s1 = "ABCDGH", s2 = "AEDFHR"

Sortie

Explication : une plus longue sous-séquence commune est ADH.

Exemple 2

Entrée

s1 = "AGGTAB", s2 = "GXTXAYB"

Sortie

Explication : une plus longue sous-séquence commune est GTAB.

Solution détaillée

Principe : si les derniers caractères des deux chaînes sont égaux, ils participent à la sous-séquence commune ; sinon, on essaie les deux possibilités en retirant un caractère d’une des chaînes.
Cas de base : si l’une des deux chaînes est vide, la longueur de la plus longue sous-séquence commune vaut 0.

Implémentation :

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

Résultat attendu : le programme retourne la longueur de la plus longue sous-séquence commune entre les deux chaînes.

Sortie

// La sortie apparaîtra ici…

Prêt · Ctrl+Entrée pour exécuter

Exercices python récursivité

Suivant Exercices corrigés sur la récursivité (TD 02)

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

Trouver le plus petit nombre manquant dans un tableau trié

Trouver un sous-tableau continu de somme donnée

Trouver la valeur la plus proche d’un nombre donné

Compter le nombre de façons de rendre la monnaie

Longueur de la plus longue sous-séquence commune

Discussion (0)

Laisser un commentaire

Structures de données

Algorithmes

Programmation

Bases de données

CPGE

Modules informatique

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

Trouver le plus petit nombre manquant dans un tableau trié

Trouver un sous-tableau continu de somme donnée

Trouver la valeur la plus proche d’un nombre donné

Compter le nombre de façons de rendre la monnaie

Longueur de la plus longue sous-séquence commune

Discussion (0)

Laisser un commentaire