• 15 heures
  • Facile

Ce cours est visible gratuitement en ligne.

course.header.alt.is_video

course.header.alt.is_certifying

J'ai tout compris !

Mis à jour le 13/12/2019

Quiz 4

Connectez-vous ou inscrivez-vous gratuitement pour bénéficier de toutes les fonctionnalités de ce cours !

Compétences évaluées

  • Se familiariser avec des algorithmes complexes
  • Question 1

    Vrai ou faux ? Deux programmes réalisant la même tâche sont deux programmes équivalents.

    • Vrai

    • Faux

  • Question 2

    Pour lire un prénom dans ma liste de prénoms, cela prend une opération, quel que soit le numéro de la case. Autrement dit, lire le prénom inscrit dans la case n° 1, ou bien dans la case n° 145 ou bien dans la case n° 3000000, se fera toujours en une seule opération et donc coûtera le même temps, quelle que soit la case lue. Avec l’algorithme de la dichotomie et une liste de 128 prénoms (triés par ordre alphabétique), combien d’opérations faut-il, dans le pire des cas, pour affirmer qu’un prénom est dans la liste ou affirmer qu’il n’y est pas :

    • 2 opérations

    • 7 opérations

    • 64 opérations

    • 256 opérations

  • Question 3

    Il existe une activité sympa à faire avec des enfants, qu’on pourrait appeler “le nombre cible”. Il s’agit d’écrire un nombre entre 1 et 100, caché quelque part (derrière le tableau, sur une feuille repliée…) Ensuite, on leur demande de deviner le nombre par essais successifs. Dans un premier temps, sauf coup de bol, on va droit à l’ennui global (après quelques essais cela devient rasoir). On peut ensuite ajouter des éléments pour rendre le jeu plus intéressant. Est-il possible, pour cela, d’utiliser la dichotomie ?

    • Non, c’est impossible car la dichotomie ne fonctionne que sur des mots (comme les prénoms).

    • Oui, ça marche mais seulement avec des mots et des nombres.

    • Oui, ça marche sur n’importe quel type d’objet que l'on peut ranger dans un ordre croissant (des mots, des nombres, des dates de naissance, des références de vols des compagnies aériennes, etc.)