Recherche d'un maximum par diviser pour régner

Application directe du cours · niveau 1 (application) · NSI (terminale), chapitre 6 — Diviser pour régner

Énoncé

Recherche d'un maximum par diviser pour régner.

Écrire une fonction qui calcule le maximum d'une liste non vide en la coupant récursivement en deux moitiés.

Corrigé


def maximum(tab, g, d):
    if g == d:                       # cas de base : un seul element
        return tab[g]
    m = (g + d) // 2
    max_g = maximum(tab, g, m)       # max de la moitie gauche
    max_d = maximum(tab, m + 1, d)   # max de la moitie droite
    return max_g if max_g > max_d else max_d

# appel : maximum(tab, 0, len(tab) - 1)

La complexité est $O (n)$ : chaque élément est examiné une fois.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.