66 lines
2.0 KiB
Markdown
66 lines
2.0 KiB
Markdown
# Mini-projets — Algorithmes de tri et recherche dichotomique
|
|
|
|
Séance de révision avant DS (mardi). Chaque groupe reçoit un projet différent.
|
|
Durée : **1h à 1h30**. Langage : **Python** (sauf projet 09 : Python + HTML/CSS).
|
|
|
|
> **Règle commune** : vous devez implémenter vous-mêmes `tri_insertion`, `tri_selection` et `dichotomique`. **Interdiction d'utiliser `sort()` ou `sorted()`.**
|
|
|
|
---
|
|
|
|
## Répartition des groupes
|
|
|
|
| # | Projet | Algorithmes utilisés | Difficulté |
|
|
|---|--------|----------------------|------------|
|
|
| 01 | [Le Nombre Mystère](01_devine_nombre/) | Dichotomie | Facile |
|
|
| 02 | [Le Tri de Cartes](02_cartes/) | Tri insertion | Facile |
|
|
| 03 | [Le Podium](03_podium/) | Tri sélection + Dichotomie | Facile |
|
|
| 04 | [L'Annuaire](04_annuaire/) | Tri insertion + Dichotomie | Moyen |
|
|
| 05 | [Le Correcteur](05_correcteur/) | Tri insertion + Dichotomie (voisins) | Moyen |
|
|
| 06 | [La Bibliothèque](06_bibliotheque/) | Tri sélection + Dichotomie | Moyen |
|
|
| 07 | [La Météo](07_meteo/) | Tri insertion + Dichotomie | Moyen |
|
|
| 08 | [La Course des Algos](08_course_algos/) | Tri insertion vs Tri sélection | Difficile |
|
|
| 09 | [Le Générateur Web](09_generateur_web/) | Tri insertion + Dichotomie → HTML | Difficile |
|
|
|
|
---
|
|
|
|
## Rappels des algorithmes
|
|
|
|
```python
|
|
def tri_insertion(tab):
|
|
for i in range(1, len(tab)):
|
|
x = tab[i]
|
|
j = i
|
|
while j > 0 and tab[j - 1] > x:
|
|
tab[j] = tab[j - 1]
|
|
j -= 1
|
|
tab[j] = x
|
|
return tab
|
|
|
|
def tri_selection(tab):
|
|
n = len(tab)
|
|
for i in range(n):
|
|
mini = i
|
|
for j in range(i + 1, n):
|
|
if tab[j] < tab[mini]:
|
|
mini = j
|
|
tab[i], tab[mini] = tab[mini], tab[i]
|
|
return tab
|
|
|
|
def dichotomique(tab, x):
|
|
a = 0
|
|
b = len(tab) - 1
|
|
while a <= b:
|
|
m = (a + b) // 2
|
|
if tab[m] == x:
|
|
return True
|
|
elif tab[m] < x:
|
|
a = m + 1
|
|
else:
|
|
b = m - 1
|
|
return False
|
|
```
|
|
|
|
---
|
|
|
|
Auteur : Florian Mathieu — Licence CC BY NC
|