Épreuve pratique

Note de service

Note de service

Sujets

Tous les sujets de l’épreuve pratique de NSI se trouvent sur la Banque Nationale de Sujets.

Algorithmes à connaitre

Voici une liste (non exhaustive) d’algorithmes vus en classe, à programmer lors du 1^er exercice de l’épreuve pratique.

Tableaux (listes Python)

Pour les algorithmes suivants, seules les opérations suivantes sur les listes sont autorisées :

• longueur : len(L)
• accès à un élément par son indice : a = L[i](indices positifs)
• affectation d’un élément par son indice : L[i] = b(indices positifs)

Interdiction d’utiliser (sauf mention contraire) les méthodes append, insert, pop, …, ni d’utiliser le slicing.

Rechercher la plus grande valeur dans un tableau

Écrire une fonction plus_grand qui prend en paramètres un tableau (liste Python), et qui renvoie un tuple contenant la plus grande valeur présente dans le tableau, ainsi que son indice.

Exemples :

>>> plus_grand([4, 8, 7, 1, 0, 5, 9, 7, 3])
(9, 6)

def plus_grand(t):
    m, j = t[0], 0
    for i in range(1, len(t)):
        if t[i] > m:
            m, j = t[i], i
    return m, j

Rechercher les occurrences d’une valeur dans un tableau

Écrire une fonction rechercher qui prend en paramètres un tableau (liste Python) et une valeur (type quelconque), et qui renvoie la liste des indices de cette valeur dans le tableau.

Pour cet exercice, la méthode de liste append est autorisée.

Exemples :

>>> rechercher([4, 8, 7, 1, 0, 5, 9, 7, 3], 7)
[2,7]
>>> rechercher([4, 8, 7, 1, 0, 5, 9, 7, 3], 2)
[]
>>> rechercher([4, 8, 7, 1, 0, 5, 9, 7, 3], 3)
[8]

def rechercher(t, v):
    p = []
    for i in range(len(t)):
        if t[i] == v:
            p.append(i)
    return p

Rechercher les doublons dans un tableau

Écrire une fonction doublons qui prend en paramètres un tableau (liste Python), et qui renvoie la dictionnaire des valeurs qui se trouvent en plusieurs exemplaires dans le tableau, sous la forme {valeur du tableau : nombre d'exemplaires}.

Exemples :

>>> doublons([4, 8, 7, 1, 0, 5, 9, 7, 3])
[7]

Calculer la moyenne des valeurs d’un tableau

Écrire une fonction moyenne qui prend en paramètres un tableau (liste Python), et qui renvoie la moyenne arithmétique des valeurs du tableau.

Exemples :

>>> moyenne([4, 8, 7, 1, 0, 5, 9, 7, 3])
3.888888889

Renverser un tableau sur place

Écrire une fonction renverser qui prend en paramètres un tableau (liste Python), et qui renverse le tableau (le premier élément se retrouve à la fin du tableau, …) sur place (la fonction ne renvoie rien, mais après son appel, le tableau passé en argument est renversé).

Exemples :

>>> T = [4, 8, 7, 1, 0, 5, 9, 7, 3]
>>> renverser(T)
>>> T
[3, 7, 9, 5, 0, 1, 7, 8, 4]

def renverser(t):
    l = len(t)
    for i in range(l//2):
        t[i], t[(l-1)-i] = t[(l-1)-i], t[i] # permutation

Rechercher une valeur dans un tableau trié, par dichotomie

Écrire une fonction dichotomie qui prend en paramètres un tableau (liste Python) et une valeur (type quelconque), et qui renvoie l’indice de cette valeur dans le tableau, ou bien None si elle ne s’y trouve pas (on suppose que le tableau ne comporte pas de doublons).

Exemples :

>>> dichotomie([1, 2, 3, 5, 9, 12, 15, 16, 19], 9)
4
>>> dichotomie([1, 2, 3, 5, 9, 12, 15, 16, 19], 10) 
None

Déterminer la hauteur d’un arbre

À partir d’une structure d’arbre fournie (objet ou pas), réaliser un algorithme de détermination de la hauteur d’un arbre.

voir : hauteur d’un arbre

Parcourir un arbre binaire

À partir d’une structure d’arbre fournie (objet ou pas), réaliser un algorithme de parcours d’un arbre, selon l’une des 4 techniques suivantes :

• ordre infixe
• ordre suffixe
• ordre préfixe
• parcours en largeur

voir : parcourir_un_arbre