Algorithmes débutants (facultatif)
Le stagiaire chez Amazon : recherche, tri, complexité, glouton, balayage
Dans ce chapitre, vous apprendrez à
- Estimer le coût d'un programme (complexité)
- Choisir la bonne approche : tri, recherche, balayage, choix glouton
Outils : Python
7 exercices
Chaque exercice est corrigé automatiquement, dans le navigateur. Les énoncés complets sont accessibles avec un compte.
À quoi ça sert dans la vraie vie
Deux programmes peuvent donner la même réponse, et pourtant l'un répond en un clin d'œil quand l'autre ne termine jamais. - Les grands catalogues. Un site marchand ou un moteur de recherche retrouve un élément…
Catalogue infini
Bienvenue chez MegaStock, le plus grand entrepôt d'Europe. Premier jour de stage. Votre manager vous tend une tablette : "Un client veut le produit
#738291045. Le catalogue contient 1 milliard de produits…File d'attente
Deuxième jour de stage. Le responsable logistique vous explique : "On a deux zones de traitement. Dans la Zone A, les commandes sont traitées dans l'ordre d'arrivée : la plus ancienne d'abord. Dans la Zone B…
Tri du convoyeur
Troisième jour. Le convoyeur principal est en panne : les colis arrivent dans un ordre aléatoire, mais le camion de livraison exige un chargement trié par poids (du plus léger au plus lourd). Votre seule capacité…
Compteur de temps
Votre manager vous donne, pour une routine interne
routine(n)dont personne ne connaît le code, ses temps d'exécution mesurés à différentes tailles d'entrée : une listemeasurementsde paires…Intervalles de livraison
Fin de semaine. L'entrepôt a un seul camion ce samedi. Chaque client a une fenêtre de livraison
[start, end]. Le camion ne sert qu'un client à la fois : une fois une livraison commencée, il est occupé jusqu'à la fin…Balayage du scanner
Dernier projet du stage. L'entrepôt est équipé d'un scanner laser qui balaye les étagères de gauche à droite. Chaque produit sur une étagère occupe un rectangle défini par
[x_start, x_end, hauteur]. Les rectangles…