Épreuve pratique

Voici une liste (non exhaustive) d’algorithmes vus en classe, à programmer lors du 1er 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)
Correction
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]
Correction
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]
Correction
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

 

Vous aimerez aussi...

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *