Parcours séquentiel d'un tableau

Numérique et sciences informatiques

algorithme

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.
Un parcours séquentiel est un accès individuel aux éléments d'une structure donnée en les parcourant un par un et dans l'ordre.

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.

tableau_entier = [19,4,9,10,6,2]
tableau_chaine = "Faustin Fleret"

Entraînement 1 :

Trouver et vérifier ce qu'affiche tableau_entier[2], tableau_entier[4],tableau_chaine[1], tableau_chaine[5]

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.

liste = [45, 21, 56 ,12, 1, 8, 30, 22, 6, 33]
chaine = "NSI Power !"
for element in liste:
   print(element)
   
for element in chaine:
    print(element)
   
for index in range (len(liste)):
    print(liste[index])
    
for index, element in enumerate(chaine):
   print(index, element)

Entraînement 2 :

Trouver l'utilité de la fonction python liste.index(element)

liste = [76, 19, 56 ,12, 19, 9, 13, 22, 6, 33]
chaine = "NSI Power !"
print(liste.index(19))
print(liste.index(12))
print(chaine.index("S"))
print(chaine.index("s"))

Notion de tri

Un algorithme de tri est, en informatique ou en mathématiques, un algorithme qui permet d’organiser une collection d’objets selon une relation d’ordre déterminée. Les objets à trier sont des éléments d’un même type.
Classiquement on tri :

booléens
Des nombres selon la relation d’ordre usuelle « est inférieur ou égal à » ("<=" en python).
booléens
Des mots à l’aide de l’ordre lexicographique (alphabet).
En python l’opérateur logique "<=" marche avec les nombres et les chaînes de caractère. "<=" utilise le code ASCII pour les str. Il faudra donc faire attention à ce que les chaînes de caractère s’écrivent uniquement en majuscule ou uniquement en minuscule.

Entraînement 3 :

Dans la console python, vérifier et comprendre les tris suivants :

# Dans la console Python
>>> 4<=19
>>> "mac"<="win"
>>>"mAc"<="WIN"
>>>"mAc".lower()<="WIN".lower()
>>>"mAc".capitalize()<="WIN".capitalize()

Est trié ?

Entraînement 4 :

Programmer la fonction est_trie qui prend en paramètre un tableau de valeurs numériques et qui renvoie True si ce tableau est trié dans l'ordre croissant, False sinon.

def est_trie(tab):
# tests

assert est_trie([0, 5, 8, 8, 9])
assert not est_trie([8, 12, 4])
assert est_trie([-1, 4])
assert est_trie([5])
assert est_trie([])
Aide 1

Indice première occurrence :

Entraînement 5 :

Compléter la fonction indice qui prend en paramètres element un nombre entier et tableau une suite de nombres entiers de type list, et qui renvoie l'indice de la première occurrence de element dans tableau. La fonction devra renvoyer -1 si element est absent de tableau.

def indice(element, tableau):
    for i in range( ... ):
        if ... :
            return i        
    return ...

# tests
assert indice(1, [10, 12, 1, 56]) == 2
assert indice(1, [1, 50, 1]) == 0
assert indice(15, [8, 9, 10, 15]) == 3
assert indice(1, [2, 3, 4]) == -1

Recherche du maximum d'une liste :

Entraînement 6 :

Compléter la fonction valeur_et_indice_du_max qui prend en paramètre une liste de nombres entiers valeurs et renvoie un couple donnant le plus grand élément de cette liste, ainsi que l'indice de la première apparition de ce maximum dans la liste. Pour une liste vide, la fonction renvoie (None, None)

def valeur_et_indice_du_max(valeurs):
    if ... :
    	return (None,None)
    val_max = ...
    pos_max = ...
    for i in range( ... ) :
        if ... :
            val_max = ...
            pos_max = ...
    return (val_max, pos_max)


# tests
assert valeur_et_indice_du_max([1, 5, 6, 9, 1, 2, 3, 7, 9, 8]) == (9, 3)
assert valeur_et_indice_du_max([1, 1, 1, 99, 99]) == (99, 3)
assert valeur_et_indice_du_max([10]) == (10, 0)
assert valeur_et_indice_du_max([]) == (None, None)
Aide 1

Aide 2

Calcul de la moyenne d'une liste :

Entraînement 7 :

Écrire une fonction moyenne prenant en paramètre un tableau non vide d'entiers et qui renvoie la moyenne des valeurs du tableau.

>>> moyenne([10, 20, 30, 40, 60, 110])
45.0
>>> moyenne([1, 3])
2.0
>>> moyenne([44, 51, 12, 72, 65, 34])
46.333333333333336
Aide 1

Aide 2

Occurrences d'un caractère dans un mot :

Entraînement 8 :

Écrire une fonction compte_occurrences qui prend en paramètres caractere, un caractère (une chaîne de caractères de longueur 1), et mot, une chaîne de caractères, et qui renvoie le nombre d'occurrences de caractere dans mot, c'est-à-dire le nombre de fois où caractere apparaît dans mot.

def compte_occurrences(caractere, mot):
    ...


# tests
assert compte_occurrences("e", "sciences") == 2
assert compte_occurrences("i", "Mississippi") == 4
assert compte_occurrences("a", "Mississippi") == 0

Dernière occurrence :

Entraînement 9 :

Programmer la fonction derniere_occurrence, prenant en paramètre un tableau non vide d'entiers et un entier cible, et qui renvoie l'indice de la dernière occurrence de cible. Si l'élément n'est pas présent, la fonction renvoie -1.

def derniere_occurrence(tab,elt):
# tests

assert derniere_occurrence([5, 3], 1) == -
assert derniere_occurrence([2, 4], 2) == 0
assert derniere_occurrence([2, 3, 5, 2, 4], 2) == 3
											

Recherche des positions d'un élément dans un tableau :

Entraînement 10 :

Écrire une fonction recherche_positions qui prend en paramètres element un nombre et tableau un tableau de nombres, et qui renvoie la liste croissante des indices de element dans tableau et la liste vide [] si element n'apparaît pas dans tableau.

*
>>> recherche_positions(3, [3, 2, 1, 3, 2, 1])
[0, 3]
>>> recherche_positions(4, [1, 2, 3])
[]
>>> recherche_positions(10, [2, 10, 3, 10, 4, 10, 5])
[1, 3, 5]