Aller au contenu

Activités I)

Activité I.01

Faites un schéma permettant d'expliquer le principe de la recherche dichotomique en vous basant sur l'exemple suivant : t = [5, 7, 12, 14, 23, 27, 35, 40, 41, 45] et x = 40 (valeur recherchée).

Activité I.02

Faites un schéma permettant d'expliquer le principe de la recherche dichotomique en vous basant sur l'exemple suivant : t = [5, 7, 12, 14, 23, 27, 35, 40, 41, 45] et x = 9 (valeur recherchée).

Activité I.03

Soit l'algorithme de recherche dichotomique :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
VARIABLE
t : tableau d'entiers trié
mil : nombre entier
fin : nombre entier
deb : nombre entier
x : nombre entier // x : l'entier recherché
tr : booléen
DEBUT
tr ← FAUX
deb ← 1
fin ← longueur(t)
tant que tr == FAUX et que deb ⩽ fin :
 mil ← partie_entière((deb+fin)/2)
 si t[mil] == x :
  tr = VRAI
 sinon :
  si x > t[mil] :
   deb ← mil+1
  sinon :
   fin ← mil-1
  fin si
 fin si
fin tant que
renvoyer la valeur de tr
FIN

1) Appliquez cet algorithme au tableau t = [5, 7, 12, 14, 23, 27, 35, 40, 41, 45] et x = 40. Vérifiez que l'algorithme renvoie bien VRAI.

2) Appliquez cet algorithme au tableau t = [5, 7, 12, 14, 23, 27, 35, 40, 41, 45] et x = 9. Vérifiez que l'algorithme renvoie bien FAUX.

Activité I.04

Implémentez l'algorithme de recherche dichotomique en Python.

Activité I.05

Activité I.06

Activité I.07

Activité I.08

Activité I.09

Activité I.10

Activité I.11

Activité I.12

Activité I.13

Activité I.14

Activité I.15

Activité I.16

Activité I.17

Activité I.18

Activité I.19

Activité I.20