Aller au contenu
Ludicademy
English
Thème Élan
ClairsSombres
S’inscrire

Fiche de révision : Deux algorithmes pour le même résultat : lequel choisir ?

L’essentiel de la leçon, ce qu’il faut retenir, les pièges et un petit test : une page à relire avant le contrôle.

Ludicademyludicademy.fr · apprendre en jouant, du CP à la Terminale
Fiche de révision · Logique · 3e · algorithmique

Deux algorithmes pour le même résultat : lequel choisir ?

Objectif : juste ne suffit pas, il faut aussi savoir compter les gestes

L’essentiel

Deux algorithmes peuvent donner exactement la même réponse et ne pas se valoir. Deviner un nombre entre 1 et 100 en essayant 1, puis 2, puis 3, finit par marcher. Couper l'intervalle en deux à chaque essai marche aussi — en sept essais au pire, contre cent.

À retenir

  • Deux algorithmes justes ne se valent pas : on compte ensuite leurs gestes
  • On compte l'opération qui coûte, en fonction de la taille des données
  • Couper en deux bat le parcours un par un dès que les données sont nombreuses
  • Un petit jeu d'essai ne montre jamais la différence : elle apparaît sur les grands

Le tableau à connaître

Le problèmeLa méthode naïveLa méthode réfléchieSur 100 éléments
Deviner un nombreEssayer 1, 2, 3…Couper en deux à chaque coup100 essais contre 7
Chercher un mot au dictionnaireLire depuis la page 1Ouvrir au milieu, éliminer une moitié1000 pages contre 10
Additionner 1 + 2 + … + 100Ajouter cent foisCinquante paires valant 101100 additions contre 2 opérations
Trouver le plus grandComparer chacun à tousGarder le meilleur vu jusqu'ici4950 comparaisons contre 99

⚠ Attention, piège

  • Un algorithme plus court à ÉCRIRE n'est pas un algorithme plus rapide à EXÉCUTER. « Trier puis prendre le dernier » tient en deux lignes et fait bien plus de travail que le parcours en une variable.

Exemples

  • Trouver le plus grand de 4, 9, 2, 7.

Le plan de la leçon

  1. Le même résultat, pas le même travail
  2. Compter les gestes, pas les secondes
  3. Un exemple qu'on peut dérouler à la main
  4. Ce qu'on compare vraiment

Je me teste

  1. Trouver le plus grand de 100 nombres avec la méthode « meilleur vu jusqu'ici » : combien de comparaisons ?

    1. 100
    2. 99
    3. 4950
  2. Quel critère départage deux algorithmes justes ?

    1. Le nombre d'opérations effectuées
    2. La longueur du texte écrit
    3. L'ordre alphabétique des noms

Le mot d’Oscar — Sur combien de données les avez-vous essayées ?

Réponses : 1. B · 2. A

La leçon complète, ses exercices et ses jeux : ludicademy.fr/lecon/2406fiche de révision · usage libre en classe et à la maison

Toutes les fiches de révision : par matière et par classe · les fiches d’exercices : la bibliothèque.