Algorithmes de recherche : obtenir une moyenne, une médiane
- Fiche de cours
- Quiz et exercices
- Vidéos et podcasts
- Écrire un algorithme de calcul de la moyenne des éléments d’un tableau.
- Écrire un algorithme de recherche de la médiane des éléments d’un tableau.
- Le cout d’un calcul de moyenne d’un tableau est linéaire en n la taille du tableau.
- Il est nécessaire de trier un tableau pour en déterminer la médiane. On utilise soit la méthode sort(), soit la fonction sorted().
- Un tableau est indexé à partir de 0. Le i-ème élément a pour indice i−1.
Algorithmes de recherche : parcourir un tableau
Voici ci-dessous un algorithme qui détermine la moyenne des éléments d’un tableau Tab (non vide et non trié) de taille n.
| S ← 0 | 0 est affecté à la variable S. |
| Pour i allant de 0 à n−1 | i = 0, puis i = 1, puis i = 2, puis… i = n − 1. |
| S ← S + Tab[i] | La somme de l’ancienne valeur de S et de Tab[i] est affectée à S. |
| FinPour |
Fin de l’instruction
« Pour ». S contient alors la somme des éléments de Tab. |
| Retourner S/n | La moyenne S/n est retournée à la fin. |
En Python, la fonction moyenne(Tab) implémente un algorithme de calcul de la moyenne de Tab.
| def moyenne(Tab): | On définit la fonction moyenne. |
| S = 0 | 0 est affecté à la variable S. |
| for elt in Tab: | Pour chaque élément elt de Tab, |
| S = S + elt | on ajoute elt à S. |
| return S/len(Tab) |
On retourne la variable S/len(Tab) (somme sur longueur de la table). |
L’algorithme de la sous-partie précédente, appliqué à un tableau comportant n éléments, nécessite :
- n + 1 affectations : une affectation avant l’instruction pour et n affectations pendant celle-ci.
- n + 1 opérations : n additions dans l’instruction pour et une division.
(car a × (n + 1) + op × (n + 1) = a × n + a + op × n + op).
On obtient une fonction affine en n. On dit alors que le cout d’un algorithme de calcul de la moyenne d’un tableau est linéaire en n la taille du tableau.
Le cout d’un calcul de moyenne d’un tableau non trié est linéaire.
Il y a ensuite deux cas, suivant la parité de l’effectif n de la série.
- Si n est impair,
il y a une seule valeur centrale.
La médiane est la
-ième valeur de la série
triée.
- Si n est pair, il y
a deux valeurs centrales. La médiane est
la moyenne de la
-ième et de la 
-ième valeur de la série
triée.
Voici ci-dessous un algorithme qui détermine la médiane des éléments d’un tableau Tab (non vide et non trié) de taille n.
| Trier Tab | On obtient un tableau Tab d’éléments triés dans l’ordre croissant. |
| Si n%2 = 0, alors | Si n est pair, alors |
| med ← (Tab[n/2 − 1] + Tab[n/2])/2 | on affecte à med la moyenne des deux valeurs centrales, |
| Sinon | sinon (c’est-à-dire si n est impair), |
| med ← Tab[(n−1)/2] | on affecte à med la valeur centrale. |
| FinSi | Fin de l’instruction conditionnelle. |
| Retourner med | La médiane med est retournée à la fin. |
Il faut faire attention aux indices. Comme les tableaux sont indexés à partir de 0, la
-ième valeur est Tab[n/2 − 1] et
la 
-ième valeur est Tab[n/2].
Si Tab = [7,8,9,10,11], alors n = 5 et la médiane est Tab[2]. On obtient l’indice 2 en calculant
(
).
En Python, deux fonctions existent pour trier des tableaux : sort et sorted. Elles sont toutefois très différentes.
Si on considère le tableau Tab, alors Tab.sort() trie Tab en place, aucun autre tableau n’est créé. En revanche, sorted(Tab) crée un nouveau tableau, Tab reste inchangé.
Une variable créée est stockée dans une partie du disque dur de l’ordinateur. Le terme « en place » signifie que le tableau trié occupe le même espace mémoire que le tableau d’origine. Cela rend l’exécution plus rapide. Aucun autre espace mémoire n’est alloué.
Dans la console de Python, on a les tris suivants selon la méthode utilisée.
| avec sort() | avec sorted() |
|
>>> Tab = [1,
3, 4, 2, 5] >>> Tab [1, 3, 4, 2, 5] >>> Tab.sort() >>> Tab [1, 2, 3, 4, 5] |
>>> Tab = [1,
3, 4, 2, 5] >>> sorted(Tab) [1, 2, 3, 4, 5] >>> Tab [1, 3, 4, 2, 5] |
En Python, la fonction mediane(Tab) implémente un algorithme de calcul de la médiane de Tab.
| def mediane(Tab): | On définit la fonction médiane. |
| Tab.sort() | On trie le tableau Tab. |
| n = len(Tab) | On affecte à n la longueur de Tab. |
| if n%2 == 0: | Si n est pair, alors |
| return (Tab[n//2-1] + Tab[n//2])/2 | on retourne la moyenne des deux valeurs centrales. |
| else: | Sinon (si n est impair), |
| return Tab[(n-1)//2] | on retourne la valeur centrale. |
En Python, // renvoie un entier et / renvoie un flottant (8//2 renvoie 4 alors que 8/2 renvoie 4.0).
Pour accéder aux éléments du tableau, on utilise la division entière // et non la division décimale / car les indices des tableaux doivent être des entiers (de type int).
Il n’est pas possible de déterminer le cout de l’algorithme de la sous-partie précédente puisque l’on ne connait pas le cout d’un tri de tableau.
En général, le cout d’un algorithme n’est pas étudié si on utilise des fonctions pré-implémentées (ici la fonction médiane) dans le langage utilisé.
Évalue ce cours !
Des quiz et exercices pour mieux assimiler sa leçon
La plateforme de soutien scolaire en ligne myMaxicours propose des quiz et exercices en accompagnement de chaque fiche de cours. Les exercices permettent de vérifier si la leçon est bien comprise ou s’il reste encore des notions à revoir.
Des exercices variés pour ne pas s’ennuyer
Les exercices se déclinent sous toutes leurs formes sur myMaxicours ! Selon la matière et la classe étudiées, retrouvez des dictées, des mots à relier ou encore des phrases à compléter, mais aussi des textes à trous et bien d’autres formats !
Dans les classes de primaire, l’accent est mis sur des exercices illustrés très ludiques pour motiver les plus jeunes.
Des quiz pour une évaluation en direct
Les quiz et exercices permettent d’avoir un retour immédiat sur la bonne compréhension du cours. Une fois toutes les réponses communiquées, le résultat s’affiche à l’écran et permet à l’élève de se situer immédiatement.
myMaxicours offre des solutions efficaces de révision grâce aux fiches de cours et aux exercices associés. L’élève se rassure pour le prochain examen en testant ses connaissances au préalable.
Des vidéos et des podcasts pour apprendre différemment
Certains élèves ont une mémoire visuelle quand d’autres ont plutôt une mémoire auditive. myMaxicours s’adapte à tous les enfants et adolescents pour leur proposer un apprentissage serein et efficace.
Découvrez de nombreuses vidéos et podcasts en complément des fiches de cours et des exercices pour une année scolaire au top !
Des podcasts pour les révisions
La plateforme de soutien scolaire en ligne myMaxicours propose des podcasts de révision pour toutes les classes à examen : troisième, première et terminale.
Les ados peuvent écouter les différents cours afin de mieux les mémoriser en préparation de leurs examens. Des fiches de cours de différentes matières sont disponibles en podcasts ainsi qu’une préparation au grand oral avec de nombreux conseils pratiques.
Des vidéos de cours pour comprendre en image
Des vidéos de cours illustrent les notions principales à retenir et complètent les fiches de cours. De quoi réviser sa prochaine évaluation ou son prochain examen en toute confiance !
Fiches de cours les plus recherchées
NSI
Trier par insertion
NSI
Trier par sélection
NSI
Utiliser les invariants pour corriger un algorithme
NSI
Comprendre et utiliser l'algorithme des k plus proches voisins
NSI
L'algorithme de recherche dichotomique dans un tableau trié
NSI
Résoudre un problème avec un algorithme glouton
NSI
Écrire un entier positif dans une base donnée
NSI
Passer de la représentation d'une base à une autre
NSI
Comprendre les bases de la représentation binaire
NSI
Effectuer des opérations en binaire
NSI
Utiliser la méthode du complément à 2 en binaire
NSI
Représenter les nombres réels en binaire
NSI
Comprendre les booléens
NSI
Utiliser les opérateurs booléens élémentaires
NSI
Obtenir une table de vérité d'une expression booléenne complexe
NSI
Représenter un texte en utilisant différents encodages
Fermer
Accédez gratuitement à
