Parcours séquentiel d’un tableau

Notion de tableau

Source : https://fr.wikipedia.org/wiki/Tableau_(structure_de_données)

En informatique, un tableau est une structure de données représentant une séquence finie d'éléments auxquels on peut accéder efficacement par leur position, ou indice, dans la séquence. C'est un type de conteneur que l'on retrouve dans un grand nombre de langages de programmation. On parle aussi de tableau indexé.

Dans les langages à typage statique (comme C, Java et OCaml), tous les éléments d’un tableau doivent être du même type. Certains langages à typage dynamique (tels que Python) permettent des tableaux hétérogènes.

Tableaux en Python

En Python, les tableaux sont représentés grâce à des objets de type list. Une liste ressemble à un p-uplet : un ensemble ordonné d’éléments avec des indices pour les repérer.

D'un point de vue syntaxique, les éléments d’une liste sont séparés par des virgules et entourés de crochets :

Mais on peut également considérer que les chaînes de caractères sont des conteneurs de caractères.

On accède aux éléments de ces tableaux grâce à leur propriété d'itérateurs, par leur indice.

 

Tableaux en Javascript

Créer un tableau

Boucler sur un tableau

 

 

 


Pour la suite, nous utiliserons Python, et travaillerons sur une liste de nombres entiers générés aléatoirement :

Parcours et Itération

En Python, les listes, les chaînes de caractères, les tuples, et un grand nombre d'autres objets sont des itérateurs : il contiennent dans leur structure les méthodes permettant de les parcourir.

Par indice

On  peut parcourir un tableau en faisant évoluer un indice :

 

 

 

Par valeur

Les listes Python possèdent leur propre propriété d'itération, on peut donc directement itérer sur les valeurs :

 

 

Par indice et valeur

Il est parfois intéressant d'avoir à la fois l'indice et la valeur d'un élément de la liste :

 

 

 

Recherche d'une occurrence

Il s'agit de déterminer la position (l'indice) d'un élément e  prétendument présent dans la liste L . On parle d’occurrence de e  dans L .

Algorithme

Un "pointeur" i , initialisé à zéro, permet d'accéder aux éléments de la liste L . A chaque itération, on compare l'élément d'indice i  de la liste avec l'élément e  recherché. S'ils sont égaux, cela signifie que l'indice de e  dans L  vaut i et les itérations cessent, dans le cas contraire, on incrémente i  et on fait une nouvelle itération. Si l'élément e  n'est pas dans la liste L , le pointeur va jusqu'au bout de la liste, et finit par prendre la valeur de la longueur de la liste.

 

 

Implémentation en Python

Remarque : si i == len(L)  alors cela signifie que L  ne contient aucune occurrence de e .

Coût

Nous supposerons que chaque opération (affectation, comparaison, opération arithmétique, ...) a un coût de 1 "unité" de temps.

Si n  est la longueur de la liste L , on peut calculer la complexité ainsi :

Complexité : \(T(n)=2+7\times n=\mathcal{O}(n)\)

Coût linéaire !

 

Méthode Python

Renvoie l'indice de l'élément e  dans la liste L.

Attention :

  • si e  n'est pas dans L , .index()  provoque une erreur !
  • s'il y a plusieurs occurrences de e  dans L , seul l'indice de la première est renvoyé.

 

Recherche des extremums

Algorithme

Pour connaitre la valeur maximum des valeurs contenues dans la liste L , il faut évaluer tour à tour tous les éléments e  de L . La valeur maximum à une étape donnée est mémorisée dans une variable m , initialisée avec le premier élément de la liste L . Si l'élément e  est supérieur à m , m  prend alors la valeur de e.

 

 

Implémentation en Python

Activité
  • Implémenter en python une fonction maximum(L) .

Coût

Activité
  • Calculer l’ordre de complexité de cet algorithme.

Méthode Python

Il existe deux fonctions max()  et min()  permettant de déterminer les extrémums d'une liste.

 

Calcul de la moyenne

Algorithme

Pour calculer la moyenne des valeurs d'une liste, il faut calculer la somme de ces valeurs et diviser par le nombre de valeurs contenues dans la liste.

Pour calculer la somme on initialise une variable s  à zéro, et on itère sur l'ensemble des éléments e  de la liste. A chaque itération, on ajoute à s  la valeur de l'élément e .

 

Implémentation en Python

Activité
  • Implémenter en python une fonction somme(L) .

Coût

Activité
  • Calculer l’ordre de complexité de cet algorithme.

Méthode Python

La fonction sum() permet de calculer la somme des valeurs d'une liste.

Il suffit ensuite de diviser par la longueur de la liste len(L) .

 

Sources : cours sur la complexité algorithmique : https://www.supinfo.com/cours/2ADS/chapitres/01-notion-complexite-algorithmique


Exercices

  • Écrire une fonction compter() permettant de compter le nombre d’occurrences d'une lettre dans une chaîne de caractères.
    compter("Numérique et Sciences Informatiques !", 'm') doit renvoyer 2.
  • Écrire une fonction compter_pos() permettant de compter le nombre d’occurrences d'une lettre dans une chaîne de caractères et de donner leurs positions.
    compter("Numérique et Sciences Informatiques !", 'm') doit renvoyer 2, [2, 27].
  • Écrire une fonction compter_tout() permettant d'obtenir les nombres d’occurrences de toutes les lettres d'une chaîne de caractères, sous la forme d'un dictionnaire {lettre:nbr_occurences} .
    compter_tout("Numérique et Sciences Informatiques !") doit renvoyer :
    {'N': 1, 'u': 3, 'm': 2, 'é': 1, 'r': 2, 'i': 3, 'q': 2, 'e': 5, ' ': 4, 't': 2, 'S': 1, 'c': 2, 'n': 2, 's': 2, 'I': 1, 'f': 1, 'o': 1, 'a': 1, '!': 1} 
  • Écrire une fonction separer()  permettant, à partir d'une liste de nombres, d'obtenir deux listes. La première comporte les nombres inférieurs ou égaux à un nombre donné, la seconde les nombre qui lui sont strictement supérieurs.
    separer([45, 21, 56 ,12, 1, 8, 30, 22, 6, 33], 30)  doit renvoyer :
    [21, 12, 1, 8, 30, 22, 6], [45, 56, 33] 
  • Écrire une fonction plus_proche()  permettant de rechercher la plus proche valeur d'un nombre dans une liste.
    plus_proche([45, 21, 56 ,12, 1, 8, 30, 22, 6, 33], 20)  doit renvoyer 21
  • Écrire une fonction plus_proche_i()  permettant de rechercher la plus proche valeur d'un nombre dans une liste et son indice dans la liste.
    plus_proche_i([45, 21, 56 ,12, 1, 8, 30, 22, 6, 33], 20)  doit renvoyer 1, 21
Afin de ne pas tenir compte de la casse (lettre majuscules ou minuscules), on pourra utiliser la méthode .lower()  ... à tester !
  • Écrire une fonction lex_avant(mot1, mot2)  permettant de déterminer si le mot1  est classé avant le mot2  dans l'ordre lexicographique (celui du dictionnaire).
    lex_avant('Information', 'informatique') doit renvoyer True .

 

 

Vous aimerez aussi...

Laisser un commentaire

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

*

code