3 - Parcours séquentiel d'un tableau

⏪

⏬

⏩

1 - Algorithmique

2 - recherche

3 - Python

4 - Exemples

5 - Autres structs

6 - FAQ

7 -

Nous allons aujourd'hui comment localiser la position d'un élément dans un tableau.

Cela s'appelle une recherche.

Documents de cours : open document ou pdf

MODE COURS (cacher les questions)

1 - Importance de l'algorithmique

⇩ ⇧ ⤊

Quelques rappels :

(Rappel) A - Algorithme : une définition ?

Voir

Définition ALGORITHME : un algorithme est un ensemble fini (au sens "pas infini") d'instructions précises permettant de résoudre une classe de problèmes. L'algorithme doit être écrit sans ambiguïté, et être facilement transposable dans n'importe quel langage de programmation.

Le mot classe est ici important : on doit pouvoir résoudre un type de problèmes et pas un cas unique. Si l'algorithme ne fonctionne que pour UN cas particulier, on ne parlera pas d'algorithme.

De façon plus schématique, un algorithme reçoit des données en ENTREE, effectue des calculs sur ces données et produit une valeur de SORTIE.

ENTREE(S) → Algorithme → SORTIE

Comme vous pouvez le voir, cela ressemble fort à ce qu'on pourrait définir comme une fonction. Ce n'est pas un hasard, nous le verrons en Terminale.

Gérard Berry parle des algorithmes comme étant des méthodes à appliquer sans réflechir, en suivant machinalement le déroulement et les ordres.

On sépare réflexion et exécution.

La réflexion est utilisée par l'informaticien ou l'informaticienne lors de l'élaboration de l'algorithme.

Lors du déroulement de l'algorithme, l'ordinateur exécute. Point.

En réalité, cette définition est floue. Elle comporte beaucoup de non-dits. Nous verrons une définition plus formelle en Terminale.

(Rappel) B - Algorithmique

Voir

L'algorithmique consiste à étudier des problèmes en vue de les résoudre à l'aide d'un algorithme le plus efficace possible.

On cherche donc :

à estimer la rapidité d'exécution de l'algorithme.

Cela revient à connaître le coût de l'algorithme.

à vérifier que la réponse éventuelle soit juste.

Cette vérification se nomme la preuve de correction.

à vérifier qu'il s'arrête bien sur n'importe quelle entrée fournie.

Cette vérification se nomme la preuve de terminaison.

(Rappel) C - Bilan des coûts

Voir

Problème facile

Facile en informatique : peut répondre en un temps raisonnable.

Le coût constant (noté 1)
Le coût logarithmique (noté log n)
Le coût polynomial (noté n^k)

Problème difficile

Difficile en informatique : temps de calcul déraisonnable.

Le coût exponentiel (noté kⁿ) : avec un tel coût, on estime que l'algorithme n'est pas exploitable à grande échelle. Il va mettre trop de temps pour répondre.
Le coût factoriel (noté n!) : encore moins exploitable.

(Rappel) D - Unités courantes : k M G T

Voir

Sous-unité	Valeur en décimal	Pourquoi ?
Un kilo (k) représente 10³	1 000
Un Méga (M) représente 10⁶	1 000 000	un million, soit 1000 x 1 000
Un Giga (G) représente 10⁹	1 000 000 000	un milliard, soit 1000 x 1 000 000
Un Téra (T) représente 10¹²	1 000 000 000 000	mille milliards, soit 1000 x 1 000 000 000

On voit donc que chaque sous-unité représente 1000 fois plus que la précédente.

Passons à la nouveauté :

1.1 Algorithme implémenté sous forme de fonction

Voir

Implémentation

L'implémentation est le nom qu'on donne au passage de :

l'idée abstraite de l'algorithme (sur papier) à
son exécution concrète à l'aide d'un programme (en machine)

Or, vous connaissez déjà un objet informatique qui accepte des valeurs en entrée et qui renvoie une réponse en sortie : les fonctions.

	⇒	algo MAXIMUM	⇒
[5, 10, 50, 0, 20]				50

	⇒	fonction maximum()	⇒
[5, 10, 50, 0, 20]				50

Exemple

L'algorithme du MAXIMUM est ainsi déjà implémenté en Python à travers la fonction native max() :


>>> max([5, 10, 50, 0, 20])
50

Conclusion

On implémentera les algorithmes sous forme de fonctions :

Les ENTREES : les paramètres de la fonction
SORTIE : le retour de la fonction

Pourquoi est-il important d'optimiser les algorithmes alors que les machines actuelles sont très puissantes ?

A cause de l'augmentation énorme du volume de données à traiter : un algorithme ne pourra être implémenté en machine que s'il répond en un temps acceptable.

Vous êtes chef de service. On vous propose de choisir entre

Investir dans un équipement informatique Tip Top ou
Investir dans le salaire d'un.e nouvel.le informaticien.ne Tip Top. Quelqu'un qui a pris NSI dès la 1er. Si si.

Alors ? Votre choix ?

Imaginons qu'on veuille identifier quelqu'un dans une base de données comportant n fiches.

Cas 1

INFORMATICIEN NORMAL : l'algorithme créé par l'informaticien a besoin de n³ opérations pour identifier la personne dans la base de données qui comporte n fiches.
ORDINATEUR TIP-TOP : l'ordinateur est capable de faire 200 Giga comparaisons par seconde.

On peut en déduire le temps mis par l'ordinateur pour identifier les personnes en fonction de la taille de la base de données :

t = (n³) / (200.10⁹)

En Python :

t = n**3 / 200E9

Intro-1° Calculer les temps mis pour réaliser cette tâche si la base de données possède

5000 fiches (n = 5.10³),
5 millions de fiches (n = 5.10⁶),
5 milliards de fiches (n = 5.10⁹).

Correction ?

...CORRECTION...

Pour n = 5000 fiches :

t = (5E3)**3 / 200E9 = 0,625 s

Pour n = 5 millions de fiches :

t = (5E6)**3 / 200E9 = 625000000 s
t = (5E6)**3 / (200E9*3600*24*365) = 19.8 ans

Pour n = 5 milliards de fiches :

t = (5E9)**3 / 200E9 = 6,25.10¹⁷ s
t = (5E9)**3 / (200E9*3600*24*365) = 19 818 619 990 ans !

Cas 2

INFORMATICIEN TIP-TOP : l'algorithme créé par l'informaticien a besoin de n² comparaisons pour identifier la personne dans la base de données qui comporte n fiches.
ORDINATEUR MEDIOCRE : l'ordinateur est capable de faire 30 Mega comparaisons par seconde...

On peut en déduire le temps mis par l'ordinateur pour identifier les personnes en fonction de la taille de la base de données :

t = (n²) / (30.10⁶)

En Python :

t = n**2 / 30E6

Intro-2° Calculer les temps mis pour réaliser cette tâche si la base de données possède

5000 fiches (5.10³),
5 millions de fiches (5.10⁶),
5 milliards de fiches (5.10⁹).

Correction ?

...CORRECTION...

Pour 5000 fiches :

t = (5E3)**2 / 30E6 = 0,83 s

Pour 5 millions de fiches :

t = (5E6)**2 / 30E6 = 833333 s
t = (5E6)**2 / (30E6*3600*24) = 9.6 jours

Pour 5 milliards de fiches :

t = (5E9)**2 / 30E6 = 833333333333 s
t = (5E9)**2 / (30E6*3600*24*365) = 26 424 ans !

Un ordinateur ultra performant n'a en réalité aucun chance face à un ordinateur moins performant muni d'un programme plus efficace.

L'aspect logiciel et algorithmique est finalement plus fondamental que l'aspect matériel.

Voici un script Python permettant de générer les courbes ci-dessus.

SCRIPT PYTHON

...PYTHON...

# 1 - Importation des modules nécessaires
import math
import matplotlib.pyplot as plt
 
# 2 - Constantes
 
# 3 - Déclaration des fonctions
 
# 4 - Programme principal
 
# Création des tableaux de données
valeurs_n = [ n for n in range(10000) ]  # Abscisse
temps_1 = [ n**3 /200E9 for n in valeurs_n ] # Ordonnée
temps_2 = [ n**2 /30E6 for n in valeurs_n ] # Ordonnée
 
xmax = max(valeurs_n )
ymax = max(temps_1 )
 
# Création des courbes
plt.plot(valeurs_n, temps_1, label="Cas 1", color='orange')
plt.plot(valeurs_n, temps_2, label="Cas 2", color="red")
plt.xlabel("Nbr de fiches")
plt.ylabel("Temps d'exécution (s)")
plt.title("Comparaison des temps d'exécution")
plt.legend(loc='upper center')
plt.axis([0, xmax, 0, ymax])
plt.grid()
plt.show() # Affichage à l'écran des courbes

Et ça date de quand l'algorithmique ? Des années 2000 ? Des années 1940 ?

1.2 Historique rapide

Voir

Certains pensent que l'un des algorithmes les plus anciens est l'algorithme d'Euclide. Cet algorithme permet de trouver le plus grand commun diviseur (PGCD) de deux entiers a et b.

Par exemple, pour a = 15 et b = 20, il s'agit de 5.

En effet,

15 peut se décomposer en 3*5 et
20 peut se décomposer en 4*5.

Un algorithme efficace permettant de trouver automatiquement ce PGCD date de -300 et se trouve dans les écrits du mathématicien Euclide d'Alexandrie. Il a été découvert de façon autonome en Inde et en Chine quelques siècles plus tard.

Vers 800, Muhammad Ibn Mūsā al-Khuwārizmī dit Al-Khwarizmi, mathématicien, né dans dans l'actuel Ouzbékistan et mort à Badgad, publie de nombreux textes. Les traductions permettront l'introduction de l'algèbre en Europe. Il a notamment répertorié et classifié de nombreux algorithmes (créés par d'autres). Il y montre leurs terminaisons (le fait qu'ils s'arrêtent bien à tous les coups) ou pas.

Son nom est bien entendu à l'origine d'algorithme.

Depuis, bien des gens ont travaillé et travaillent toujours pour trouver, créer ou améliorer les algorithmes.

L'un des grands noms de l'algorithmique est Donald Knuth, informaticien et mathématicien américain de renom. Il est un des pionniers de l'algorithmique et a fait de nombreuses contributions dans plusieurs branches de l'informatique théorique (fondements logiques et mathématiques de l'informatique). A tel point, qu'on le nomme parfois le père de l'analyse algorithmique.

https://fr.wikipedia.org/wiki/Donald_Knuth#/media/Fichier:KnuthAtOpenContentAlliance.jpg — Donald Knuth - CC BY-SA 2.5

Pour en savoir plus sur son oeuvre

The Art of Computer Programming

2 - Recherche d'un élément dans un tableau

⇩ ⇧ ⤊

Nous allons maintenant tenter de réaliser un algorithme qui signale si un élément existe dans un tableau (et renvoie son indice) ou renvoie -1 sinon.

Cette méthode se nomme méthode par balayage ou recherche linéaire.

En anglais, on parle de linear search.

Vous allez comprendre pourquoi en utilisant l'animation suivante : créer un tableau avec l'un des boutons aléatoires, choisir une valeur à chercher et appuyer sur le bouton lançant l'animation.

Valeur cherchée :


Indice i	00	01	02	03	04	05	06	07	08	09	10	11	12	13	14	15	16	17	18	19
Case t[i]	60	89	15	56	82	1	86	97	24	86	75	6	14	69	98	31	37	89	91	56

2.1 Principe de la recherche linéaire

Voir

Principe général

BUT : trouver la position de la première occurrence de l'élément x recherché dans un tableau t.

PRINCIPE (en 4 étapes) :

On commence par la case d'indice 0
TANT QUE la case est valide ET ne contient pas le contenu cherché, on passe à la case suivante
SI la valeur finale de l'indice est valide : la réponse est bien l'indice. SINON, la réponse est -1 car on a atteint la fin du tableau sans trouver.
On RENVOIE la réponse

Exemples

Prenons t = [13, 18, 89, 1024, 45, -12, 18]

Indice i	0	1	2	3	4	5	6
Case t[i]	13	18	89	1024	45	-12	18

Voici trois exemples de réponses attendues :

Recherche de 89 (présent une fois) :

t = [13, 18, 89, 1024, 45, -12, 18]	⇒	RECHERCHER	⇒
et				2
x = 89

Recherche de 18 (présent deux fois) :

t = [13, 18, 89, 1024, 45, -12, 18]	⇒	RECHERCHER	⇒
et				1
x = 18

Recherche de 100 (non présent) :

t = [13, 18, 89, 1024, 45, -12, 18]	⇒	RECHERCHER	⇒
et				-1
x = 100

2.2 Algorithme de la recherche linéaire

Voir

Description des entrées/sortie

NOM : RECHERCHE_LINEAIRE
ENTREES :

t : un tableau contenant n éléments.
x : l'élément qu'on recherche dans le tableau

SORTIE : un entier valant

soit l'indice où se trouve la première (et peut-être) seule occurrence de l'élément cherché.
une réponse (VIDE ou -1) voulant dire que l'élément x n'est pas présent dans le tableau.

Description de l'algorithme

Avec une réponse -1 en cas de valeur non trouvée.

i ← 0

TANT QUE i < longueur du tableau ET que t[i] est différent de x

i ← i + 1

Fin TANT QUE

SI i < longueur

reponse ← i

SINON

reponse ← -1

Fin Si

Renvoyer reponse

01° Utiliser les instructions suivantes pour revoir comment fonctionne un tableau :


>>> t = [5, 10, 7]
>>> len(t)
???
 
>>> t[0]
???
 
>>> t[1]
???
 
>>> t[2]
???
 
>>> t[3]
???

Correction ?

...CORRECTION...


>>> t = [5, 10, 7]
>>> len(t)
3
 
>>> t[0]
5
 
>>> t[1]
10
 
>>> t[2]
7
 
>>> t[3]
ElémentError: list index out of range

FONDAMENTAL POUR COMPRENDRE LA SUITE

On rappelle une évidence super-importante :

i veut dire : l'indice, le numéro de la case
t[i] veut dire : le contenu de la case i du tableau t

02 ✎° Quel est le seul cas où un ET logique a ET b répond VRAI ?

Correction ?

...CORRECTION...

Un ET logique est VRAI si et seulement si toutes les conditions sont évaluées à VRAI.

Donc, dès qu'une condition est fausse, le ET est évalué à FAUX.

03 ✎° Voici la ligne du TANT QUE :

TANT QUE i < longueur du tableau ET que t[i] est différent de x

Question 1 : trouver à quelle phrase correspond le mieux la condition i < longueur du tableau :

"Cette case existe" ?
"Cette case est assez petite" ?
"La longueur de la case est plus petite que la longueur du tableau" ?
"La case i ne contient pas la valeur qu'on recherche".

Question 2 : trouver à quelle phrase correspond le mieux la condition t[i] est différent de x :

"Cette valeur x qu'on recherche n'existe pas" ?
"Le tableau est différent de x qu'on recherche" ?
"L'indice i est différent de x qu'on recherche" ?
"Le contenu de la case i est différent de la valeur x qu'on recherche".

Correction ?

...CORRECTION...

Question 1 : trouver à quelle phrase correspond le mieux la condition i < longueur du tableau :

"Cette case existe"

Question 2 : trouver à quelle phrase correspond le mieux la condition t[i] est différent de x :

"Le contenu de la case i est différent de la valeur x qu'on recherche".

04 ✎° Deux questions.

Question 1 : Ecrire le déroulé de l'algorithme s’il travaille sur le tableau ci-dessous en recherchant 1024. Vous devriez trouver qu'il renvoie 3.

t ← [13, 18, 89, 1024, 45, -12, 18]

Voici le début d'une rédaction possible (avec en gris des indications supplémentaires qu'il est inutile de marquer sur votre feuille de cours) :

i = 0.

longueur = 7 car le tableau a 7 cases numérotées de 0 à 6.

x = 1024 car c'est ce qu'on cherche.

Boucle TQ ? Oui car 0 < 7 et t[0] ≠ 1024. Après le tour : i = 1

Boucle TQ ? Oui car 1 < 7 et t[1] ≠ 1024. Après le tour : ...

Question 2 : Quelle est la condition évaluée à FAUX qui a provoqué l'arrêt du TANT QUE :

la valeur de la variable indice i devenue trop grande ou
le contenu de la case i qui correspond à la valeur voulue ?

Correction ?

...CORRECTION...

t = [13, 18, 89, 1024, 45, -12, 18]

i = 0.

longueur = 7 car le tableau a 7 cases numérotées de 0 à 6.

x = 1024 car c'est ce qu'on cherche.

Boucle TQ ? Oui car 0 < 7 et t[0] ≠ 1024. Après le tour : i = 1

Boucle TQ ? Oui car 1 < 7 et t[1] ≠ 1024. Après le tour : i = 2

Boucle TQ ? Non car t[2] = 1024. On stoppe la boucle.

Ici, on s'arrête donc puisqu'on a trouvé la valeur 1024 voulue dans le tableau.

05 ✎° Appliquer l'algorithme à la main avec une recherche sur 1025. Vous devriez trouver qu'il renvoie -1.

Quelle est la condition évaluée à FAUX qui a provoqué l'arrêt du TANT QUE ?

Correction ?

...CORRECTION...

t = [13, 18, 89, 1024, 45, -12, 18]

i = 0.

longueur = 7 car le tableau a 7 cases numérotées de 0 à 6.

x = 1024 car c'est ce qu'on cherche.

Boucle TQ ? Oui car 0 < 7 et t[0] ≠ 1025. Après le tour : i = 1

Boucle TQ ? Oui car 1 < 7 et t[1] ≠ 1025. Après le tour : i = 2

Boucle TQ ? Oui car 2 < 7 et t[2] ≠ 1025. Après le tour : i = 3

Boucle TQ ? Oui car 3 < 7 et t[3] ≠ 1025. Après le tour : i = 4

Boucle TQ ? Oui car 4 < 7 et t[4] ≠ 1025. Après le tour : i = 5

Boucle TQ ? Oui car 5 < 7 et t[5] ≠ 1025. Après le tour : i = 6

Boucle TQ ? Oui car 6 < 7 et t[6] ≠ 1025. Après le tour : i = 7

Boucle TQ ? Non car 7 n'est pas strictement inférieur à 7. On stoppe la boucle.

Ici, on s'arrête donc puisqu'on a atteint une valeur impossible pour l'indice.

06 ✎° 18 apparaît deux fois dans le tableau. La valeur renvoyée par cet algorithme sur une recherche de la première occurrence sur 18 donne :

A : 0
B : 1
C : 6
D : (1,6)

Rappel du contenu

Indice i	0	1	2	3	4	5	6
Case t[i]	13	18	89	1024	45	-12	18

Correction ?

...CORRECTION...

On lit le contenu progressivement de façon séquentielle.

En lisant l'algorithme, on voit qu'on renvoie la première occurrence trouvée, soit 1.

3 - Implémentation Python

⇩ ⇧ ⤊

07 ✎° Compléter la fonction Python rechercher() fournie pour qu'elle fasse correctement le travail demandé.

def rechercher(t:list, x:'Element') -> int:
    """Renvoie l'indice de la première occurrence de x dans t, -1 si non présent"""
     
    i = ...  
    while i < ... and ...:
        i = ...
     
    if i < ...:
        reponse = ...
    else:
        reponse = ...
    return ...
 
tab_test = [13, 18, 89, 1024, 45, -12, 18]
a = rechercher(tab_test, 18)
b = rechercher(tab_test, 1024)
c = rechercher(tab_test, 1025)

Correction ?

...CORRECTION...

def rechercher(t:list, x:'Element') -> int:
    """Renvoie l'indice de la première occurrence de x dans t, -1 si non présent"""
     
    i = 0
    while i < len(t) and t[i] != x:
        i = i + 1
     
    if i < len(t):
        reponse = i
    else:
        reponse = -1
    return reponse
 
tab_test = [13, 18, 89, 1024, 45, -12, 18]
a = rechercher(tab_test, 18)
b = rechercher(tab_test, 1024)
c = rechercher(tab_test, 1025)

08 ✎° Vider maintenant la fonction Python rechercher() et refaire cette implémentation à partir d'une fonction vide.

Le prototype de la fonction :

`1`	`def rechercher(t:list, x:'Element') -> int:`

def rechercher(t:list, x:'Element') -> int:
    """Renvoie l'indice de la première occurrence de x dans t, -1 si non présent"""
     
    pass
 
tab_test = [13, 18, 89, 1024, 45, -12, 18]
a = rechercher(tab_test, 18)
b = rechercher(tab_test, 1024)
c = rechercher(tab_test, 1025)

Comme vous pouvez le voir, sous la fonction à réaliser, on a rajouté des instructions pour créer un tableau et mémoriser quelques appels dans des variables. Vous pourrez visualiser le résultat pour voir si votre fonction répond correctement.

Réaliser la fonction en ne travaillant que sur les paramètres nommées t et x qui contiennent ce qu'il faut pour gérer ce problème : utilisez bien la notion de variables contenant les informations reçues en entrée.

Correction ?

...CORRECTION...

def rechercher(t:list, x:'Element') -> int:
    """Renvoie l'indice de la première occurrence de x dans t, -1 si non présent"""
     
    i = 0
    while i < len(t) and t[i] != x:
        i = i + 1
     
    if i < len(t):
        reponse = i
    else:
        reponse = -1
    return reponse
 
tab_test = [13, 18, 89, 1024, 45, -12, 18]
a = rechercher(tab_test, 18)
b = rechercher(tab_test, 1024)
c = rechercher(tab_test, 1025)

09 ✎° Rajouter un commentaire derrière chaque instruction pour traduire en français le rôle de cette ligne.

Correction ?

...CORRECTION...

def rechercher(t:list, x:'Elément') -> int:
    """Renvoie l'indice de la première occurrence de x dans t, -1 si non présent"""
     
    i = 0                            # On se place sur la première case
    while i < len(t) and t[i] != x:  # Tant qu'il reste des cases et que la case actuelle n'est pas la bonne
        i = i + 1                    # On passe à la case suivante
     
    if i < len(t):                   # Si i est une valeur possible pour ce tableau
        reponse = i
    else:                            # Sinon, c'est qu'on est sorti du tableau
        reponse = -1
    return reponse                   # Renvoie la réponse

RAPPEL : phase d'initialisation du TANT QUE

Attention à l'une des erreurs typiques lors de l'utilisation d'une boucle non bornée TANT QUE : le fait d'oublier de donner une valeur par défaut permettant de rentrer dans la boucle à la variable qui gère la boucle.

10 ✎ °Supprimer temporairement la ligne où on déclare i en y plaçant 0. Lancer le programme : vous devriez voir que Python ne parvient plus à démarrer : il ne peut pas choisir seul de placer 0 dans i lorsqu'on utilise le TANT QUE.

11° Réaliser une modification de rechercher() en utilisant plutôt une boucle for associée à un return : dès qu'on connaît la réponse, on répond. On ne renvoie -1 qu'après avoir effectué toute la boucle : si on arrive sur cette dernière ligne, c'est que l'élément x voulu n'a jamais été rencontré.

def rechercher(t, x):
    """Renvoie l'indice de la première occurrence de x dans t, -1 si non présent
 
    for i in range( ... ):
        if ... == ...:
            return ...
    return ...
 
tab_test = [13, 18, 89, 1024, 45, -12, 18]
a = rechercher(tab_test, 18)
b = rechercher(tab_test, 1024)
c = rechercher(tab_test, 1025)

Correction ?

...CORRECTION...

def rechercher(t, x):
    """Renvoie l'indice de la première occurrence de x dans t, -1 si non présent
 
    for i in range( len(t) ):
        if t[i] == x:
            return i
    return -1
 
tab_test = [13, 18, 89, 1024, 45, -12, 18]
a = rechercher(tab_test, 18)
b = rechercher(tab_test, 1024)
c = rechercher(tab_test, 1025)

12° Au niveau algorithmique, quelle est la version la plus rigoureuse : celle avec le while ou celle avec for+return ?

Correction ?

...CORRECTION...

Sur le principe de la recherche, on doit interrompre la recherche dès qu'on trouve le bon élément. Il s'agit donc d'une boucle non bornée.

Donc, le while est le plus adapté.

13° Au niveau programmation, quelle est la version la plus lisible : celle avec le while ou celle avec for+return ?

Correction ?

...CORRECTION...

Cette fois, la version avec le for est plus lisible : pas besoin de noter l'initialisation, l'incrémentation et de tester s'il reste encore une case ou non.

14 (difficile)° : fournir une fonction de recherche un peu différent : cette fois, on veut renvoyer l'indice de la dernière occurrence dans le tableau.

Recherche de 18 (présent deux fois) :

t = [13, 18, 89, 1024, 45, -12, 18]	⇒	RECHERCHER	⇒
et				6
x = 18

Il faudra vous demander s'il faut utiliser une boucle bornée ou non bornée, comment parvenir à stocker les réponses successives...

Il a plusieurs façons de faire cela.

Correction ?

...CORRECTION...

def rechercher(t, x):
    """Renvoie l'indice de la dernière occurrence de x dans t, -1 si non présent
 
    reponse = -1
    for i in range( len(t) ):
        if t[i] == x:
            reponse = i
    return reponse
 
tab_test = [13, 18, 89, 1024, 45, -12, 18]
a = rechercher(tab_test, 18)
b = rechercher(tab_test, 1024)
c = rechercher(tab_test, 1025)

def rechercher(t, x):
    """Renvoie l'indice de la dernière occurrence de x dans t, -1 si non présent
 
    for i in range( len(t)-1,-1, -1):
        if t[i] == x:
            return i
    return -1
 
tab_test = [13, 18, 89, 1024, 45, -12, 18]
a = rechercher(tab_test, 18)
b = rechercher(tab_test, 1024)
c = rechercher(tab_test, 1025)

def rechercher(t:list, x:'Elément') -> int:
    """Renvoie l'indice de la dernière occurrence de x dans t, -1 si non présent"""
     
    i = len(t) - 1               # On se place sur la dernière case
    while i >= 0 and t[i] != x:  # Tant qu'il reste des cases et que la case actuelle n'est pas la bonne
        i = i - 1                # On passe à la case précédente
     
    if i < len(t):               # Si i est une valeur possible pour ce tableau
        reponse = i
    else:                        # Sinon, c'est qu'on est sorti du tableau
        reponse = -1
    return reponse               # Renvoie la réponse

4 - Exemples de recherche

⇩ ⇧ ⤊

Cette partie nécessite d'avoir fait l'activité Python Boucle et types construits et d'y avoir rencontré la création par compréhension.

14° Utiliser le programme ci-dessous. Il génére PAR COMPREHENSION un tableau t de n nombres compris entre 10 et 20, génère un nombre x au hasard puis utilise la fonction rechercher(). On affiche le résultat obtenu.

Lancer 5 fois le programme et vérifier qu'il donne la bonne réponse à chaque fois.

import random
 
def rechercher(t:list, x:int) -> int:
    """Renvoie l'indice de la première occurrence de x dans t, -1 si non présent"""
     
    i = 0                            # On se place sur la première case
    while i < len(t) and t[i] != x:  # Tant qu'il reste des cases et que la case actuelle n'est pas la bonne
        i = i + 1                    # On passe à la case suivante
     
    if i < len(t):                   # Si i obtenu est une valeur possible pour ce tableau
        reponse = i
    else:                            # Sinon, c'est qu'on est sorti du tableau
        reponse = -1
    return reponse                   # Renvoie la réponse
 
n = random.randint(5, 10)                      # nombre de cases entre 5 et 10
t = [random.randint(1, 20) for x in range(n)]  # le tableau de cases aléatoires
x = random.randint(0, 30)                      # génération du nombre qu'on cherche
indice = rechercher(t, x)                      # récupération de l'indice 
print(t)  
print(f"On cherche {x} : réponse {indice}")   

Malheureusement, tester (même 1 million de fois) ne permet pas d'être certain que la réponse est bonne.

15° Même si nous savons que vérifier ne veut pas dire démontrer, ce programme va vous permettre de lancer en boucle autant de tests que vous le désirez. Si l'un d'entre eux est faux, le programme doit stopper immédiatement.

Comment procéder ?

Si c'est -1, on vérifie que l'élément n'appartient pas au tableau
Si on récupère un indice valide, il faudra tester deux choses :

l'élément se trouve bien à cette position i et
aucun indice plus petit ne contient cet élément.

Tâches à accomplir :

Placer ce nouveau programme en mémoire
Lire le prototype de la fonction pour comprendre ce que doit faire cette fonction
Compléter la fonction ("code à trou")
Tester que votre fonction semble bien fonctionner

import random
 
def rechercher(t:list, x:int) -> int:
    """Renvoie l'indice de la première occurrence de x dans t, -1 si non présent"""
     
    i = 0                              # On se place sur la première case
     while i < len(t) and t[i] != x:  # Tant qu'il reste des cases et que la case actuelle n'est pas la bonne
        i = i + 1                      # On passe à la case suivante
     
    if i < len(t):                   # Si i obtenu est une valeur possible pour ce tableau
        reponse = i
    else:                              # Sinon, c'est qu'on est sorti du tableau
        reponse = -1
    return reponse                     # Renvoie la réponse
 
def tester():
    for k in range(1000):
        n = random.randint(3, 10)
        t = [random.randint(10, 20) for x in range(n)]
        x = random.randint(8, 22)
        indice = rechercher(t, x)
        print(f"Test {k+1}")
        if indice == ... and ... in ...:  # Si on a -1 alors que x est présent
            print("ECHEC DU TEST")
            print(t)  
            print(f"On cherche {x} : réponse {indice}")            
            return ...
        else:
            for i in range(0, indice):  # Pour chaque indice j inférieur à indice
                if t[...] == ...:           # Si on trouve x dans la case j
                    return ...
    print("OK AVEC LES 1000 TESTS AUTOMATIQUES")
    return ...                    # si on arrive ici, c'est que tous les tests sont bons
 
tester()

Correction ?

...CORRECTION...

import random
 
def rechercher(t:list, x:int) -> int:
    """Renvoie l'indice de la première occurrence de x dans t, -1 si non présent"""
     
    i = 0                              # On se place sur la première case
    while i < len(t) and t[i] != x:  # Tant qu'il reste des cases et que la case actuelle n'est pas la bonne
        i = i + 1                      # On passe à la case suivante
     
    if i < len(t):                   # Si i obtenu est une valeur possible pour ce tableau
        reponse = i
    else:                              # Sinon, c'est qu'on est sorti du tableau
        reponse = -1
    return reponse                     # Renvoie la réponse
 
def tester():
    for k in range(1000):
        n = random.randint(3, 10)
        t = [random.randint(10, 20) for x in range(n)]
        x = random.randint(8, 22)
        indice = rechercher(t, x)
        print(f"Test {k+1}")
        if indice == -1 and x in t:  # Si on a -1 alors que x est présent
            print("ECHEC DU TEST")
            print(t)  
            print(f"On cherche {x} : réponse {indice}")            
            return False
        else:
            for i in range(0, indice):  # Pour chaque indice j inférieur à indice
                if t[i] == x:           # Si on trouve x dans la case j
                    return False
    print("OK AVEC LES 1000 TESTS AUTOMATIQUES")
    return True                    # si on arrive ici, c'est que tous les tests sont bons
 
tester()

5 - Recherche dans les autres structures

⇩ ⇧ ⤊

Il n'existe aucune différence sur on cherche dans un tuple ou un string.

La fonction permettant de chercher dans un tableau fonctionne aussi bien à travailler sur un tuple ou sur un string.

Reste le cas du dictionnaire, un peu plus complexe. Voyons comment réaliser la version qui utilise la méthode keys() permettant de récupérer les clés une par une.

16° On utilise le même principe sauf qu'on va lire les clés une par une. Dès qu'on trouve le bon élément en tant que valeur associée à une clé, on répond.

Si nous n'avons pas trouvé alors que toutes les clés ont été explorées, c'est que l'élément n'est pas présent. On décide alors de renvoyer un string vide en tant que réponse VIDE.

def rechercher_dico(d:dict, x:int) -> int:
    """Renvoie la clé de la première occurrence de x dans d, -1 si non présent"""
     
     for ... in d.keys():  # Pour toute les clés du dictionnaire
        if ... == ...:                   # Si on trouve la bonne valeur avec cette clé
            return ...
     
    return ""

Correction ?

...CORRECTION...

def rechercher_dico(d:dict, x:int) -> int:
    """Renvoie la clé de la première occurrence de x dans d, -1 si non présent"""
     
     for cle in d.keys():  # Pour toute les clés du dictionnaire
        if d{cle] == x:                   # Si on trouve la bonne valeur avec cette clé
            return cle
     
    return ""

6 - FAQ

⇩ ⇧ ⤊

Chercher, c'est courant... Python ne sait pas faire ça tout seul ?

Si, il existe des fonctions ou méthodes de Python qui permettent de le faire. Mais, comment fonctionnent-elles ?

En NSI, nous cherchons à comprendre et construire, pas simplement utiliser.

Maintenant, vous savez comment cela fonctionne, on peut vous montrer comment le faire en quelques lignes.


>>> t = [40, 70, 30, 20, 30] 
>>> t.index(40)
0
 
>>> t.index(30)
2
 
>>> t.index(80)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: 80 is not in list

7 -

⇩ ⇧ ⤊

Activité publiée le 02 02 2020
Dernière modification : 12 12 2021
Auteur : ows. h.

⏪

⏫

⏩